[Haskell-cafe] Short circuiting and the Maybe monad

[Eric Stansifer]

> 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