May 2002 - Haskell - Haskell.org

tuple component functions
by trb＠eastpac.com.au 03 Jan '03

03 Jan '03

S.D.Mechveliani writes: > As Haskell has the standard functions fst, snd to decompose (a,b), > maybe, it worths to provide also > tuple31, tuple31, tuple31, > ... > tuple51, tuple52, tuple53, tuple54, tuple55 > > for the tuples of n = 3,4,5 ? I've found some of these useful, except I named them differently: > fst3 :: (a,b,c) -> a > fst3 (x,_,_) = x > snd3 :: (a,b,c) -> b > snd3 (_,x,_) = x > thd3 :: (a,b,c) -> c > thd3 (_,_,x) = x .... never got around to quadruples etc. I also defined (some of these may be untested): > tripl :: a -> (a,a,a) > tripl x = (x,x,x) > curry3 :: ((a, b, c) -> d) -> a -> b -> c -> d > curry3 f x y z = f (x, y, z) > uncurry3 :: (a -> b -> c -> d) -> ((a, b, c) -> d) > uncurry3 f t = f (fst3 t) (snd3 t) (thd3 t) > applyTriple :: (a -> b, a -> c, a -> d) -> a -> (b,c,d) > applyTriple (f,g,h) x = (f x, g x, h x) > cross3 :: (a -> b, c -> d, e -> f) -> (a,c,e) -> (b,d,f) > cross3 (f,g,h) (x,y,z) = (f x, g y, h z) > mapTriple :: (a -> b) -> (a, a, a) -> (b, b, b) > mapTriple = cross3 . tripl > applyFst3 :: (a -> b) -> (a, c, d) -> (b, c, d) > applyFst3 f = applyTriple (f . fst3, snd3, thd3) > applySnd3 :: (a -> b) -> (c, a, d) -> (c, b, d) > applySnd3 f = applyTriple (fst3, f . snd3, thd3) > applyThd3 :: (a -> b) -> (c, d, a) -> (c, d, b) > applyThd3 f = applyTriple (fst3, snd3, f . thd3) > applyArgs3 :: (a -> b) -> (c -> d) -> (e -> f) -> (b -> d -> f -> g) -> (a -> c -> e -> g) > applyArgs3 af1 af2 af3 f = \x y z -> f (af1 x) (af2 y) (af3 z) > rotl :: (a -> b -> c -> d) -> (b -> c -> a -> d) > rotl f y z x = f x y z > rotr :: (a -> b -> c -> d) -> (c -> a -> b -> d) > rotr f z x y = f x y z > rotl4 :: (a -> b -> c -> d -> e) -> (b -> c -> d -> a -> e) > rotl4 f y z t x = f x y z t > rotr4 :: (a -> b -> c -> d -> e) -> (d -> a -> b -> c -> e) > rotr4 f t x y z = f x y z t Some more combinators (only for pairs so far): > twin :: a -> (a,a) > twin x = (x,x) > swap :: (a,b) -> (b,a) > swap (x,y) = (y,x) -- apply a pair of functions to one argument > applyPair :: (a -> b, a -> c) -> a -> (b, c) > applyPair (f, g) x = (f x, g x) -- apply a pair of functions to a pair > cross :: (a -> b, c -> d) -> (a, c) -> (b, d) > cross (f, g) = applyPair (f . fst, g . snd) -- compose a pair of functions onto one function > dotPair :: (a -> b, a -> c) -> (d -> a) -> (d -> b, d -> c) > dotPair (f, g) h = (f . h, g . h) -- compose a pair of functions onto a pair of functions > dotCross :: (a -> b, c -> d) -> (e -> a, f -> c) -> (e -> b, f -> d) > dotCross (f, g) (h, i) = (f . h, g . i) > mapPair :: (a -> b) -> (a, a) -> (b, b) > mapPair = cross . twin > applyFst :: (a -> b) -> (a, c) -> (b, c) > applyFst f = applyPair (f . fst, snd) > applySnd :: (a -> b) -> (c, a) -> (c, b) > applySnd f = applyPair (fst, f . snd) > applyArgs :: (a -> b) -> (c -> d) -> (b -> d -> e) -> (a -> c -> e) > applyArgs af1 af2 f = \x y -> f (af1 x) (af2 y) > betweenFst :: (a -> b -> c) -> (a, d) -> (b, e) -> c > betweenFst = applyArgs fst fst > betweenSnd :: (a -> b -> c) -> (d, a) -> (e, b) -> c > betweenSnd = applyArgs snd snd I find these combinators useful, and probably other people have their own versions - it would be nice to get them standardised, so we all speak the same language. By standardised, I mean a prominent version that will be adopted by users, not necessarily a committee process. Tim

