- Haskell - Haskell.org

PhD Fellowship in Valencia, Spain
by Maria Alpuente 06 Feb '02

06 Feb '02

DOCTORAL RESEARCH GRANT Extensions of Logic Programming and Formal Methods ************************************************************** The Department of Software of the Technical University of Valencia UPV (Spain), offers one research scholarship to pursue a Ph.D. degree in the Extensions of Logic Programming and Formal Methods Group (ELP). The financial support is provided by the Spanish Ministry of Science and Technology. The grant is posted for one 1-year, extensible to 4 years. The applicants must have a degree in Computer Science to be eligible for PhD admission and research scholarship. The ELP Group currently has 7 faculty members at Valencia, leading activities in different research areas. The topics eligible for research are described below: - Programming Languages: Functional, Logic, Concurrent languages. Multiparadigm Programming. - Term Rewriting Systems. - Formal methods in Software Engineering: Semantics-based analysis, verification, learning, debugging, transformation and optimization of (multiparadigm) programs. Information about the ELP group (9 PhD's, 18 researchers) can be found at: http://www.dsic.upv.es/users/elp/elp.html ============================================================= Appointment and salary ---------------------- PhD students are appointed for a maximum period of 4 years with a gross salary around 10,000 Euros per year (this is not bad for the Spanish cost of living, particularly in Valencia). This includes a 1-month holiday. As part of their training, PhD students will enroll in the PhD program for the graduate courses. The scholarship will also cover all tuition fees. Information and application --------------------------- The call for applications, forms to fill, and all the information to apply can be found at the URL: http://www7.mcyt.es/becas/InicioBecas The deadline to send the application is February 21, 2002. Queries concerning the position should be directed to Maria Alpuente (alpuente(a)dsic.upv.es) ___________________________________________________ Prof. Maria Alpuente Frasnedo Dpto. de Sistemas Informaticos y Computacion U. Politecnica de Valencia Camino de Vera s/n - Apdo. 22.012 E-46022 Valencia (Spain) Fax +34 96 387 9726 http://www.dsic.upv.es/~alpuente ___________________________________________________

1 0

Re: Reference types
by John Hughes 06 Feb '02

06 Feb '02

Ashley Yakeley wrote: 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'. Well, I'm still not convinced. A reference *value* can't have the type (LiftedMonad (ST s) m) => Ref m a This is the type of a function, which given a dictionary returns a reference. Moreover, since when I write do r <- newSTLiftedRef x ... then I am effectively lambda-binding r, then r cannot have this type. It can only have an instance of it ... which ties r to the monad m. Am I missing something here? Seems to me, to do what you're suggesting I would have to put the context inside the Ref type itself: data Ref s a = Ref { readRef :: forall m. LiftedMonad (ST s) m => m a, writeRef :: forall m. LiftedMonad (ST s) m => a -> m () } But now the s had to go back in the type of the reference... Are you really in Seattle? If so, you must be a real nightbird or a tremendously early riser! John

1 0

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