Monad for a Rose tree

Question

I have this data type

> data Rose a
>   = RoseNode a [Rose a]
>   | RoseLeaf

And I need to make a monad instance for it. Here's my atempt

> instance Monad Rose where
>    return = RoseNode
>    RoseNode a rs >>= f = RoseNode (f a) (rs >>= f)
>    RoseLeaf >>= _ = RoseLeaf

But I'm getting this error

app\Main.lhs:599:15: error:
    * Couldn't match type `[Rose a] -> Rose a' with `Rose a'
      Expected type: a -> Rose a
        Actual type: a -> [Rose a] -> Rose a
    * Probable cause: `RoseNode' is applied to too few arguments
      In the expression: RoseNode
      In an equation for `return': return = RoseNode
      In the instance declaration for `Monad Rose'
    * Relevant bindings include
        return :: a -> Rose a (bound at app\Main.lhs:599:6)
    |
599 | >    return = RoseNode
    |               ^^^^^^

and this one

app\Main.lhs:601:51: error:
    * Couldn't match type `Rose' with `[]'
      Expected type: Rose a -> [b]
        Actual type: a -> Rose b
    * In the second argument of `(>>=)', namely `f'
      In the second argument of `RoseNode', namely `(rs >>= f)'
      In the expression: RoseNode (f a) (rs >>= f)
    |
601 | >    RoseNode a rs >>= f = RoseNode (f a) (rs >>= f)
    |

How do I fix those?

Edit Here's the Applicative for Rose

> instance Applicative Rose where
>     pure x = RoseNode x []
>     (<*>) _ RoseLeaf = RoseLeaf
>     (<*>) RoseLeaf _ = RoseLeaf
>     (<*>) (RoseNode f rosa) n@(RoseNode x subrosa) = RoseNode (f x) (map (fmap f) subrosa ++ map (<*> n) rosa)

user_7203016 · Answer

Was this a homework exercise? If so, was the Rose data type given to you, or did you come up with it yourself? It's possible that you were supposed to come up with a different Rose type, with the values in the leaves instead of the nodes, because the monad instance for leaf-value rose trees is much more obvious than the monad for node-value rose trees.

As you know, for a list, the monadic bind operation lst >>= f uses f to replace each value in the original list with a sublist, and then it "flattens" the result, so it's still a list of values, instead of a list of lists of values.

Similarly, for a tree, the monadic bind operation tree >>= f should apply f to replace each value in the tree with a subtree, and then "flatten" the result, so it's still a tree of values, instead of a tree of trees of values.

Specifically, for a rose tree with the values in the leaves, the intended definition of rose >>= f is straightforward -- it should replace each leaf-value with a leaf-tree, and then "flatten" the result, so the new subtrees are grafted on to the original tree.

For a rose tree with the values in the nodes, it's tougher to figure out what's supposed to happen. Each value in a node should be replaced by a subtree, but it's a little hard to figure out how to "flatten" the result, since it's not as simple as grafting subtrees onto the leaves. At each node, you've got the new subtree, and then you've also got the main tree branches under that node, each a tree of subtrees that need to be flattened. I guess the obvious possibilities are to (1) concatenate the node's subtree with the flattening of the other branches under that node; or (2) concatenate them in the opposite order, first flattening of other branches under that node, then the node's subtree.

It looks like your applicative instance implements the equivalent of (1).

So, the instances you probably want are:

data Rose a
  = RoseNode a [Rose a]
  | RoseLeaf
  deriving (Functor)
instance Applicative Rose where
  pure x = RoseNode x []
  (<*>) _ RoseLeaf = RoseLeaf
  (<*>) RoseLeaf _ = RoseLeaf
  (<*>) (RoseNode f rosa) n@(RoseNode x subrosa) 
    = RoseNode (f x) (map (fmap f) subrosa ++ map (<*> n) rosa)
instance Monad Rose where
  RoseLeaf >>= _ = RoseLeaf
  RoseNode x branches >>= f = case f x of
    RoseLeaf -> RoseLeaf
    RoseNode y branches' -> RoseNode y (branches' ++ fmap (>>= f) branches)

Note that you need not define return because it defaults to pure.

You can ensure that the applicative and monad instances are "compatible" by comparing (<*>) from the Applicative instance with ap from Control.Monad, which implements (<*>) using monadic operations:

{-# LANGUAGE DeriveFunctor #-}

import Control.Monad

data Rose a
  = RoseNode a [Rose a]
  | RoseLeaf
  deriving (Functor, Show)
instance Applicative Rose where
  pure x = RoseNode x []
  (<*>) _ RoseLeaf = RoseLeaf
  (<*>) RoseLeaf _ = RoseLeaf
  (<*>) (RoseNode f rosa) n@(RoseNode x subrosa)
    = RoseNode (f x) (map (fmap f) subrosa ++ map (<*> n) rosa)
instance Monad Rose where
  RoseLeaf >>= _ = RoseLeaf
  RoseNode x branches >>= f = case f x of
    RoseLeaf -> RoseLeaf
    RoseNode y branches' -> RoseNode y (branches' ++ fmap (>>= f) branches)

t1 = RoseNode (+1) [RoseNode (+2) [], RoseNode (+3) []]
t2 = RoseNode 17 [RoseNode 23 [], RoseNode 29 []]

main = do
  print $ t1 <*> t2
  print $ t1 `ap` t2

Monad for a Rose tree

1 Answers