August 2007 - Libraries

ANN: HIntegerByInt
by Isaac Dupree 13 Aug '07

13 Aug '07

LICENSE: BSD3 (or also similar, like GHC, etc.) INITIAL AUTHOR: Isaac Dupree <id(a)isaac.cedarswampstudios.org> What is this? It is a reimplementation, in Haskell, of the Integer type that Haskell provides in its Prelude. It is designed in mind of being actually usable as the implementation of that type, for compilers. It is also a module that exports a working Integer type. It is in terms of only basic Prelude functions, [], and Int. It is NOT a purely inductive definition, because Int is much faster than a purely inductive definition would allow, and nevertheless often easier to come by (more portable, license-wise, size-wise, nuisance-wise...) than GMP or other C bignum libraries. /========= darcs repo: http://isaac.cedarswampstudios.org/2007/HIntegerByInt I'm rather proud of it in a silly way: I have run into bugs in *all* major Haskell implementations I tried it with, while testing it (see COMPILERS section). Reminds me somewhat of GMP triggering compiler bugs actually:) All the implementation and documentation is currently in one file "IntegerInTermsOfInt.hs", except for three auxiliary modules for testing, where CheckIntegerInTermsOfInt is a Main module that uses QuickCheck. I have copied some of that documentation here. From here, I offer it to anyone who is interested it using it and will try to help as needed, but I'm not likely to search out compiler internals myself just to try it in them. I didn't give it a version number or Cabal file because it is completely useless on its own, as a library, in view of Prelude already providing a very good Integer. \========== SPEED: It is not too slow on small numbers (smallish constant - much larger than for Int of course), not too slow on medium-size numbers (which I've been testing it with), and not too slow on large numbers (asymptotically; karatsuba multiplication, O(n^1.585) is used to split up large numbers, and division by large numbers uses multiplication and Newton's method). Also see BUGS for the speed of 'show'. CORRECTNESS: It seems to be correct, after a fairly thorough million-iteration QuickCheck in GHC plus a lot of quickcheck testing using debugging-"Int"s that tell you when they overflow and have (minBound,maxBound)=(-31,31). Each of these caught an incredible number of bugs, which is why I am inclined to trust them. Unfortunately, most Haskell implementations are somewhat incorrect - see COMPILERS. Also see CAVEATS(c) for *very* large numbers. CAVEATS: a- It is obviously much slower than GMP. (although I don't know if the penalties for calling primitive/foreign functions counterbalance that for small numbers.) b- It assumes that Int operations are fairly fast, although it doesn't tend to waste them that much (e.g. it uses `quotRem` when it needs both, which is almost always). c- It is expected to break when handling values with magnitude greater than around ( (maxBound::Int)^(maxBound::Int) ). (just like GMP. Probably the assumption is that you'll run out of memory at the same time, or that the operations will take SO LONG, so no-one cares. Prelude.length will (relatedly) also break at this point.) USAGE AS NATIVE INTEGER: Completely untried so far (search file for INTERESTING to customize). The algorithms are quite separable from the newtype Integer and its instances, and Bits, Ix... parts can be separated out too (in which case a proper export list would have to be made for the algorithm functions, which might hinder optimization a little, if assuming separate compilation...). See <http://www.haskell.org/ghc/docs/ latest/html/libraries/base/Prelude.html#t%3AInteger> for all things GHC's Prelude.Integer be an instance of, including Typeable? Data? NFData? PrintfArg? Typeable? Random? This is also a purpose CPP could be useful for, to define (#define?) quotRemDInt and such type-specific things, conditionally on how this Integer-implementation is being used. The internal format is (currently) a list([]) of Ints in base "intLargeBase", least-significant "digit" first (negative x is represented by negating all elements of the list that represents positive x) (No most-significant zeroes are allowed (so zero is represented by the empty list, for example)) ("intLargeBase" is customizable, although there is an optimal value for any particular size of Int, and a limit based on the Int's size) TODO/BUGS: COMPILERS. a- There is one WORKAROUND so Hugs can compile it and two for nhc/yhc. Even so, I refused to keep a third workaround for N/Yhc, but that is for a nyhc bug that Neil thinks should be reasonably fixable. b- though extensively QuickChecked in GHC, Hugs occasionally fails QuickCheck, but when the particular example is run in Hugs, it gives the correct answer! I think Hugs is buggy. (Hugs Version September 2006) c- ghc -O -fvia-C may miscompile "quotRem x (some power of two)". (ghc trac#1603) If QuickCheck fails badly on you, try adding -fasm. d- Beware testing in interpreters - some (at least GHCi 6.6.1) will default to Prelude.Integer even if the module has "default ()". Make show faster than O(n^2), e.g. see http://darcs.haskell.org/packages/base/GHC/Num.lhs ? ...but converting that, it seemed altogether slower than the current [and there is more in IntegerInTermsOfInt.hs] Isaac