3 2

ICFP programming contest
by trb＠eastpac.com.au 03 Jan '03

03 Jan '03

Michael Hobbs writes: > Just took a look at the results for the ICFP contest. Am I correct in > assuming that "LA" stands for Lennart Augustsson and that "Si^3" stands > for Simon Marlow, Simon Peyton-Jones, Sigbjorn Finne? Is there a URL for the results ? Tim

2 1

reverse function application
by Hal Daume III 12 Jun '02

12 Jun '02

i have a function: (*==) :: B -> (C -> IO a) -> IO a basically, it takes b, does something to it to make c, performs the action on c and returns the value. the Bs are basically Doubles, so we'll consider them as such for now. suppose I want to string together a bunch of these things...i can write: 5 *== \x -> 6 *== \y -> somefunctiononxandy x y but i'd really like to be able to write: 5 *== 6 *== somefunctiononxandy or, secondarily 5 *== (6 *== somefunctiononxandy) but i can't seem to get this to work and my brain is beginning to hurt. i suppose this is basically the same as wanting to write something like: action1 >>= action2 >>= somefunction instead of action1 >>= \x -> action2 >>= \y -> somefunction x y so if it can be done for >>=, i can make it to work. any advice? - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

2 1

Type extensions
by Ronald Legere 04 Jun '02

04 Jun '02

Greetings. I have decided to try and understand the type system of haskell with extensions. As far as I can tell, the following set of extensions has been included, for example in ghc: multiparameter type classes constructor classes existential types explicit universal quantification scoped type signatures funtional dep?? Etc There is probably some overlap, and probably missed a few, as i do not understand what all these things do! ! My question: How do you get started learning all this? which of these is the most important? Is there a paper out there that explains most or all of these extensions and why you would want them and HOW the heck they work together? Ron Legere __________________________________________________ Do You Yahoo!? Yahoo! Greetings - send holiday greetings for Easter, Passover http://greetings.yahoo.com/

2 2

Re: arrows
by Ashley Yakeley 03 Jun '02

03 Jun '02

At 2002-05-25 01:32, Koen Claessen wrote: >Might I remind you that an arrow (as defined in category >theory) only requires identy and composition to be defined >and satisfying some laws? > >In particular, an arrow does not have to have the operations >"arr" and "first". Well either "arrow" is being used in two different senses or the "Arrow" class should be renamed. If you can't define "arr" and "first", it may be an arrow but it's not an Arrow. -- Ashley Yakeley, Seattle WA

2 1

Re: arrows
by Ashley Yakeley 03 Jun '02

03 Jun '02

