March 2006 - Libraries

Edison 1.2rc2
by Robert Dockins 07 Mar '06

07 Mar '06

Greetings! The second release candidate for Edison 1.2 is now ready for comments. The notable changes from RC1 are: * add strict variants of all folds and reduces * reverse argument orders to 'rcons' and 'lookup*' in Sequence * Add symbolic operators for lcons, rcons, append, and lookup from the Sequence API * Add symbolic operators for subsetEq, difference, intersection and union from the set API * rename 'single' to 'singleton' in all APIs * rename 'intersect' to 'intersection' in Collection and Associated Collection APIs * add 'adjustOrInsert' to the Associated Collection API (see http://www.haskell.org//pipermail/libraries/2006-February/ 004952.html for a use case) And the following are the remaining major issues I'd like to get feedback about: -- Edison defines 'subset' and 'subsetEq' in the set API. Data.Set has operations with the same meanings named 'isProperSubsetOf' and 'isSubsetOf'. I am considering adoping the Data.Set names, but they are quite a bit longer. Also what about the meaning of "subset" vs "proper subset"? What do you find most intuitive? -- Data.Map defines 'isSubmapOfBy' and 'isProperSubmapBy'. Edison has no corresponding API methods. Are they important enough to add? -- What do you think about the symbolic operators? Is the fact that (++) clashes with the Prelude a problem? Should the operators be folded into the "Data.Edison" module instead? (see http://www.eecs.tufts.edu/~rdocki01/docs/edison/Data-Edison- Sym.html) In addition, I'm interested in any API related feedback you might have. Code and docs can be found at the project website: http://www.eecs.tufts.edu/~rdocki01/edison.html Or you can go directly to the haddock docs: http://www.eecs.tufts.edu/~rdocki01/docs/edison/index.html Or the darcs repo: http://www.eecs.tufts.edu/~rdocki01/edison/ Thanks, Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG

7 14

n-Tuple maps
by Jean-Philippe Bernardy 07 Mar '06

07 Mar '06

Hello Adrian, On 3/6/06, Adrian Hey <ahey(a)iee.org> wrote: > Hello Jean-Philippe, > > I haven't had much time to study this, but in the light of recent > discussions about generalised tries I played about a little last night > and did have a go at producing n-Tuple maps from instances of your classes. > e.g. for pairs I ended up trying to define something like this.. > > instance (MapLike c1 k1 c2, MapLike c2 k2 a) => MapLike (Map2 c1) (k1,k2) a > where.. Not sure I got what you want to do exactly, but here's what I came up with: (using Indexed because it's lighter, but the idea is the same for Map.) module Map2 where import Data.Collections newtype Map2 c1 c2 k1 k2 v2 = Map2 c1 instance (Indexed c1 k1 c2, Indexed c2 k2 v2) => Indexed (Map2 c1 c2 k1 k2 v2) (k1,k2) v2 where (!) (Map2 c1) (k1,k2) = (c1 ! k1) ! k2 > I must admit I found it hard going, but maybe I'm just using it wrong and > I didn't have much time to play about with alternatives. Perhaps you'd care > to give it a shot. You "just" need to witness the types you define Map2 for as parameters. A bit tricky, I grant you, but nonetheless logical. Once I got used to it I didn't find it any more difficult than the constructor-class approach. Cheers, JP.

2 1

Applicative and Functor
by Ashley Yakeley 07 Mar '06

07 Mar '06

Shouldn't Applicative be a subclass of Functor? "<$>" can then be dropped. The Functor laws are this: fmap id = id fmap (a . b) = (fmap a) . (fmap b) These are already implied by the Applicative laws: (<$>) id = id Proof: LHS = (<$>) id = \v -> id <$> v = \v -> (pure id) <*> v -- "pure application" = \v -> v -- "identity" = id = RHS QED. (<$>) (a . b) = ((<$>) a) . ((<$>) b) Proof: LHS = (<$>) (a . b) = \v -> (a . b) <$> v = \v -> pure (a . b) <*> v -- "pure application" = \v -> (pure ((.) a) <*> (pure b)) <*> v -- "homomorphism" = \v -> ((pure (.) <*> (pure a)) <*> (pure b)) <*> v -- "homomorphism" = \v -> (pure a) <*> ((pure b) <*> v) -- "composition" = \v -> (a <$> (b <$> v)) -- "pure application" = ((<$>) a) . ((<$>) b) = RHS QED. -- Ashley Yakeley

2 8

a proposal regarding libraries
by Isto Aho 04 Mar '06

04 Mar '06

Hello, What do you think about the following proposal to try to activate people to build up new not-yet-seen Haskell libraries? I remember a discussion a couple of months ago where somebody said that it is more important to have imperfect libraries than to not have a perfect one. This proposal aims for populating your favorite missing libs... First, the libs could be diveded into two parts: to those that are under construction (where some reorganization may occur in near future ~ dev libs) and to those that are more or less stable (where reorganization is not likely to occur in the next few years ~ stable libs). And these libs could be distributed with the Haskell compilers so that they are usable instantly. Second, to populate the dev libs with new funcs, it would be relatively easy to organize monthly competitions with the new HaskellWiki-pages. Idea could be something like - On the first day of the month, a lib design is released on the HaskellWiki, giving 12 competitions a year. - Who completes most of the funcs, documentation, examples FIRST, etc, wins the competition. - Competition tasks (e.g. an individual func) are weighted somehow. - The HaskellWiki has page histories, which can be used to make judgements in cases where a task has no clear winner. - Prices: a name on HaskellWiki Hall of the Fame page or something similar... If there is enough interes in this kind of activity, there is a need for a couple of volunteers to organize everything and to work as judges on the competition days (or weeks). They should decide, what the competition is about etc. What do you think? Pros & Cons? Would you take part in this kind of competition(s), if these were organized? Anybody interested in developing this idea further? I'll guess many people have their favorite missing libs that could be build this way in collaboration and so do I. br, Isto

4 10

library reorganisation
by Simon Marlow 04 Mar '06

04 Mar '06

This mailing list seems to be an appropriate place to discuss: http://cvs.haskell.org/trac/ghc/ticket/710 Rather than keep adding comments to the ticket, I'll continue the discussion here. I don't suggest changing the module name of Text.Html. Ross suggests moving it to the network package - I'm abivalent about that. A completely separate package (html) would be fine by me. In reply to maeder: yes the package boundaries do reflect implementation dependencies. I don't think this is a big problem. In theory we could rename /everything/ in base to be PackageBase.* and then re-export the actual interfaces from a bunch of separate packages, but that doesn't really buy much, and it's a lot of work. Having said that, I'm open to arguments for extracting Data.Array.* into a separate package. I almost suggested removing Text.Printf, but it seems too small to put in a package of its own and I don't know where else to put it :-) If we had a separate 'text' package it could go there, maybe with Text.PrettyPrint? Cheers, Simon

4 5

RFC: Collection Framework, reprise.
by Jean-Philippe Bernardy 03 Mar '06

03 Mar '06

Hello, I'm glad you see so many good point in my design. I must say however that the operator names are (c) Ross Paterson :) On 2/21/06, Robert Dockins <robdockins(a)fastmail.fm> wrote: > Well, I have to begin with the caveat that I am not a data structures > expert, and that the design of Edison is almost entirely due to Chris > Okasaki. That said, I can certainly share my opinion. In no > particular order: > -- Your use of two type parameters to model read-only or unobservable > collections is very interesting. I wonder, though, how useful it > actually is. I facilitates some interesting possibilities with > views, but I can't think of any compelling use cases. I sort of > dislike the fact that it can turn certain of the class methods > "useless", but maybe the idea just hasn't grown on me yet. The truth is, I hope this will become nicer when (if) we move to associated types. I need to play a bit more with Phrac to have a clearer idea though. > -- I like the idea of views generally, and I'm now trying to think if > there is a good way to work something like them into Edison. > -- The 'isSingleton' method seems unnecessary. Are singleton > collections interesting enough to supply a special test for them? This is based on Christan Maeder idea. We are planning to move to AVL trees for A. Hey, which do not provide a O(1) size function. A singleton test thus becomes valuable, and since costs next to nothing to add to the class I decided to to it. > -- Your 'lookup' method has a Monad context, which I assume is the > 'NotJustMaybe' pattern, but 'front' and 'back' return Maybe. You > should probably pick one style and stick to it. True. > -- Qualified infix functions look horrible. I know you say this > module should be imported unqualified, but with Prelude clashes > people qualify it anyway. I'd suggest you stick to regular prefix > functions for your class methods and define the infix functions as > the appropriate aliases. That way people importing qualified can > still use something reasonable looking. > -- In a related thread I've been discussing argument orders. I think > I've just about come to the decision that all the Edison API > functions will take the collection argument last, including the > troublesome 'rcons'. If you take my suggestion to remove infix > symbols from your classes, I suggest you also make your right cons > and index functions take the collection argument last. However, I'd > probably leave the symbols as is, so that, e.g., (|>) = (flip rcons). If i understand this correctly, you suggest that regular functions should have a prefix meaning, whereas operators should have infix meaning (also in the light of your answer to Ross). I remember some peope spoke against this when we tuned Data.Map (& friends) API some years ago. I guess the reason is that some functions cannot be assigned a clear enough operator (isSubsetOf, etc.) > -- In fact, I like your right and left insert symbols so much, I may > adopt them myself. > -- You claim that 'union' takes an unspecified element in the case of > duplicates, but you also claim it is commutative. You need to > specify in what sense you claim commutativity; your collection class > doesn't require an Eq or Ord instance, and the claim seems very > suspect if you mean up to identity. Similar with intersection. This has been written in a hurry, and I didn't mean anything very formal. We have re-hashed implied meanings of Eq and Ord quite a few times however, and the general idea is that we require Eq to mean equality, and similarly for Ord, otherwise all bets are off. This is better stated in a general comment rather than on the definition on union though. > -- Does 'adjust' affect all elements with the given key, or just a > single unspecified one? The class has the (implicit) assumption that a key cannot exist twice. The semantic could be generalized however. > -- 'Indexed' doesn't have any notion of bounds. That seems like a > pretty necessary concept. Humm, I see now that MapLike is a subclass > of Indexed. Perhaps then you should have 'DenseIndexed' or > 'ArrayLike' which has bounds related methods together with the > "denseness" property. It seems like the class you suggest to add would become a replacement for the Array class. > > Overall, I'd say the methods you have carved out seem to be the ones > that are most-used, with the notable exception of 'head' and 'tail' > for sequences. Rather, I intend to start with those. It seems easier to add than to remove. > If you are attempting to go for a fairly minimal set > of operations (that's more or less what I read your design goals as > saying), then the only method I'd consider adding is a strict fold. > People get irritated if they can't, e.g., sum the elements in a > collection without building a gajillion unnecessary closures. Every day I pray for a genius to come with the generic solution to eliminate unnecessary lazyness :) Thanks again for the helpful comments. JP.

11 17

darcs patch: make head/build rule apply to all types, not just Bool.
by John Meacham 03 Mar '06

03 Mar '06

Thu Mar 2 20:57:53 PST 2006 John Meacham <john(a)repetae.net> * make head/build rule apply to all types, not just Bool.

1 0

FunctorM
by Ross Paterson 02 Mar '06

02 Mar '06

I propose to deprecate Data.FunctorM in favour of Data.Traversable: http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-Traversabl…

3 4

conditional code, was: Template haskell instance checking
by Christian Maeder 02 Mar '06

02 Mar '06

heatsink wrote: > Is there a way, in template haskell, to find out what instance > declarations exist? I'm not trying to accomplish anything specific > right now, but I can see two potential uses for this. One is to emit > compile-time error messages from TH code which would be more informative > than the typechecker's output. The other is to produce TH functions > that conditionally generate code depending on the instances satisfied by > their arguments. Apologies for becoming off-topic now, I've got nothing against template haskell (TH), on the contrary, it is a great device to increase genericity. But I want to warn about conditional code, because this may become a nightmare to maintain. I.e. we (at Bremen) have (few) bits in TH that check if we run under windows or unix (but no one knows if the windows part is still working). Furthermore we support a few older (still recent) ghc versions with conditional code (like ghc itself can be bootstrapped with different older version). Plugging in various libraries using Cabal is a nice feature, but imagine if you would start to program depending on the currently installed packages (and visible instances)! (Fortunately, this would be hard to do currently.) So (despite cabal and the desire for a minimal kernel) I hope that ghc will continue to supply a large number of more or less "standard" packages or modules that can safely be expected to exist in (almost) every installation. (Therefore I've suggested to keep Data.Set and Data.Map in the base package, but another "standard" package may be fine, too). Otherwise truly application specific 3rd party cabal packages may all come with their own "Prelude extensions" rather than reusing increasingly solidified Haskell basics (that are hopefully not disputed too much by the design of Haskell-Prime). If you agree with me, great, ignore this posting. Respectfully Christian

1 0

Re: libraries in hugs/nhc
by Jean-Philippe Bernardy 01 Mar '06

01 Mar '06

Good, so I propose to create a separate package (collections?) where we'll put the AVL-tree based collection types, plus the code they are based on. I will do this next week, provided I have the rights to create a new package on darcs.haskell.org Later on Data.Set/Map/IntSet/IntMap shall be moved to that package. Cheers, JP. On 3/1/06, Simon Marlow <simonmar(a)microsoft.com> wrote: > On 28 February 2006 16:47, Adrian Hey wrote: > > > On Tuesday 28 Feb 2006 9:46 am, Jean-Philippe Bernardy wrote: > >> On 2/27/06, Simon Marlow <simonmar(a)microsoft.com> wrote: > >>> I didn't see the start of this discussion, but I'd question whether > >>> AVL should go into the base package. What's the goal here? > >> > >> See my other reply to Ross. Text quoted below. > >> > >> A (better) alternative is of course to put this in its own package. > >> This is in line with the "decentralisation" idea indeed. I even say > >> we should put the existing Data.Map/Set; etc. into that package; so > >> "base" become lighter. > > > > To be honest it's never been too clear to me what the long term > > plans are for library distribution and the base package. > > As far as possible I think we should extract non-essential code from the > base package. The main constraint on base is that it must contain > enough to be able to implement the Prelude. There's a lot in there that > doesn't fit that criteria. If Prelude gets smaller in Haskell', then > base can be reduced even further (splitting out the I/O library, > perhaps). > > The minimum we can ship GHC with is those libraries required to > bootstrap GHC itself (any less would cause undue difficulties, I think). > This set is currently: base, haskell98, template-haskell, unix, Cabal, > readline. > > Ideally it should be configurable which packages are included in a GHC > build, so that systems with a good package manager (Debian, Gentoo, > FreeBSD etc.) can provide a minimal GHC and deliver further (Haskell) > packages as separate OS-managed packages. For some distributions, such > as the plain binary distribution, we will probably want to ship GHC with > a larger set of libraries by default. > > It has been at the back of my mind to think about this reorg at some > point. The main technical hurdle is that we really need to build the > libraries with Cabal, and that needs some extra support in Cabal. >

1 0