[Haskell-cafe] tree with labeled edges as a monad

[Andrew Pimlott]

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