5 9

wORD_SCALE etc.
by Roman Leshchinskiy 13 Aug '07

13 Aug '07

Hi Ian, in the new array package, Data.Array.Base is a hidden module. Trouble is, it defines wORD_SCALE, fLOAT_SCALE, dOUBLE_SCALE and various bOOL_* things which are generally useful and used by NDP. I could work around this by simply redefining them in the ndp package, but I don't like that. Should they perhaps be exported from array? Cheers, Roman

2 2

gnomevfs2
by Ashley Yakeley 12 Aug '07

12 Aug '07

Has anyone created Haskell bindings for gnomevfs2? -- Ashley Yakeley

2 2

Re: patch applied (packages/containers): Remove the rest of base to leave a "containers" package
by ross＠soi.city.ac.uk 12 Aug '07

12 Aug '07

Quoting Ian Lynagh <igloo(a)earth.li>: > Wed Aug 1 15:38:31 PDT 2007 Ian Lynagh <igloo(a)earth.li> > * Remove the rest of base to leave a "containers" package There may be a case for treating the constructor classes (in Data.Foldable and Data.Traversable) differently from the concrete container types (Data.Set et al). For example, to accomodate the instances for Array in the current setup, one of array and containers must depend on the other, although they are not otherwise related. ---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.

5 4

Proposal: Make arrays safer
by Ian Lynagh 10 Aug '07

10 Aug '07

Hi all, Proposal: http://hackage.haskell.org/trac/ghc/ticket/1610 This is a proposal to make arrays safer, e.g. see: http://hackage.haskell.org/trac/ghc/ticket/1046 This is a divergence from Haskell 98. The patches: * Add (numElements :: Ix i => a i e -> Int) to IArray class * Array types get an extra field for numElements, e.g. -data UArray i e = UArray !i !i ByteArray# +data UArray i e = UArray !i !i !Int ByteArray# This is a cache of rangeSize(l,u) * Add safeRangeSize (always returns >= 0) * Add safeIndex (use unsafeIndex (no Ix inRange check), but check index < numElements) * unsafeForeignPtrToStorableArray gained an (Ix i) context * Use the new functions in various places Suggested deadline: 24 Aug 2007. Thanks Ian

2 2

"Data.TupleFields" for review
by Samuel Bronson 09 Aug '07

09 Aug '07

Hi. I wrote a module and dons suggested I ask you guys for some tips. Here's a good deal of it: ----------------------------------------------------------------------------- -- | -- Module : Data.TupleFields -- Copyright : (c) 2007 Samuel Bronson -- License : BSD3-style -- -- Maintainer : naesten(a)gmail.com -- Stability : experimental -- Portability : non-portable (multi-param classes, functional dependencies) -- -- -- This module provides tuple field access similar to ML's #1, #2 etc. -- ------------------------------------------------------------------------ {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-} module Data.TupleFields where import Data.Tuple class Field1 t f | t -> f where field1 :: t -> f field1_u :: (f -> f) -> (t -> t) field1_s :: f -> (t -> t) field1_s x = field1_u (const x) class Field1 t f1 => Field2 t f1 f | t -> f where field2 :: t -> f field2_u :: (f -> f) -> (t -> t) field2_s :: f -> (t -> t) field2_s x = field2_u (const x) class Field2 t f1 f2 => Field3 t f1 f2 f | t -> f where field3 :: t -> f field3_u :: (f -> f) -> (t -> t) field3_s :: f -> (t -> t) field3_s x = field3_u (const x) class Field3 t f1 f2 f3 => Field4 t f1 f2 f3 f | t -> f where field4 :: t -> f field4_u :: (f -> f) -> (t -> t) field4_s :: f -> (t -> t) field4_s x = field4_u (const x) class Field4 t f1 f2 f3 f4 => Field5 t f1 f2 f3 f4 f | t -> f where field5 :: t -> f field5_u :: (f -> f) -> (t -> t) field5_s :: f -> (t -> t) field5_s x = field5_u (const x) class Field5 t f1 f2 f3 f4 f5 => Field6 t f1 f2 f3 f4 f5 f | t -> f where field6 :: t -> f field6_u :: (f -> f) -> (t -> t) field6_s :: f -> (t -> t) field6_s x = field6_u (const x) class Field6 t f1 f2 f3 f4 f5 f6 => Field7 t f1 f2 f3 f4 f5 f6 f | t -> f where field7 :: t -> f field7_u :: (f -> f) -> (t -> t) field7_s :: f -> (t -> t) field7_s x = field7_u (const x) instance Field1 ((,) t1 t2) t1 where field1 ((,) x1 x2) = x1 field1_u f ((,) x1 x2) = (,) (f x1) x2 instance Field2 ((,) t1 t2) t1 t2 where field2 ((,) x1 x2) = x2 field2_u f ((,) x1 x2) = (,) x1 (f x2) instance Field1 ((,,) t1 t2 t3) t1 where field1 ((,,) x1 x2 x3) = x1 field1_u f ((,,) x1 x2 x3) = (,,) (f x1) x2 x3 instance Field2 ((,,) t1 t2 t3) t1 t2 where field2 ((,,) x1 x2 x3) = x2 field2_u f ((,,) x1 x2 x3) = (,,) x1 (f x2) x3 instance Field3 ((,,) t1 t2 t3) t1 t2 t3 where field3 ((,,) x1 x2 x3) = x3 field3_u f ((,,) x1 x2 x3) = (,,) x1 x2 (f x3) The module goes on to define instances for all the tuple types up through (,,,,,,) (7-tuples). Any suggestions?

