January 2002 - Haskell-Cafe

Re: monad parsing article....
by David Feuer 23 Jan '02

23 Jan '02

> Also, why were monad comprehensions > removed from Haskell? Was it for efficiency? > > No, it was to help beginners. When list comprehensions, and other list > operators like ++ and filter were overloaded, then errors involving the > class > system became much more common, and in particular cropped up for simple > list I now understand the problem. However, I'm not sure that the solution is the right one. I think that it makes more sense to change the way that Haskell deals with the Prelude. I think the way this issue is handled in DrScheme (www.plt-scheme.org) is pretty reasonable. There are a number of different "language levels" available. In the beginner's mode, complex operations are prohibited, and (I think) some operations have restricted semantics. It would seem to make sense for Haskell implementations to provide something similar: a prelude customized for beginners would have no overloaded functions, a prelude for experts would have many of them. Special syntactic forms like comprehensions and do notation can be specialized to the language mode. Examples for beginner's mode: monad comprehensions become list comprehensions do notation is restricted to IO numbers are not overloaded: 4,5,6::Integer and 4.0,5.0,6.0::Float This kind of multi-level system would allow beginner's an easy introduction without forcing people who know what they're doing to remember bizarre names for simple overloaded operators. David Feuer

1 0

Re: [Fwd: Re: type class VS struct/functor]
by John Hughes 23 Jan '02

23 Jan '02

The advantage of functors shows up when you need to have multiple implementations of a module for a type. For instance, suppose you want to implement a set, and you write the functors (OCaml below): ... Now, suppose you want two kinds of sets of string, one of which is case-sensitive and one of which is not. You can easily do this with functors like so module SensitiveCase = struct type t = string let eq s s' = (s = s') end module InsensitiveCase = struct type t = string let eq s s' = (String.lowercase s) = (String.lowercase s') end module SensitiveSet = Set(SensitiveCase) module InsensitiveSet = Set(InsensitiveCase) Each of these Set types takes a string, but the membership test is different. This is an annoying case in Haskell, because you can make a String a member of the Eq typeclass in only one way. Of course, you can always define newtype CaseInsensitiveString = CaseInsensitive String whereupon you can define an Eq instance that ignores case. Maybe this isn't common Haskell style, but it does have many advantages. In particular, the type-checker now checks that you don't pass a case sensitive string where an insensitive one is expected, or vice versa, and this should help catch bugs. I've begun to use this style more, particularly when using QuickCheck. There I define a new type when I want a different distribution of test data from the default. I've found it's error-prone to specify which distribution to use explicitly; much better to let the type-checker figure it out. John

1 0

Re: monad parsing article....
by John Hughes 23 Jan '02

23 Jan '02

Also, why were monad comprehensions removed from Haskell? Was it for efficiency? No, it was to help beginners. When list comprehensions, and other list operators like ++ and filter were overloaded, then errors involving the class system became much more common, and in particular cropped up for simple list processing functions. These are exactly the kinds of functions that beginning Haskell programmers write, and error messages involving class Monad are unlikely to help them! We decided consciously to keep the types of list functions simple, so that learners aren't forced to face the complexity of the class system from the word go. Overloading comprehensions is nice for experts, but even experts were beginners once! It's important that learning Haskell is not too difficult, otherwise there will eventually be no experts. Hence the decision. John Hughes

1 0

monad parsing article....
by David Feuer 23 Jan '02

23 Jan '02

In "Monadic Parser Combinators" (1996) by Graham Hutton and Erik Meijer, the authors state that "Some prior exposure to functional programming would be helpful in reading this article, but special features of Gofer (Jones, 1995b) --- our implementation language --- are explained as they are used. Any other lazy functional language that supports (multi-parameter) constructor classes and the use of monad comprehension notation would do equally well. ...." I am curious: was there any other language at the time supporting all of these features, or was this a joke? Also, why were monad comprehensions removed from Haskell? Was it for efficiency? -- /Times-Bold 40 selectfont/n{moveto}def/m{gsave true charpath clip 72 400 n 300 -4 1{dup 160 300 3 -1 roll 0 360 arc 300 div 1 1 sethsbcolor fill}for grestore 0 -60 rmoveto}def 72 500 n(This message has been)m (brought to you by the)m(letter alpha and the number pi.)m(David Feuer) m(David_Feuer(a)brown.edu)m showpage

3 2

Re: mzero
by Marcin 'Qrczak' Kowalczyk 23 Jan '02

23 Jan '02

Fri, 18 Jan 2002 05:18:07 -0500, Feuer <feuer(a)his.com> pisze: > Why is mzero in MonadPlus rather than a separate MonadZero class? It used to be in MonadZero. In Haskell98 these two classes were merged into one. I guess it was to simplify the library and programs using these classes: they are usually defined together and used together. Can you give an example of a useful MonadZero instance without MonadPlus which would be used by some function working on an arbitrary MonadZero? -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ QRCZAK

1 0

memoization hints
by David Feuer 23 Jan '02

23 Jan '02

