February 2002 - Haskell

Re: Reference types
by Ashley Yakeley 06 Feb '02

06 Feb '02

At 2002-02-06 00:54, Koen Claessen wrote: >You are completely right, of course I meant r -> m! Right. There's the equivalent of an r -> m dependency because m is a parameter in the Ref type constructor. But it doesn't matter, because you can create values of this type: myIntRef :: (MyMonad m) => Ref m Int ...i.e., references that work with multiple monads. -- Ashley Yakeley, Seattle WA

1 0

Re: Reference types
by Ashley Yakeley 06 Feb '02

06 Feb '02

At 2002-02-06 01:09, John Hughes wrote: >No no no! This still makes the reference type depend on the monad type, which >means that I cannot manipulate the same reference in two different monads! Yes you can. Consider: -- m somehow uses 'rep' internally class (Monad rep, Monad m) => LiftedMonad rep m where { lift :: rep a -> m a; } instance LiftedMonad (ST s) (ST s) where { lift = id; } instance LiftedMonad (ST s) TransformedMonad where ... liftRef :: (LiftedMonad rep m) => Ref rep a -> Ref m a; liftRef ref = ... newSTRef :: a -> Ref (ST s) a; newSTLiftedRef :: (LiftedMonad (ST s) m) => a -> Ref m a; newSTLiftedRef = liftRef . newSTRef; With me so far? Now here's the clever bit: Refs created with newSTLiftedRef are of type '(LiftedMonad (ST s) m) => Ref m a'. This means they will work equally well as 'Ref (ST s) a' as they will as 'Ref TransformedMonad a'. -- Ashley Yakeley, Seattle WA

1 0

Re: Reference types
by John Hughes 06 Feb '02

06 Feb '02

