November 2002 - Haskell

Enum on Float/Double
by George Russell 23 Oct '03

23 Oct '03

The situation with Enum on Ratio is pretty bad but at least it's not hopeless, since rational numbers are at least exact. But for Float/Double it seems to be a total disaster area. Since it seems to be impossible to abolish Enum Float/Double altogether, would it at least be possible to make it rather more useful, by making succ x return the next representable float after x (or x if x is non-finite) and pred x the previous representable float. This would (a) be useful; (b) make mathematical sense; (c) is tricky to implement with the existing primitives. Before someone else points it out, this is of course unimplementable should someone in the future implement infinite-precision reals in Haskell, but as (barring a solution to the halting problem) Eq would be as well, that does not bother me. My preference would be for succ (+-0) to return the smallest positive real, since then you could define succ x to be the unique y with x < y and forall z . z < y => not (x < z), where such a y exists, and I'm not sure if the Haskell standard knows about signed zeros. Feri wrote > Everybody working with floats should know their quirks While in an ideal world, everyone who represented a mouse position or anything else as a float should have a PhD in numerical analysis, in practice they do not. Indeed I think the Haskell Library Report contains quite a few examples of floating point code which a numerical analyst would have written rather better. So I don't think it's good enough to treat every Float/Double operation as if it had an implicit "UNSAFE" flag indicating that the compiler was entitled to wierd behaviour only comprehensible to experts, as seems to be the case with floating enumerations now.

8 11

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

diff in Haskell: clarification
by George Russell 16 Dec '02

16 Dec '02

Since various people seem to have misunderstood the problem, I shall try to state it more precisely. What is required is a function diff :: Ord a -> [a] -> [a] -> [DiffElement a] for the type data DiffElement a = InBoth a | InFirst a | InSecond a such that given the functions f1 (InBoth a) = Just a f1 (InFirst a) = Just a f1 (InSecond a) = Nothing and f2 (InBoth a) = Just a f2 (InFirst a) = Nothing f2 (InSecond a) = Just a the following identities hold: mapPartial f1 (diff l1 l2) == l1 and mapPartial f2 (diff l1 l2) == l2 This is a well-known problem. The most helpful Web page I could find about it is here: http://apinkin.net/space/DifferenceEngine There is an algorithm known as Myer's algorithm, but obviously I want it in Haskell rather than C, and it would be nice if someone else had written it so I don't have to.

4 4

Re: arrows
by Ashley Yakeley 06 Dec '02

06 Dec '02