(sorry I can't reply directly, but my mail situation is a bit messed up) Simon Marlow said: ----------- > Take a standard sort of example: > fib n =3D let > f =3D 0:1:zipWith (+) f (tail f) > in > f !! n > -- code that first calculates fib 1000, then fib 3, fib 4, then does > some other stuff >=20 >=20 > I believe that the entire list will be maintained (when compiled with > ghc -O) after calculating fib 1000, despite the fact that it=20 > will never > be used again. GHC will retain the list only if it determines that it might still be required, in other words if fib might be called again. If fib will never be called again, then the chances are that the list will be garbage collected. (I'm being intentionally imprecise, because of course the compiler can't in general determine accurately whether fib will or will not be called again).=20 If you don't want the list to be retained at all, you can use the -fno-full-laziness flag to GHC. Unfortunately there's no way to do this at the level of a single binding. Cheers, Simon ----------------- What I was talking about was whether it would be possible/practical to extend the language to allow this control at the single-binding level. This kind of control seems useful even without full laziness, but with full laziness it becomes essential--it is no longer possible to hide something in a function to prevent it from being persistent, and as all here know, it is often much better to compute values of a list over and over than to store the whole list in memory. This seems to require some weird form of garbage collection, where an accessible object which may be used again is collected. It is necessary, however, to ensure that enough information is retained to be able to reconstruct the value when necessary. I don't know nearly enough about GC to say what this might involve, but I'd be interested to hear what other people think about this problem, this (vague) solution, and perhaps other solutions. -- /Times-Bold 40 selectfont/n{moveto}def/m{gsave true charpath clip 72 400 n 300 -4 1{dup 160 300 3 -1 roll 0 360 arc 300 div 1 1 sethsbcolor fill}for grestore 0 -60 rmoveto}def 72 500 n(This message has been)m (brought to you by the)m(letter alpha and the number pi.)m(David Feuer) m(David_Feuer(a)brown.edu)m showpage

1 0

RE: memoization hints?
by Simon Marlow 22 Jan '02

22 Jan '02

> Take a standard sort of example: > fib n = let > f = 0:1:zipWith (+) f (tail f) > in > f !! n > -- code that first calculates fib 1000, then fib 3, fib 4, then does > some other stuff > > > I believe that the entire list will be maintained (when compiled with > ghc -O) after calculating fib 1000, despite the fact that it > will never > be used again. GHC will retain the list only if it determines that it might still be required, in other words if fib might be called again. If fib will never be called again, then the chances are that the list will be garbage collected. (I'm being intentionally imprecise, because of course the compiler can't in general determine accurately whether fib will or will not be called again). If you don't want the list to be retained at all, you can use the -fno-full-laziness flag to GHC. Unfortunately there's no way to do this at the level of a single binding. Cheers, Simon

1 0

RE: Programming style question
by Simon Marlow 22 Jan '02

22 Jan '02

> Ah, now I see the issue seems to be closeley related to > full lazy lambda lifting. Given.. > f = \x -> <blah> x > where <blah> has no free occurences of x, then I > thought the compiler would reduce this immediately to > f = <blah> > > Full lazy lambda lifting would give something like this.. > b = <blah> > f = \x -> b x > But this still requires, the (\x -> b x) to be reduced to b > to get.. > b = <blah> > f = b > (and hence f = <blah>) This transformation (eta reduction) is done by GHC under certain circumstances; in particular I believe that in the case where a binding can be eta-reduced so that its right hand side becomes a variable, then the reduction will be performed on the grounds that we can then substitute the binding everywhere without loss of efficiency or increase in code size. However, sometimes it is more beneficial to do the opposite, namely eta expansion. This is because in GHC a call to a known function with all the arguments present is the fastest type of call. Eg: f = \x -> h a x could be reduced to f = h a but if h has arity 2, then the call to h changes from a fast to a slow one, and futhermore we can't make any fast calls to f. On the other hand, the code for the second version is somewhat smaller. There are some subtle tradeoffs here, and this is one of the areas where we often tweak GHC's behaviour in order to try to pick the right balance more often. Cheers, Simon

1 0

Re: Ambiguous types
by Ashley Yakeley 21 Jan '02

21 Jan '02

At 2002-01-21 02:19, Janis Voigtlaender wrote: >The problem is >that for some instance A1 of Ord, l might be an empty list, whereas for >some other instance A2 of Ord, l might be nonempty. Right. I understand now. -- Ashley Yakeley, Seattle WA

1 0

Re: Ambiguous types
by Ashley Yakeley 21 Jan '02

21 Jan '02

I'm quite convinced the Haskell implementations are correct to complain, I just don't understand it intuitively. Anyway, here's an even simpler example: compiles fine: ordnull :: forall a. (Ord a) => [a] -> Bool ordnull = null ordtrue :: (forall a. (Ord a) => [a]) -> Bool ordtrue = const True gives type error: ordnull :: (forall a. (Ord a) => [a]) -> Bool ordnull = null -- Ashley Yakeley, Seattle WA

2 1