John Hughes despaired: | Oh no, please don't do this! I use the RefMonad class, | but *without* the dependency r -> m. Why not? Because | I want to manipulate (for example) STRefs in monads | built on top of the ST monad via monad transformers. | So I use the same reference type with *many different* | monads! Your change would make this impossible. Ashley Yakeley soothingly suggested: | I don't think so. [...] : | data Ref m a = MkRef | { | get :: m a, | set :: a -> m (), | modify :: (a -> a) -> m () | }; Koen commented: Hm... this looks nice. With slight name changes this becomes: data Ref m a = MkRef { readRef :: m a , writeRef :: a -> m () } No no no! This still makes the reference type depend on the monad type, which means that I cannot manipulate the same reference in two different monads! One of the things I want to do sometimes is to, say, add exceptions using a monad transformer during just *part* of an ST computation. That means I want to manipulate the *same* references in both the unadorned ST monad and the transformed one. Further, Ashley writes: | The point is that the m -> r dependency is also | unnecessary, except when you want a new "standard" ref | for a monad. No no no! Well, preferably not. I find that removing that dependency creates a lot of ambiguity in the overloading: if one uses a reference locally, the type-checker cannot infer (from the type of the monad) what kind of reference should be used. That forces a lot of explicit type information to be added, which just clutters programs unnecessarily. Koen says: Not really, the m -> r is still there in practise, since you want to be able to use the 'readRef' and 'writeRef' operators, which work on the monad m, and you want them to work on the monad (t m). In this case one can simply lift the reference, like this: liftRef :: MonadTrans t => Ref m a -> Ref (t m) a liftRef ref = MkRef { readRef = lift (readRef ref) , writeRef = \a -> lift (writeRef ref a) } Look, ma, no type classes! No no no! I don't want to have to *transform* references in order to use them in another monad! Suppose I've built a large structure, such as a UNION-FIND forest, and then I want to work in an extended monad for a little. Should I transform the entire structure in order to continue working on it? Afterwards, when I return to the underlying monad, I would need to coerce the references back again... I would need dropRef :: MonadTrans t => Ref (t m) a -> Ref m a How would you provide that?? This is beginning to sound expensive. And all of this, just because of an arbitrary type distinction between types which are actually the same! I'm using monad transformers heavily now, and often switching between monads. I find it a very modular and attractive way of programming, and in this context I'm (still) convinced that making reference types depend on the monad is a Really Bad Idea! The most reasonable approach I can see if one were to do this, would be just to manipulate references in the monad they belong to (normally ST or IO), and explicitly lift reference operations to the current monad at each use. That could be awkward, since if one has applied several monad transformers then the lifting might be in several stages (and don't say "overlapping instances"). It also would hinder one from writing generic reference-using code, that would work in either an unadorned ST or IO monad or a transformed one. In fact, it seems to lose most of the benefit of overloading the reference operations in the first place! John

1 0

Re: Reference types
by Ashley Yakeley 06 Feb '02

06 Feb '02

At 2002-02-06 00:33, Koen Claessen wrote: >Hm... this looks nice. With slight name changes this >becomes: Oh if you must. I decided that Refs were _so_ fundamental that anytime you get, set or modify anything it could probably be represented as a Ref, so the functions merit highly generic names. And 'read' and 'write' are for streams IMO. >Not really, the m -> r is still there in practise, since you >want to be able to use the 'readRef' and 'writeRef' >operators, which work on the monad m, and you want them to >work on the monad (t m). So how is that an m -> r dependency? Nothing is stopping the programmer have two different kinds of reference for the same monad, and 'readRef' and 'writeRef' will work on any Ref. -- Ashley Yakeley, Seattle WA

2 1

Re: Reference types
by Ashley Yakeley 06 Feb '02

06 Feb '02

At 2002-02-05 15:10, John Hughes wrote: >Oh no, please don't do this! I use the RefMonad class, but *without* the >dependency r -> m. Why not? Because I want to manipulate (for example) STRefs >in monads built on top of the ST monad via monad transformers. So I use the >same reference type with *many different* monads! Your change would make this >impossible. I don't think so. Provided you have a class that represents your monads, I don't see why you can't do this: class (Monad m) => MyMonad m where ... myIntRef :: (MyMonad m) => Ref m Int; ...except that with Simon's suggested change you wouldn't be able to define your own Refs. I believe the best solution to the problem involves leaving the existing functions as is but adding something like this: data Ref m a = MkRef { get :: m a, set :: a -> m (), modify :: (a -> a) -> m () }; mkRef g s = MkRef g s (\map -> do { val <- g; s (map val); }); refBind :: (Monad m) => (m a) -> (a -> Ref m b) -> Ref m b; refBind ma arb = MkRef ( ma >>= (\a -> get (arb a) )) (\b -> ma >>= (\a -> set (arb a) b )) (\map -> ma >>= (\a -> modify (arb a) map )); class (Monad m) => RefMonad m where { newRef :: a -> m (Ref m a); -- "standard" ref for this monad }; instance RefMonad IO where { newRef a = do { r <- newIORef a; return MkRef (readIORef r) (writeIORef r) (modifyIORef r) }; }; instance RefMonad (ST s) where etc. The point is that the m -> r dependency is also unnecessary, except when you want a new "standard" ref for a monad. -- Ashley Yakeley, Seattle WA

2 1

Re: Reference types
by John Hughes 05 Feb '02

05 Feb '02

The basic bind operations etc are overloaded for IO and ST, but to overload the Ref operations one needs to add class RefMonad r m | r -> m, m -> r where newRef :: a -> m (r a) readRef :: r a -> m a writeRef :: r a -> a -> m () instance RefMonad IORef IO where ... instance RefMonad (STRef s) (IO s) where ... A multi-paramter type class is needed. Notice particularly the bidirectional functional dependencies. This is the only convincing example I know with functional dependencies going both ways. Or at least it was. But in a recent conversation with Peter Thiemann I realised that this is all baloney. There's a much easier type structure: data Ref m a -- References in monad m, values of type a newIORef :: a -> IO (Ref IO a) readIORef :: Ref IO a -> IO a writeIORef :: Ref IO a -> a -> IO () newSTRef :: a -> ST s (Ref (ST s) a) readSTRef :: Ref (ST s) a -> ST s a writeSTRef :: Ref (ST s) a -> a -> ST s () class RefMonad m where newRef :: a -> m (Ref m a) readRef :: Ref m a -> m a writeRef :: Ref m a -> a -> m () instance RefMonad IO where ... instance RefMonad (ST s) where ... No functional dependencies. No multi-parameter classes. Pure Haskell 98. All of this works for mutable arrays too, of course. Oh no, please don't do this! I use the RefMonad class, but *without* the dependency r -> m. Why not? Because I want to manipulate (for example) STRefs in monads built on top of the ST monad via monad transformers. So I use the same reference type with *many different* monads! Your change would make this impossible. John

1 0

Simpler Fibonacci function
by Brian Berns 05 Feb '02

05 Feb '02

I am new to functional programming and teaching myself Haskell. The canonical Haskell "fib" function (e.g. as presented in the "Gentle" tutorial) is: fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ] This seems, to be polite, a bit overly complex. By comparison, here is a simpler version: fib x y = x : fib y (x+y) For example, fib 1 1 => [1,1,2,3,5,8,13,21,...]. Is there a reason why the canonical fib function is so complex? If not, would it be possible to use a simpler version in the tutorial? Thanks. -- Brian

4 3

Re: Reference types
by Ashley Yakeley 05 Feb '02

