This is a "have you seen this monad?" post. I was trying to construct a search tree, and decided I wanted to do it in a monad (so I could apply StateT and keep state as I explored the space). I discovered that a tree with labeled leaves is a monad, but I wanted to label internal nodes, and such a tree (eg, Data.Tree.Tree) is not a monad (because it can only have one result type). Finally, I realized I could get a similar effect by labeling the edges and the leaves with different types: data Tree l a = Leaf a | Branch [(l, Tree l a)] instance Monad (Tree l) where return = Leaf Leaf a >>= f = f a Branch c >>= f = Branch [(l, t >>= f) | (l, t) <- c] You might use it as turn = do board <- getBoard move <- lift (Branch [(move, return move) | move <- findMoves board]) applyMove move turn I found this quite pleasing, though I hadn't run across trees as monads before. Has anyone else found this useful? Is it in a library somewhere? Andrew
On Wed, Jan 19, 2005 at 01:40:06AM -0800, Andrew Pimlott wrote:
This is a "have you seen this monad?" post. I was trying to construct a search tree, and decided I wanted to do it in a monad (so I could apply StateT and keep state as I explored the space). I discovered that a tree with labeled leaves is a monad, but I wanted to label internal nodes, and such a tree (eg, Data.Tree.Tree) is not a monad (because it can only have one result type). Finally, I realized I could get a similar effect by labeling the edges and the leaves with different types:
data Tree l a = Leaf a | Branch [(l, Tree l a)]
instance Monad (Tree l) where return = Leaf Leaf a >>= f = f a Branch c >>= f = Branch [(l, t >>= f) | (l, t) <- c]
You might use it as
turn = do board <- getBoard move <- lift (Branch [(move, return move) | move <- findMoves board]) applyMove move turn
I found this quite pleasing, though I hadn't run across trees as monads before. Has anyone else found this useful? Is it in a library somewhere?
More generally: data Resumptions f a = Val a | Resume (f (Resumptions f a)) instance Functor f => Monad (Resumptions f) where return = Val Leaf a >>= f = f a Resume t >>= f = Resume (fmap (>>= f) t) An example is a model of the IO monad, with f instantiated to data SysCall a = GetChar (Char -> a) | PutChar Char a | ... This monad in turn is a special case of the monad transformer newtype GR f m a = GR (m (Either a (f (GR f m a)))) unGR (GR x) = x instance (Functor f, Monad m) => Monad (GR f m) where return = GR . return . Left GR r >>= f = GR (r >>= either (unGR . f) (return . Right . fmap (>>= f))) which Moggi calls generalized resumptions in "A syntactic approach to modularity in denotational semantics", section 2.3. This paper is available on http://www.disi.unige.it/person/MoggiE/publications.html (It has some nice general monads, but is mostly impenetrable.)
Hi, This is a "hey that's cool" post :-) I have seen both of those separately --- the generalized resumptions monad, and the IO (and others) monad written in continuation passing style, but never realized that the one was an instance of the other. It is neat how the basic operations are separated from the sequencing. Does anyone know how related (it seems somewhat related) is all that to the recent work by Plotkin and Power on deriving monad implementations from their operations? -Iavor
More generally:
data Resumptions f a = Val a | Resume (f (Resumptions f a))
instance Functor f => Monad (Resumptions f) where return = Val Leaf a >>= f = f a Resume t >>= f = Resume (fmap (>>= f) t)
An example is a model of the IO monad, with f instantiated to
data SysCall a = GetChar (Char -> a) | PutChar Char a | ...
participants (3)
-
Andrew Pimlott -
Iavor Diatchki -
Ross Paterson