1

I'm trying to make a Decision Tree for a game and I have:

data DecisionTree a
   = Result a
   | Decision [DecisionTree a]
   deriving (Eq,Show)`

furthermore, I have

instance Functor DecisionTree where
    fmap = liftM

now I have to define 

instance Monad DecisionTree where
-- return :: a -> DecisionTree a
   return = ...
-- (>>=) :: DecisionTree a -> (a -> DecisionTree b) -> DecisionTree b
   (>>=) = ...

Now I'm kinda confused how to fill in the definitions.

To define >>= I tried splitting the definition into two cases:

(>>=) (Result a) f    = f a
(>>=) (Decision ys) f = Decision (fmap (>>= f) ys)

As for return I thought at least something like

return = Result

but this only builds Result a and no Decision [DecisionTree a].

Am I completely off or am I close?

leftaroundabout
  • 117,950
  • 5
  • 174
  • 319
tbpotn
  • 73
  • 8
  • Please use proper block-markdown for code blocks (as I edited it now). The easiest way to do this is to select the code blocks and press `ctrl+k`. – leftaroundabout Oct 16 '15 at 17:41
  • There is in general not _one right way_ to define a monad instance. It depends on what behaviour you want / how you plan to use these trees. Your ideas aren't “completely off”, but whether they're right I can't say without further information. – leftaroundabout Oct 16 '15 at 17:45
  • 1
    If I'm looking at it correctly, `DecisionTree` is isomorphic to `Free []` (that is, [`Control.Monad.Free`](http://hackage.haskell.org/package/free-4.12.1/docs/Control-Monad-Free.html) from the `free` package). In that case, what `(>>=)` does is to substitute each `Result` in the decision tree with a whole new tree constructed from the result's value. See this other question: http://stackoverflow.com/questions/32413797/implementing-mymonad-free-f – danidiaz Oct 16 '15 at 17:51
  • It looks to me like if your if `f` produces a `Decision [DecisionTree a]` you can also build that kind of substructure. What is the problem exactly? Are you not sure if the monad laws are fulfilled, do you get errors, are the results not what you expected? – Sam van Herwaarden Oct 16 '15 at 18:04
  • I decided to check what was not functioning properly by just plugging in some values and see what the results are and they were what I wanted. So I decided to go on and use it in my next function to simulate tossing a coin and rolling a dice and apparantly it does function the way I intended. Thanks for the added information, I think it helped me understand more what I was doing. – tbpotn Oct 16 '15 at 18:32

1 Answers1

4

This is the free monad for []. As such, while there may be multiple ways to define a monad instance (per @leftroundabout), there is one canonical way to define a free monad instance, which is the one you have chosen. (You can compare your implementation to that of Free and see that they are equivalent. The only difference is that you fix the choice of f to [].)

but this only builds Result a and no Decision [DecisionTree a].

I'm not sure what this means, but an arrow a -> DecisionTree b that produces a Decision will produce a Decision. return will always produce a Result, but that is expected.

Rein Henrichs
  • 15,437
  • 1
  • 45
  • 55
  • Accepting this, since this combined with the comments made me find the solution (which was in fact what I had already, but somehow it gave some problems). – tbpotn Oct 16 '15 at 18:34