05 Feb '02

At 2002-02-05 07:50, Simon Peyton-Jones wrote: > data Ref m a -- References in monad m, values of type a etc. You might be interested in: <http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/*checkout*/jvm-bridge/sourc e/Haskell/Ref.hs?rev=HEAD&content-type=text/plain> data Ref m a = MkRef { get :: m a, set :: a -> m (), modify :: (a -> a) -> m () }; JVM-Bridge uses Refs for fields in Java classes. The monads in question are of type "(IsJVMMonad m) => m". As a general rule, if your class has a lot of members of the form "a -> b", where the a's are all the same, it's a clue to consider using a data type instead. -- Ashley Yakeley, Seattle WA

1 0

Implicit Parameters
by Koen Claessen 05 Feb '02

05 Feb '02

Hi all, Now we are talking about implicit parameters, let us take up the following problem with them on the Haskell mailing list too. Suppose I have the following function definition: app :: (?ys :: [a]) => [a] -> [a] app xs = case ?ys of [] -> xs (y:ys') -> y : (app xs with ?ys = ys') This function appends its argument to its implicit argument, by recursively changing the implicit argument. For example: Hugs> app [1,2] with ?ys = [3,4] [3,4,1,2] So far so good! Now, since Haskell has type inference, we can leave out the type signature: -- app :: (?ys :: [a]) => [a] -> [a] app xs = case ?ys of [] -> xs (y:ys') -> y : (app xs with ?ys = ys') Let us check if it still works again: Hugs> app [1,2] with ?ys = [3,4] [3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,{Interrupted!} And, stunningly, it doesn't! Why doesn't this work? That is because type inference assumes that the body of `app' is monomorphic, i.e. has no context in its type. Therefore, the recursive call to app where ?ys is changed, had no effect at all. It works with the type signature there, because in order to implement type checking (note: not type inference) with polymorphic recursion demands to use the stated type in checking the body of the function. Mark Shields, Simon Peyton-Jones, and I, and also Jörgen Gustavsson have been discussing several modest solutions to this (we believe it is not needed to do full type inference that can deal with polymorphic recursion to solve this problem). My questiona are: Were the designers of the implicit parameters paper aware of this problem when they wrote the paper? If so, they probably did not think this was a big problem. Do people in general think this is a problem? /Koen. -- Koen Claessen http://www.cs.chalmers.se/~koen Chalmers University, Gothenburg, Sweden.

3 2

Re: RFC: Syntax for implicit parameter bindings
by John Hughes 05 Feb '02

05 Feb '02

[Resent with permission of author -=chak] I'm beginning to find implicit parameters *extremely* useful, so I think it's important to get this right. I have some code that will have to change, but not as much as I will have in a couple of years...! I find adding a keyword to implicit parameter declarations, as in let dynamic ?base = 10 in addBase 5 or let nonrec ?base = 10 in addBase 5 just plain ugly. The question mark already indicates that this is an implicit parameter binding, there is no need for another keyword to say the same thing. This would make sense to me if implicit parameter names were lexically the same as other identifiers -- but THAT would be a big mistake! Without wanting to stir up language wars, this idea reminds me of ML rather than Haskell. One of the great strengths of Haskell's syntax, in my opinion, is just that it is so concise. Let's keep it that way! I am against let ?base := 10 in addBase 5 also -- not because := is already a constructor, but because I have another proposal for how to use it! From time to time I argue for a "monomorphic binding" operator, a substitute for the monomorphism restriction, which has become even more necessary with the addition of implicit parameters. (See my "Global Variables in Haskell" paper for a discussion and example). I'd like to reserve := for monomorphic binding. That leaves plain let bindings -- and in that case, why not also where, case, do, and lambda? There was also a mention of extending the implicit parameter story to work as recursive bindings, but I don't know any details here. It would certainly strengthen the case for using plain `let'. Why not recursive bindings? Why not mix implicitly bound variables and explicitly bound ones in the same pattern? This is surely the most orthogonal and powerful mechanism. The question is whether such bindings always have a clear meaning. I claim they do. For each implicitly bound variable ?x, let's assume that x is a fresh variable. Let e be an expression in the scope of ?x. Then I claim that replacing each such e by e with ?x = x and replacing the binding occurrence of ?x by x gives a sensible meaning to the extended language. For example, let ?fac n = if n==0 then 1 else n*fac? (n-1) in e means let fac n = if n==0 then 1 else n*fac? (n-1) with fac? = fac in e with fac? = fac And (\?x -> e) means (\x -> e with ?x = x) The only funny thing is that, because of the way implicit parameters are passed, their types cannot be generalised. John

2 1