At 2002-06-29 14:43, Wolfgang Jeltsch wrote: >To simplify things a bit, let's take a simpler Parser type which doesn't >use monad state transformers but simple state transformers instead. This >makes the type ParserState simpler. You can think of a parser state as >an infinite list of substate-token pairs now. The tokens denote the >input stream. The substates may be used to encapsulate parser states of >a subordinate parsing process. When a token is read, the corresponding >token-substate pair is discarded. Sounds very complicated. Wouldn't a simple stream transformer work? newtype MyParser baseMonad token output = MkMyParser (baseMonad token -> baseMonad output); > (>>=): sequencing of parsers > return: returning values > fail: generation of always failing parsers > mzero: always failing parser > mplus: parsing using alternative parsers > fmap: applying a function to the result of a parser > (>>>): providing high-level tokens and parsing using these tokens > identity: reading a single token > pure: reading a single token and applying a function to it I think I can do all of those for MyParser. There's a one-token look-ahead variant: newtype MyLookaheadParser m t a = MkMyLookaheadParser (m t -> Maybe t -> m (Maybe t,a)); >(I don't allow >finite lists here to make some things a bit easier an more elegant. You >can easily produce an infinite list from a finite one by applying >something like (++ repeat Nothing) . map Just to the finite list.) Wouldn't it be easier to allow finite token lists and have reading past the last token be the same as mzero? -- Ashley Yakeley, Seattle WA

2 1

AW: slide: useful function?
by Markus.Schnell＠infineon.com 03 Dec '02

03 Dec '02

Thanks for the comments. It seems the function is not really needed (at least not predefined), although I use it fairly often. > Read more in > > T Uustalu, V Vene. The dual of substitution is redecoration. > In K Hammond, S Curtis, eds, Trends in Functional Programming > 3, pp 99-110. Intellect, > Bristol / Portland, OR, 2002. - .ps.gz, 46K (© Intellect) > > http://www.cs.ioc.ee/~tarmo/papers/sfp01-book.ps.gz , > > if you want to be bothered with categorical nonsence ;-) There's too much mathematics in it, I'm only an engineer... ;-) Thanks, Markus -- Markus Schnell, Infineon Technologies AG

14 21

The Haskell 98 Report
by Simon Peyton-Jones 01 Dec '02

01 Dec '02

Folks, As you know, Cambridge University Press are doing us the huge service of publishing the Haskell 98 report, both as a special issue of the Journal of Functional Programming (Jan 2003) and as a hardback book (it'll cost around £35). I'm very, very, very happy to say that, following discussion with CUP, the copyright and reproduction arrangements for the report will remain unchanged; i.e. exactly as they are at: http://research.microsoft.com/~simonpj/haskell98-revised/haskell98-report-h… I'm signing a letter that grants CUP a *non-exclusive* license to publish the Report, but it places no limitations on what else may be done with it. The copyright will still be (c) Simon Peyton Jones (as it has for some while; it has to be attached to someone or some thing), and the existing notice that says "you can do what you like with this Report" will stay unchanged. No "non-commercial only" caveats. In my view this is extremely generous of CUP, and I am particularly grateful to Conrad Guettler for making it happen. As a thank-you to CUP, perhaps you can all go out and buy a copy! Simon

4 3

Re: Running out of memory in a simple monad
by Zdenek Dvorak 29 Nov '02

29 Nov '02

Hello, I hope I understand what's going on; if not please someone correct me. >I have problems with monads and memory. I have a monad through which >I thread output. If I do the concatenation of the output-strings in >one way Hugs runs out of memory, but if I do it in another way >everything works. I can't see why the first way doesn't work but the >second is OK. I woudl appreciate if someone could tell me what I am >doing wrong. > Here is the non-working monad: -} The problem is not directly connected to monads; what is the problem: [] ++ x = x (h:t) ++ x = h : (t++x), i.e. time complexity of ++ is proportional to the length of first list. first way: >putCharM c = M $ \o -> ((), o ++ [c]) -- Is this stupid in some way? this takes list (looong) of everything produced before this putCharM and concatenates c as last member; this takes time linear in the length of the list, summing over all putCharMs it is quadratic (and of course, due to laziness a lot of memory is consumed; seq does not help, as it only evaluates first cell of the list so that it sees it is not empty; deepSeq would solve this, but the time consumption would still stay long). the second way: > M f >>= k = M $ > let (x, o) = f > M f2 = k x > (x', o') = f2 > in (x', o ++ o') this is done reverse way (because >>= is bracketed to the right); we concatenate output of f (short) with output of f2 (the rest of computation, i.e. looong); but the time is proportional to the length of first list, so it is constant in our case; summing it over all putCharMs, we get linear time and we are happy :-) If you want to do it the first way, define putCharM c = M $ \o -> ((), c : o) and then reverse the list in runM. Zdenek Dvorak _________________________________________________________________ Add photos to your messages with MSN 8. Get 2 months FREE*. http://join.msn.com/?page=features/featuredemail

2 1

ANNOUNCE: HaXml-1.08
by Malcolm Wallace 29 Nov '02

29 Nov '02

HaXml-1.08 ---------- http://www.haskell.org/HaXml/ We announce a fresh release of HaXml, a collection of libraries and tools for using XML from Haskell. This is mainly a bug-fix release. What is new in 1.08? * A new and highly useful function, Text.XML.HaXml.Validate.partialValidate, does validation except for checking whether the root element type matches that of the DTD's root element. This is just what you need in order to validate any partial document or sub-document. * The function Text.XML.HaXml.Html.Generate.htmlprint had a little bug which caused it to loop infinitely if some text was longer than 60 characters without a space. * The Xtract parser and combinators are now included in the HaXml library package, rather than existing solely for the Xtract command-line tool. * HaXml now works nicely with ghc-5.04.x as well as ghc-5.02.x and nhc98. Regards, Malcolm

1 0

Re: nub
by Jan-Willem Maessen 29 Nov '02

29 Nov '02

I find that nub is nearly always the wrong tool for the job (unless the job is trivial quickie coding). I'll point out that: > map head . group . sort has O(n lg n) asymptotic complexity, whereas nub or (sort . nub) both are O(n^2). This fact seems all too frequently forgotten. For short lists it doesn't matter much---but I find I like to use set union a lot, and "merge" is quite a bit better than List.union for this, so I tend to keep even short sets sorted. (For bigger sets, of course, one should import a nice set implementation.) Richard Braakman <dark(a)xs4all.nl> writes: > uniq = map head . group and later: > I think both functions are useful. If I understand it right, uniq > can evaluate its argument list lazily, while nub cannot. There's no > real need to put uniq in the standard library, though. Here's a little experiment for folks with big Haskell programs: Look for uses of "group" in your code. I suggest: find -name '*.hs' | xargs grep -n '[^a-zA-Z]group[^a-zA-Z]' Now, look at two divisions of these calls: 1) What proportion are *not* performed in conjunction with a call to sort? 2) What proportion are *not* preceded by "map head"? In the case of the Eager Haskell compiler, the answer to (1) was "none", and the answer to (2) was "several". I suspect I'm not uniq in this finding. Providing "uniq" and/or "uniqSort" as prelude functions could in fact be a great service. Of course, if I only got to add one function to List, it would be some variant of "merge". -Jan-Willem Maessen

1 0