3 4

Re: "Data.TupleFields" for review
by Samuel Bronson 09 Aug '07

09 Aug '07

On 8/9/07, Ketil Malde <ketil(a)ii.uib.no> wrote: > On Wed, 2007-08-08 at 22:30 -0400, Samuel Bronson wrote: > > > -- This module provides tuple field access similar to ML's #1, #2 etc. > > Perhaps the naming could be improved? > > Lisp calls these first, second, third, etc and nth for the general case. > (Ignoring the more esoterically named car, cadr, etc, and the fact that > they operate on lists) > > Also, I presume the abbreviations are _u for update, _s for set? Unless > this goes into a standard library (replacing fst and snd?) and thus > becomes ubiquitously used, I'd prefer less cryptic names, perhaps > mapFirst, setSecond, etc. I think 'map' gives the correct connotation, > rather than 'update'. The only convention I'd seen for this when I picked those names was the one that DrIFT implements, so that's what I used. I've since learned that Derive implements a different convention, with names like setFoo where DrIFT would have foo_s, though it doesn't seem to have an equivalent for foo_u. I'm not sure I want map; perhaps some variant of modify... > (Private reply only, as the list won't accept mail from an address the > MUA will let me use. Feel free to cite in public.) How do you know that the list won't accept mail from your address?

1 0

Cabal bug
by Simon Peyton-Jones 03 Aug '07

03 Aug '07

I have not been following the recent work on Cabal, but I tried to build in the gap before this patch was committed. I Fri Aug 3 18:57:01 GMT Daylight Time 2007 Thomas Schilling <nominolo(a)gmail.com> * Fix tab in Cabal.cabal. I was surprised to find that tabs are disallowed in cabal files. Is that really the intention? It seems like a pitfall for the unwary! At the very least, if they must be disallowed, could the error message be more informative? At the moment we get Setup.exe: Cabal.cabal:70: Unrecognized field format: 'Distribution.Simple.SetupWrapper,' It'd be better to get Setup.exe: Cabal.cabal:70: illegal tab character: replace with spaces Simon

3 4

RE: [Haskell-cafe] Definition of the Haskell standard library
by Simon Peyton-Jones 01 Aug '07

01 Aug '07

| On the other hand, it's not entirely true that there's no standard | library, it's just that it's borders are slightly fuzzy. For example, we | do have the library change submission process for modifying the standard | libraries. Up until now that has been taken to mean changes to the base | package. That package is now being split up, so we'll have to think | about what it'll apply to in the future. | | My opinion is that in the past it has been too difficult to get changes | into the base library, that there's been too much stability at the | expense of improving scope and quality. Making it easy to install new | packages and upgrade existing standard libraries should make it easier | to trial more major changes outside of the standard libs before | proposing getting those changes integrated. All true, but not so helpful for Joe User. For Joe, I think it might be helpful to have some easily-discoverable notion of which package quality and stability. - Package X is "blessed"; lots of people have argued over its design, it's stable, widely used, and actively maintained. Changes to this package goes through a quality-control process. - Package Y is a bit specialised, but it's the result of work by a small group, and it's actively maintained. - Package Z is designed, written, and maintained by one person. That person has kindly put it on Hackage so that others may share it, but you probably don't want to rely on it unless you are happy to help maintain it. Then, in effect, the "standard library" is all the X packages. I wonder if it'd help to have some descriptions such as those above (better worded), and use them? Cabal already has a "stability" indication, and that might serve, but we'd want to articulate much more clearly what it meant. Simon

5 5