August 2008 - Libraries

Interleave two lists
by Sean Leather 28 Aug '08

28 Aug '08

Mark Jones gave several talks at Advanced Functional Programming 2008. In one of them, he presented approaches to enumerating the elements of various datatypes. I found several interesting things in it, but one function stuck out as being perhaps useful in general. infixr 5 ||| (|||) :: [a] -> [a] -> [a] [] ||| ys = ys (x:xs) ||| ys = x : ys ||| xs It interleaves the elements of two lists. It's defined exactly as (++) with the exception that the arguments are swapped for the recursive application. This works nicely when one wants to merge infinite lists. For example, suppose you want a list of the enumerable numbers with a balance of positive and negative: enums :: (Num a, Enum a) => [a] enums = [0..] ||| map negate [1..] You can't use (++) here, because the left side never completes. Does (|||) seem useful to others? Is it already available in some other form (or in a library) of which I'm not aware? If yes and no are the answers, then I wonder if it's useful enough for Data.List (modulo any expected renaming). Sean

5 4

Developing SYB, packaging issues
by José Pedro Magalhães 24 Aug '08

24 Aug '08

Hello all, This message focuses on a problem Claus mentioned before: > One other thing I meant to ask was about procedure, > given that Syb is currently in base and hence under the > library modification process. How is this going to combine > with an active maintainer and some parts on hackage? > > Claus To be able to further develop SYB (see [1] for history), it's probably best to develop it as a separate package, which people can install, upgrade, etc. This would mean the library could be updated independently of GHC, and new GHC releases could then use the most recent version of the package. But how do these things merge? Can/should SYB be moved out of the base package? And, if this happens, can the library being developed as a separate package still use the automatic deriving mechanism? I'm sending this message to libraries(a)haskell.org too because I guess this problem might have shown up here before. Cheers, Pedro [1] http://search.gmane.org/?query=%22Owning+SYB%22&group=gmane.comp.lang.haske…

4 7

Syb Renovations? Issues with Data.Generics
by Claus Reinke 21 Aug '08

21 Aug '08