At 2002-05-24 13:40, Wolfgang Jeltsch wrote: >Now, I have a type which would fit wonderfully into the Arrow concept if >arrows wouldn't be expected to have a first operator. ...then it's not an Arrow. It sounds like it might be one of these, however: class Compositor comp where { identity :: comp a a; compose :: comp b c -> comp a b -> comp a c; }; I'm not sure if 'Compositor' is a good name for it, or what. >Parser arrow. And there is also a meaningful definition for pure (arr). >pure f just has to be a parser which reads exactly one token, applies f >to it and outputs the resulting value. >The problem is that there seems to be no appropriate definition for >first. That's why, in my opinion, it would be very good to have only the Can't you have a parser that reads in one token tuple, and apply another parser to the first part of it only? Otherwise, perhaps you could have classes like this: class (Compositor arrow) => Semiarrow arrow where { arr :: (p -> q) -> arrow p q; }; class (Semiarrow arrow) => Arrow arrow where { arrFirst :: arrow p q -> arrow (p,r) (q,r); }; -- Ashley Yakeley, Seattle WA

5 4

RE: [Fwd: F#]
by Don Syme 03 Jun '02

03 Jun '02

Hi Manuel, One point is that in the absence of extensive purity annotations to imperative libraries you will need to use monads for operations that shouldn't need them. Having to add the annotations certainly counts as a complication in comparison to what many other languages have to do on .NET. As for monads, this is hardly the place to go into an argument about their relative merits re. all those slightly more widespread approaches to imperative programming. If you think driving imperative libraries using monads will be so great then a Haskell.NET would certainly be a perfect place to try out that theory. Don -----Original Message----- From: Manuel M. T. Chakravarty [mailto:chak@cse.unsw.edu.au] Sent: Fri 31.05.2002 03:27 To: Don Syme Cc: tweed(a)cs.bris.ac.uk; paul.hudak(a)yale.edu; haskell(a)haskell.org Subject: RE: [Fwd: F#] "Don Syme" <dsyme(a)microsoft.com> wrote, > And getting top-notch performance is obviously always a huge challenge > for Haskell, and you can't play some common implementation tricks when > compiling to IL. But the only truly serious complications added by .NET > itself are (a) the general problem of Haskell interop with imperative > libraries, requiring you to reach for monads quite often (or to wrap the > libraries yourself) [..] > IMHO problem (a) will always be the thing that stops Haskell becoming > very very big. But then being non-imperative it's also its main selling > point... So, you are saying that Haskell's problem with .NET is that it is not imperative, but at the same time you don't want to resort to Haskell's imperative sublanguage (the IO monad). I don't quite understand this. Personally, I find[1] Haskell to be very pleasant for imperative programming. In fact, I agree with SPJ, who wrote[2] (slightly provocatively), Haskell is the world's finest imperative programming language. Cheers, Manuel [1] After having written piles of low-level imperative code in Haskell. [2] In ``Tackling the Awkward Squad''

3 2

Lists representations (was: What does FP do well? (was ...))
by C.Reinke 01 Jun '02

01 Jun '02

Long away and far ago (or something like that;), there was a discussion on Lists implemented as arrays rather than linked structures, during which Jerzy Karczmarczuk commented: > What bothers me quite strongly is the algorithmic side of operations > upon such objects. > > Typical iterations map- (or zip-) style: do something with the head, pass > recursively to the tail, would demand "intelligent" arrays, with the indexing > header detached from the bulk data itself. The "consumed" part could not be > garbage collected. In a lazy language this might possibly produce a considerable > amount of rubbish which otherwise would be destroyed quite fast. The > concatenation of (parts of) such lists might also have very bad behaviour. > > Can you calm my anxiety? > > Jerzy Karczmarczuk The reason I wanted to reply is that I can offer one data point on this. An even longer time ago, there were the various reduction systems developed in Kiel, implementing the Kiel Reduction Language KiR, a variant of Berkling's reduction languages (the Berkling pointed to in Backus' Turing Award Lecture). KiR lacked lots of useful features Haskell has, and Haskell's implementations still lack lots of useful features KiR's had. I dearly miss those features, but that is not the topic here (I don't know whether any of the systems still install or even run, but see the Manual at http://www.informatik.uni-kiel.de/~base/ for more info). The topic here was list representations. KiR's implementations moved from interpreted graph-reduction over compiled graph-reduction with a code interpreter to compiled graph-reduction with compilation via C, all more or less with the same high-level front end. All of these represented lists as vectors (KiR was dynamically and implicitly typed, btw), and the memory was divided into an area for fixed-size descriptors pointing to each other or into the second area, the heap, for variable-sized data blocks. The descriptor area was reference-counted and simply reused free space (most KiR variants were call-by-value), the other area needed memory compactification when space grew fragmented. A list's elements (or pointers to their descriptors) went into a contiguous block in the heap, and the descriptors made it possible to share subsequences of elements between different lists (descriptors were large enough to hold a pointer to the start of the sequence and its length). Quite as Jerzy suspected. Supported operations included both array and list operations, append required the allocation of a new heap block and copying of *both* lists, but was provided as a primitive (the standard approach for systems that started out as interpreters: a good mix of efficient primitives and interpreted user defined constructs). As others have pointed out, this looks rather inefficient, especially for longer lists, so when we set out to make measurements for a JFP paper [1], comparing with the likes of ghc, we expected to be beaten, but hoped to be not too far away, at least with the latest via-C implementation.. Benchmarks are always difficult, but especially so between so different languages: in KiR, we could easily and correctly execute programs that in Haskell, either wouldn't even compile, or wouldn't terminate, or wouldn't show any result (with similar problems the other way round). And after adapting to the common subset of algorithms, a translation to Haskell might mean that a complex program execution might return immediately, as the compiler and runtime system lazily determined that none of it was needed for the program output (compiled Haskell programs report almost no reduction results, only explicit program output, or show-able results). With all these preliminaries and caveats, and the standard disclaimer that all benchmarks are useless, but interesting, the relevant benchmark is the infamous "pretty quicksort" for some 4000 elements (qusort in the paper - lots of finite lists, traversals, fragments and appends, just like the typical Haskell program written without any concern for efficiency; Haskell programs concerned with efficiency tend to look rather different). To our astonishment, even the code interpreting implementation (which should otherwise be in the ballpark of Hugs) outperformed ghc, hbc, and Clean on this example (call-by-value also played a role: compiled sml was in the same area as compiled KiR, but both only slightly faster than code-interpreted KiR, so data representation and primitives seemed to play the main role). This prompted us to include Augustsson's sanitized variant of quicksort (qusortbin in the paper - from the hbc libs) as well, which gave the results everyone expected (it substantially modifies the algorithm to a profile better supported by the current list representation, e.g., no appends). [and before anyone accuses me of advocating functional quicksort: the naive quicksort is useless, and even the real one isn't the best choice in many cases;-] But the moral for the current discussion: a more intelligent list representation could have substantially more benefits for the average Haskell program than any compiler optimization twiddling, and I'd really like to see someone (PhD student?) investigating that topic seriously, as the answers are unlikely to be obvious. The representation chosen in the reduction systems could be a first hint, but as Jerzy points out, things may be more complicated in the context of Haskell. For comparison, Haskell array performance was somewhere between non-existent and terrible in those days (another clear win for both the compiled and the interpreted reduction systems) and has only recently improved somewhat. That needs to continue and, please, someone do the same for lists! Just my old 2 Pfennige (former currency;-), Claus [1] D. Gaertner, W. Kluge: pi-RED+: An Interactive Compiling Graph Reduction System for an Applied Lambda-Calculus Journal of Functional Programming, 6 (5), 1996.

