[Haskell-cafe] Short circuiting and the Maybe monad
Eric Stansifer
stansife at caltech.edu
Sun May 18 09:11:29 EDT 2008
> Since a tree is a kind of container, yes, it should be a monad. [I'm still
> not really sure whether it's "useful".]
I have a use for the tree monad -- well, I have a use for the monadic
`join' operation (but I don't use any of the monadic operations other
than `return').
My program is making a file. It stores the lines in the file (I need
the individual lines, for operations like "indent all lines by four
spaces"):
*> type File = [Line]
And each line is a ordered collection of String s, waiting to be concatenated:
*> type Line = [String]
At the end of the day I need one long string:
*> finish :: File -> String
*> finish file = concat (concat file)
(I'm eliding dealing with endlines, etc.)
But elsewhere in my program, I would like to have an O(1) (++)
operation, i.e., I would like to be able to do "line1 ++ line2" and
"file1 ++ file2" in O(1) time. So I use a "Tree a" instead of "[a]":
> type File = Tree Line
> type Line = Tree String
> finish file = concat (tree_to_list (tree_flatten file))
Admittedly, I'm not really doing anything actually "monadic" here -- I
just happen to be using the `join' operation. I am sure others can
come up with better examples.
While we're at it, an example use for the ((->) a) monad. For any set
S and ring R, the abelian group of functions f :: S -> R is a free
module (in the mathematical sense of the word "module") over the ring
R. The group and module operations are easily defined in terms of the
monadic operations:
> data FreeModule s r = FreeModule (s -> r)
> instance Functor (FreeModule s) where ...
> instance Monad (FreeModule s) where ...
> instance Ring r => Group (FreeModule s r) where
> (+) m1 m2 = liftM2 (+) m1 m2
> negative m = fmap negative m
> zero = return zero
>
> instance Ring r => Module r (FreeModule s r) where
> r *> m = fmap (r *) m
(Here I write `r *> m' to mean the module element `m' left-multiplied
by the ring element `r'.)
I have another implementation of FreeModule which specializes S to the
natural numbers: but the set of functions f :: \mathbb{N} -> R are
isomorphic with f :: [R] (provided we only permit infinite lists), in
the same way that Dave Menendez describes how f :: Bool -> a is
isomorphic to f :: Diag a. Under this isomorphism, we translate the
monadic operations from ((->) \mathbb{N}) to monadic operations on
lists -- but the resulting monad is different from the usual list
monad (where join = concat is the "structure flattening" operation).
After all, the `concat' operation is pretty boring if you only permit
infinite lists (for then `concat' is the same as `head').
Eric
More information about the Haskell-Cafe
mailing list