For some time now, GHC and Hugs have had the following families of types and operations: data IO a data IORef a newIORef :: a -> IO (IORef a) readIORef :: IORef a -> IO a writeIORef :: IORef a -> a -> IO () data ST s a data STRef s a newSTRef :: a -> ST s (STRef s a) readSTRef :: STRef s a -> ST s a writeSTRef :: STRef s a -> a -> ST s () 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. I'm sending this to the Haskell list for several reasons. 1. It's a good lesson in "don't use a sledgehammer just becaues it happens to be to hand". 2. I'd be interested to know of any other examples you have of *bi-directional* functional depenencies. The above simplification nukes my only convincing example. (Usually one set of type variables determines another, but not vice versa.) Unless there's some technical flaw, this simpler type structure will be in the new hierarchical Haskell library structure. Simon
I applaud the simplification. Getting rid of multi parameter classes and functional dependencies is a Good Thing. Unfortunately I am worried about the extensibility of the new scheme. You replace two types, IORef a and STRef s a by a single type:
data Ref m a -- References in monad m, values of type a
I suppose the implementation of the two original types is actually the same, so that they can be merged. The m is a phantom type argument. How, however, can I now define an instance of RefMonad for my own Monad?
class RefMonad m where newRef :: a -> m (Ref m a) readRef :: Ref m a -> m a writeRef :: Ref m a -> a -> m ()
If I remember Koen Claessen correctly, it is actually impossible to define your own references in Haskell, even inefficient ones, without builtin references. Nonetheless, I might want for example to define a GUI monad, with an embedded IO monad. data GUI a = GUI (State -> IO (State,a)) Then I would like to define the newRef, readRef, writeRef operations on Ref GUI a in terms of the operations on Ref IO a. But I don't see any way to do that. Probably some kind of type conversion between various Ref m a types would be needed; the existence of such a type conversion function probably leads to other nasty problems... Any solutions? -- OLAF CHITIL, Dept. of Computer Science, The University of York, York YO10 5DD, UK. URL: http://www.cs.york.ac.uk/~olaf/ Tel: +44 1904 434756; Fax: +44 1904 432767
Hi Simon, The one parameter scheme that you've described breaks down if you want to generalize further and allow something like: class RefMonad r m where new :: a -> m (r a) read :: r a -> m a write :: r a -> a -> m () instance RefMonad IORef IO where ... instance RefMonad STRef ST where ... instance RefMonad Channel IO where ... -- note, this breaks the instance RefMonad MVar IO where ... -- (m -> r) dependency instance (RefMonad r m, MonadT t) => RefMonad r (t m) where ... -- and this kills the -- (r -> m) dependency [This is just an example, not a proposal.] Note the complete lack of functional dependencies. I really don't think they are the right tool here. Similar uses of fundeps have appeared in some code for state monads; I don't think they are appropriate there either. Bidirectional dependencies are occasionally useful, but, in general, it is also easy to overuse functional dependencies (the same, I believe, is true for classes in general). The simpler type structure you describe looks more appealing to me. All the best, Mark
Hi Simon On Tue, 5 Feb 2002, Simon Peyton-Jones wrote:
2. I'd be interested to know of any other examples you have of *bi-directional* functional depenencies. The above simplification nukes my only convincing example. (Usually one set of type variables determines another, but not vice versa.)
The kind of programming I do at the type level in `Faking It' http://www.dur.ac.uk/c.t.mcbride/faking.ps is fairly ordinary recursive programming on datatype expressions using type classes with functional dependencies. Just as many logic programs have more than one functional (or partial-functional) mode, so do many type class programs. An artificial, but simple example
data Empty
class Add x y z | x y -> z, z x -> y
instance Add Empty y y
instance Add x y z => Add (Maybe x) y (Maybe z)
The two functional dependencies indicate that the compiler can be expected either to add or to subtract in order to determine a missing instance variable. Of course, depending on the types of the operations for which Add is used, not all of the possible functional dependencies may be relevant. There is one example in `Faking It'---zipWith for vectors---which requires two such dependencies. I'm sure I've got some other examples lurking about; these things do pop up. Whether such examples are `convincing' is another matter. Type-level functional programming is a rather bizarre application of the class system. I nonetheless find it very useful; I just wish type-level functional programming was a less bizarre application of something rather more like functional programming. Cheers Conor
participants (4)
-
C T McBride -
Mark P Jones -
Olaf Chitil -
Simon Peyton-Jones