3 2

Re: readFloat
by Wolfgang Jeltsch 31 May '02

31 May '02

On Tuesday, 2002-05-28, 18:57, CEST Simon Peyton-Jones wrote: > Folks > > I'm back to tidying up the Haskell Report. > > In the Numeric library, there is the useful function > > readFloat :: RealFloat a => ReadS a > > But you can't use it for reading rationals, because Rational > isn't in RealFloat! > > This is a Royal Pain, and entirely unnecessary. In fact, > readFloat uses only operations from the RealFrac class, > so it could equally well have type > > readFloat :: RealFrac a => ReadS a > > I'm strongly inclined to make this change. It breaks no > programs, and it fixes a real bug i.e. there is no way to > read a "103" as a Rational. > > Simon It would be strange to name a function readFloat if its type is RealFrac a => ReadS a. I think the function should be named readFrac. For compatibility, one could put the following into the prelude: readFloat :: RealFloat a => ReadS a readFloat = readFrac And one could mark readFloat as depricated and maybe remove it in some future version of Haskell. Ciao, Wolfgang

3 2

RE: [Fwd: F#]
by Don Syme 31 May '02

31 May '02

> GHC supports concurrency, exceptions, weak pointers, foreign calls, > etc, etc. All these need to be mapped onto .NET. ... GHC comes > with a large collection of libraries of its own. These need to be > still available in the .NET version. I don't really agree with these points. If someone tried to support all of this they'd be unlikely to appear out the other end of the swamp. Having actually tried both ways myself, I'd suggest that GHC is simply not the right starting point for a Haskell.NET compiler. Much better to start a fresh compiler, essentially from scratch, with a suitable selection of optimizations, language extensions, library features and interop extensions given the platform and kind of programming you're aiming to support. If you look at history successful compiler projects do not tend to some out of attempts to graft large code bases for alternative purposes (unless you've got loads of resources to throw at the problem). Cheers, Don -----Original Message----- From: Simon Peyton-Jones [mailto:simonpj@microsoft.com] Sent: 31 May 2002 15:31 To: Don Syme; D. Tweed Cc: Paul Hudak; haskell Subject: RE: [Fwd: F#] | Idle curiosity: which aspects of the Haskell language are the | ones that make it complicated -- e.g., long-time stuff like | lazy evaluation, typeclasses & inferrence, etc or newer stuff | like functional dependencies, etc or something else entirely | -- and do they only make it complicated in the context of the | .NET architecture or in any implementation? General remarks about targetting .NET from GHC. * There is no reason in principle why one can't write a back end for GHC to generate .NET IL. * Generating *verifiable* IL is noticeably harder: you have to take much more care; to deal with parametric polymorphism you need Generic IL, which isn't "out" yet; and even then, higher kinded type variables are a serious problem. Being verifiable almost certainly requires some runtime checked type casts, which hurt performance -- and reducing them to a minimum complicates the compiler. * My conclusion: best plan is to generate unverifiable IL, and run it unverified. Situation is then just like an existing code generator: you have to trust the compiler. But it's fast and it's much simpler. * The resulting code will still run quite a bit slower than GHC-complied code. So why would anyone want to use it? Presumably, to get access to the .NET libraries. So that has to be very convenient. Tools are needed to read .NET library meta-data and generate impedence matching glue to make them easily callable from Haskell. Haskell needs some new 'foreign import' stuff to make it easy to call the libraries. There's a big design space here about how much to extend Haskell to make calling .NET convenient. * GHC supports concurrency, exceptions, weak pointers, foreign calls, etc, etc. All these need to be mapped onto .NET. Some might not fit well; for example, Concurrent Haskell assumes extremely lightweight concurrency, whereas .NET threads are OS threads; and asynchronous exceptions might be tricky too. * GHC comes with a large collection of libraries of its own. These need to be still available in the .NET version, so the .NET implementation of GHC needs to be pretty fully-featured (because the libraries use a lot of features). What all this means is that GHC.NET is a lot more than just a code generator. That is, I think, what Don meant when he said that GHC is complicated. (In our defence, it is the very fact that GHC is a rich system that makes it useful. Its complexity is not gratuitous.) Part of my reason for writing this is to encourage anyone out there to take up the challenge. There's nothing too difficult -- it's "just work". Simon and I don't have immediate plans to do anything about this, but we'd be delighted if someone else did. Congratulations to Sigbjorn to doing a great job with Hugs. Simon _______________________________________________ Haskell mailing list Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell

1 0