Calling all Syb/Data.Generics users!-) I keep running into problems with Data.Generics, mostly because I actually want to use it (no claims that it is the best or final solution, or that other approaches aren't equally in need of support, just that it is the best-supported working approach right now). Some tricky issues are (sometimes against published expectations) solvable, suggesting useful additions to the library, but some seemingly trivial things have me stumped, suggesting (to me, at least;-) a need for improvements either in the library or in its documentation. Part of the reason I'm interested in this now is that Data/Typeable instances seem likely (I hope:-) to be added to the GHC Api, where Thomas Schilling is working on improvements http://hackage.haskell.org/trac/ghc/wiki/GhcApiStatus http://hackage.haskell.org/trac/ghc/wiki/GhcApiAstTraversals also, the old question of porting HaRe to the GHC Api is currently being looked into again, by Chaddaï Fouché, and crucially depends on Syb's generic traversals. As it is still holiday season, it is a bit early for proposal deadlines, but I'd like to start a discussion of Syb/Data.Generics and collect the issues and solutions arising, in the hope of following up with concrete proposals for improvements. To start the discussion, a simple item: 1. inconvenient convenience instances of Data for non-"data" types Data.Generics.Instances defines instances of Data for many types, including some abstract types that don't really fit into the concrete value based model of Data, like 'IO a' and 'a->b'. Those instances give runtime errors for some class methods, and mainly offer faked (no-op) gmap traversals, serving as a convenience/enabler for 'deriving instance Data': http://www.haskell.org/pipermail/generics/2008-June/000346.html A list of the odd instances in Data.Generics.Instances, with examples of their oddities, can be found here: http://www.haskell.org/pipermail/generics/2008-June/000347.html My suggestion is to split this module into two, and stop the implicit import/export of the incomplete instances from Data.Generics. Reactions to this suggestion have been muted so far (Simon PJ was as surprised as I was about the existence of these instances, but has no strong opinion about the issue, Alexey Rodriguez supports the suggestion, Ian Lynagh points out the difficulty of transition), which is one reason why I'll try to move the discussion to libraries@. Pro: - the instances are still available, and only one explicit import away, so 'deriving instance Data' for types containing uninteresting functions is still convenient - the problematic instances are no longer implicitly imported, so applications that don't want these instances can now avoid them completely, or define their own instances - these convenience instances are not just inconvenient for some applications, due to the way intances are handled in Haskell; they actually violate some "natural" invariants like "everything queries every substructure of the specified type", "everywhere applies a transformation at every substructure of matching type" - the situation is similar to Text.Show.Functions, as the convenience instances don't provide the full expected functionality, just barely enough for deriving to get by Cons: - due to the implicit import and use of these instances, there is no obvious transition scheme; it seems that the least painful process would be to make the change without transition/deprecation period and to document the explicit import option [it would be useful to have a way of deprecating instance imports, so that any deriving scheme depending on imports from a deprecated location would trigger a warning, in this case suggesting the new import location] As I said, I'd like to wait until at least the Syb authors are back from holidays before setting any proposal deadlines, but I'd like to invite feedback from Syb users on this and other Syb issues. Here is a preview on other items I'd like to raise later on, please add your own: 2. Data.Generics.Utils Since Data/Typeable are compiler-derivable (in GHC) while other classes like Functor/Traversable/etc are not, it would be useful if generic instances for those other classes could be defined in terms of Data/Typeable. The Uniplate library already does this for its own classes via Data.Generics.PlateData, and it appears that at least Functor is defineable as well (code exists, proof is only informal at this stage, and those invariant violations and runtime errors in the implicitly imported dummy instances from (1) really get in the way): http://www.haskell.org/pipermail/generics/2008-June/000343.html http://www.haskell.org/pipermail/generics/2008-July/000349.html http://www.haskell.org/pipermail/generics/2008-July/000351.html What other classes can be defined in this way? Traversable (traverse) seems very nearly possible, what else? 3. Performance Naive use of Syb traversal schemes can lead to huge performance losses. Experienced users tend to write their own traversal schemes, using Syb's low-level Api directly, but we can take inspiration from some Uniplate/PlateData optimization techniques and generalise them for use with Syb's high-level traversal scheme Api, yielding similar performance gains for everywhere/everything: http://www.haskell.org/pipermail/generics/2008-July/000353.html Another direction that might be worth exploring is to use Maps instead of nested generic extensions to define adhoc-overloaded transformation and queries (I've actually started playing with that, but am currently stuck on GHC ticket #2463). 4. Useability There is probably nothing one can do to make the types of Syb's low-level Api less of a brain hazard, but not all of the stumbling blocks seem to be necessary consequences of the carefully crafted edifice of interactions between nearly polymorphic types, runtime type checks and type reflection. Examples: - there doesn't seem to be a way to get hold of a types' constructors, only of constructor representations, structure scaffolds, and structure generators - the actual domain on which a transformation/query acts is hidden behind the near-polymorphic default type of generic extensions - I can't seem to figure out how to use typeOf1, when the other Syb operations only give me 'forall a . Data a => a'; instead, I seem to be forced to use something like: [ mkTyConApp tyCon (init tyArgs) | not (null tyArgs) ] where (tyCon,tyArgs) = splitTyConApp typeRep - others? What are your personal gripes with Syb/Data/Typeable, and for which of them do you see a chance of addressing them by changing/adding code? Claus

5 12

Cabal question: Generated data files
by Neil Mitchell 20 Aug '08

20 Aug '08

Hi, First off, this list seems a bit off-topic for a question about Cabal, but its what the web page told me to do: http://haskell.org/cabal/ - if this isn't the place for this email, could someone update the web page? The question is about generated data files, specifically for Hoogle. Hoogle generates search databases, which I want to be installed as read-only data, in datadir. For a release I want to bundle up these databases in the tarball, pregenerated. I don't want to include these databases in the darcs version (they are fairly specific to a particular version and regularly changing), but I do want people to be able to build the darcs version using cabal. To generate these databases requires a second Haskell program (included in the darcs repo), and an installed copy of the same version of Hoogle. So, I want to generate database files, which can only be done after install time, but which I then want to be installed. Is there any way to acheive this? Or some better idea? Currently I just generate the databases and have the .cabal file reference them, which means the darcs version can't be compiled with Cabal. Thanks Neil

3 7

Proposal: Reserved module namespace for packages on Hackage
by David Menendez 20 Aug '08

20 Aug '08

In the interests of reducing module name collisions, I suggest reserving part of the module name space for individual packages on Hackage. Specifically, I'm suggesting that a new top-level module name, "Lib", be added to the module naming conventions, and that the children of "Lib" be reserved for the Hackage package with the same name. That is, "Lib.Foo" and "Lib.Foo.*" would be reserved for the package "Foo" on Hackage. This would not require packages to *use* this namespace. However, packages that do use it would have a greatly reduced chance of conflicting with other packages. Implementation costs are minor. At most, we might want some code in Hackage to prevent packages from using module names reserved for other packages. At the least, all we need to do is add "Lib" to the list of allowable top-level module names. Developers who object to giving the provenance of a module in its name are free to take their chances with the rest of the module hierarchy. Mapping package names to module names is mostly straightforward. According to the Cabal documentation, a package name consists of one or more alphanumeric words separated by hyphens, where each word contains at least one letter. Since hyphens aren't allowed in module names, they would get mapped to underscores, which are not allowed in package names. Thus, "Lib.Foo_Bar" would be reserved for package "Foo-Bar". It's less obvious what to do with packages whose names start with lower-case letters or digits. I see three possible solutions: (a) Do not reserve module names for these packages. (b) Map these package names to module names in a way that avoids conflicts, e.g., prefixing the package name with "P'", which cannot occur in a package name. That is, package "foo" would get "Lib.P'foo". (c) Change the rules for package names on Hackage by disallowing package names which start with a digit or which differ from an existing package only in the case of the first letter, and reserve module names based on capitalized package names. That is, package "foo" would get "Lib.Foo", and Hackage would not accept a new package "Foo" if there was a preexisting "foo", and vice versa. My preference is for (c). In fact, I might go further and forbid any package whose name differs only in case from an existing package in Hackage. Further thoughts: (1) I chose "Lib" because it's short and, so far as I know, unused. "Hackage" might be a better choice, since the scheme depends on Hackage to prevent name collisions. (2) It was surprisingly difficult to find out the rules for valid package naming. None of the tutorials I found discussed choosing a valid name. The GHC documentation mentions that package names must have a specific form, but I couldn't find any description of it. (3) I did not find a definition of "alphanumeric" in the Cabal documentation. Does this include non-ASCII characters? (4) We could also reserve additional module names corresponding to specific versions of packages, e.g., "Foo-1.0" might get "Lib.Foo_1_0". This does not create ambiguity, because "Foo-1-0" is not a valid package name.

7 9

Re: cabal-install calls setup with unrecognised distpref flag
by José Pedro Magalhães 19 Aug '08

19 Aug '08

Hello all, I decided to bring this to libraries(a)haskell.org too in case anyone had the same problem before. Cheers, Pedro On Wed, Aug 6, 2008 at 11:38, José Pedro Magalhães <jpm(a)cs.uu.nl> wrote: > Hello all, > > Recently, while developing a package here in the group, we changed the > build-type from "Simple" to "Custom" to allow for "cabal test". The Setup.hs > simply calls defaultMainWithHooks with simpleUserHooks where runTests has > been redefined. > > The problem is that this change gives me the following error when invoking > "cabal build" (after invoking "cabal configure"): > setup.exe: Unrecognised flags: > --distpref=dist > > runhaskell Setup.hs build works fine, though. This happens on a win64 > machine, cabal-install version 0.5.1 using version 1.4.0.1 of the library. > On a mac there seem to be no problems, though. > > Am I doing something wrong? > > > Thanks, > Pedro >

2 2

Re: [Haskell] ANN: witness 0.1, open-witness 0.1, "Witnesses and Open Witnesses"
by Don Stewart 18 Aug '08

18 Aug '08

ashley: > witness 0.1 > A witness is a value that witnesses some sort of constraint on some list > of type variables. This library provides support for simple witnesses, > that constrain a type variable to a single type, and equality witnesses, > that constrain two type variables to be the same type. The library also > provides classes for representatives, which are values that represent types. snip > open-witness 0.1 > Open witnesses (type IOWitness) are simple witnesses that can witness to > any type. However, they cannot be constructed, they can only be > generated in certain monads: snip > Hackage: > <http://hackage.haskell.org/cgi-bin/hackage-scripts/package/open-witness> > Source: <http://code.haskell.org/open-witness/> You can find these packages for your local Arch Linux distribution, http://aur.archlinux.org/packages.php?ID=19194 http://aur.archlinux.org/packages.php?ID=19195 Come on Debian! :) -- Don

1 0

Re: laziness of intersperse
by Thomas Schilling 17 Aug '08

17 Aug '08

On Sun, Aug 17, 2008 at 9:43 AM, Barton C Massey <bart(a)cs.pdx.edu> wrote: > Maybe something like > > intersperse _ [] = [] > intersperse sep (x : xs) = > x : concatMap ((sep :) . (: [])) xs > > is clearer (maybe), but I doubt it's as efficient (although > I haven't checked). concatMap is a bit tricky when it comes to performance. I also think the low-level loop implementation that duncan showed is rather readable. > Thanks much for the corrections! (I hope it's OK to do this on-list.) Of course. Nobody gets it right the first time. (Well, maybe Oleg. But then again we have some doubts whether he is from this planet or, if he is, perhaps from the future.)

1 0

laziness of intersperse
by Reid Barton 16 Aug '08

16 Aug '08

(This is the same issue as http://www.haskell.org/pipermail/haskell/ 2004-March/013739.html but there was no follow-up at that time.) The intersperse library function is not as lazy as it could be. The current definition of intersperse is intersperse :: a -> [a] -> [a] intersperse _ [] = [] intersperse _ [x] = [x] intersperse sep (x:xs) = x : sep : intersperse sep xs For any list (x:xs) not containing _|_, intersperse sep (x:xs) is a list of the form (x:...); yet intersperse sep (x:_|_) = _|_ because the pattern match on the second equation diverges. A better definition would be intersperse _ [] = [] intersperse sep (x:xs) = x : intersperseWithPrefix xs where intersperseWithPrefix [] = [] intersperseWithPrefix (x:xs) = sep : x : intersperseWithPrefix xs (slightly modified from http://www.haskell.org/pipermail/haskell/2004- March/013741.html) An application: There was a question on #haskell about how to compute the "ruler" sequence [1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,...]. The definition ruler = fix ((1:) . intersperse 1 . map (1+)) works with the properly lazy intersperse, but not with the intersperse in Data.List. Comments on this new definition? Can it get added to Data.List? Regards, Reid Barton

6 5

darcs patch: Fix oversight in Control.OldException
by Bertram Felgenhauer 16 Aug '08

16 Aug '08

Sat Aug 16 15:26:31 CEST 2008 Bertram Felgenhauer <int-e(a)gmx.de> * Fix oversight in Control.OldException The NonTermination constructor slipped through in the Exception instance.

2 1