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