Trees as Monads

We first encountered trees in Haskell in my blog post titled “Trees in Haskell”. In that blog post we studied binary trees. Then we continued our study of binary trees in my blog post titled “Examples of Functors in Haskell”. In that blog post, we saw how binary trees can act not only as type constructors, but also as Functors.

In this blog post, we will study three different types of trees and see how they behave as Functors, Applicatives, and Monads. The first type of tree that we will study is the binary tree. So far, we only elevated the binary tree to a Functor. We are now going to see if and how a binary tree can function as an Applicative and as a Monad. Hint: a binary tree is inappropriate as an Applicative and as a Monad.  Then we are going to study another type of tree that again is inappropriate as an Applicative, but can function as a Monad.  After that, we are going to study yet a third type of tree that is appropriate in all cases.

But who is to say if a type constructor (for trees in this case) is inappropriate or not, as a Functor, Applicative, or Monad? Well, common logic might have something to do with that, but it really is a matter of opinion; it is a subjective matter. Anyway, we are going to discuss what it means for each tree type constructor to be a Functor, Applicative and Monad and the reader can form her own opinion from there. Of course, it is up to the reader to provide her own definition for the Functor, Applicative and Monad instances for any type of tree she wishes to do so, in order to prove her view of how these should be in each case.

First type of tree: good as a Functor, bad as an Applicative, bad as a Monad.

The first type of tree we are going to study is the binary tree, the one we have been studying in previous posts (“Trees in Haskell” and “Examples of Functors in Haskell”). Its definition, i.e. type constructor, is:

data MyTree a = MyEmptyNode
              | MyFilledNode a (MyTree a) (MyTree a)

We can see that the characteristic of a binary tree is that the value (of type a) is held alongside two other trees (of type MyTree a), in each MyFilledNode.

We have seen how this type of tree functions as a Functor, but let us recapitulate: This type of tree behaves nicely as a Functor. Specifically, we program fmap so that the function f of type a -> b is applied to each value of type a throughout the tree. Thus, we apply f to the value of type a and to each of the left and right subtrees all the way down.

Let us now see why everyone (as far as I know) thinks that it is a bad idea to elevate this type of tree to an Applicative or a Monad.

First of all, let us study this type of tree as an Applicative. Elevating this type of tree to an Applicative – what would that entail? When we elevated the list Functor to an Applicative, we programmed <*> so that a list of functions and another list of elements would produce a list with every output of each function applied to each element. Logical and useful. But now, for this type of tree to function as an Applicative, we have to program <*> in a way so that it will utilize two such trees, one with functions and one with values. So what would the output of <*>  look like?

Again, we have a binary tree of functions and a binary tree of values. What should an Applicative instance do? To visualize the situation we are in and the decision we have to make for the implementation of our Applicative, here is an example:

BinaryTreeApplicative

In this example, we have two trees, one with four functions and one with three elements, each one a list. How would we go on applying the functions in the left tree to the functions in the right tree? Remember that the type signature of an Applicative is  (<*>) :: f (a -> b) -> f a -> f b, where f is the Functor/Applicative. Thus, an applicative takes a tree of functions of type a -> b and a tree of elements of type a and produces a tree of elements of type b. Thus, the output of any applicative we can come up, has to be a tree. One tree; not more than one tree. In this case, it has to be one tree of lists, since the output of each of the functions is a new list.

Thus, we cannot devise a solution where we produce a multitude of trees; the Applicative declaration does not allow us to do that with this type of tree that we have. We have to come up with one tree only as the Applicative output. So what will we put into this tree and where? There is no easy answer that everyone can agree on. Whats more, everyone thinks that it is best that binary trees should not be elevated into an Applicative, because there is no real value in doing so. In the program that follows, I provide a rudimentary, unthoughtful, just plain stupid implementation for an Applicative: I only apply the function in the root of the left (functions) tree to the right (elements) tree and discard(!) every other of the left tree’s functions.

Binary trees are also unintuitive as Monads. A Monad is declared as (>>=)  :: m a -> (a -> m b) -> m b, where m is the Monad. In our case, bind (>>=) will take a binary tree as input, as well as a function. This function will take an element of the tree as input and it will produce a binary tree as output. The output of bind has to be of type m b, thus in our case the output of bind is a binary tree. One binary tree; not more than one binary tree.

Perhaps there is no useful and intuitive way to program bind for a binary tree. Indeed, every node that is filled, has an element and two subtrees. If we apply a function of type a -> m b (as the very declaration of Monad demands) to such a node, the function applied to the element will produce a binary tree that we would have nowhere to put. This is because that position can only hold an element (not a tree) and the other two positions are filled with the left and right subtree, that may not be empty (that may not be MyEmptyNode trees) .

In essence, it is difficult, if not impossible, to apply a function a -> m b to a binary tree. In the program that follows, I provide a rudimentary, unthoughtful, just plain stupid implementation for a Monad: I only apply the function to the root element of the input binary tree, and provide this as the output, discarding(!) the left and right subtrees of the input tree altogether.

module Main where

import Control.Applicative

data MyTree a = MyEmptyNode
              | MyFilledNode a (MyTree a) (MyTree a)
              deriving (Show)

instance Functor MyTree where
   fmap f MyEmptyNode          = MyEmptyNode
   fmap f (MyFilledNode x y z) = MyFilledNode (f x) (fmap f y) (fmap f z)

instance Applicative MyTree where
   pure x = MyFilledNode x MyEmptyNode MyEmptyNode
   (MyFilledNode f fy fz) <*> (MyFilledNode x y z) = MyFilledNode (f x) MyEmptyNode MyEmptyNode
   _ <*> _ = MyEmptyNode

instance Monad MyTree where
   return x = MyFilledNode x MyEmptyNode MyEmptyNode
   (MyFilledNode x y z) >>= f = f x
   MyEmptyNode >>= _ = MyEmptyNode

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that MyTree behaves as a type constructor."

      let tree1 = MyFilledNode 5 (MyFilledNode 3 MyEmptyNode MyEmptyNode) (MyFilledNode 2 MyEmptyNode MyEmptyNode)
      print tree1

      let tree2 = MyFilledNode "ABC" (MyFilledNode "AB" MyEmptyNode MyEmptyNode) (MyFilledNode "ABCDEF" MyEmptyNode MyEmptyNode)
      print tree2

      putStrLn "Tests that prove that MyTree behaves as a Functor."

      print (fmap (*2) tree1)
      print (fmap length tree2)

      putStrLn "Tests that prove that MyTree behaves as an Applicative."

      print ((MyFilledNode (*2) MyEmptyNode MyEmptyNode) <*> tree1)
      print ((MyFilledNode init MyEmptyNode MyEmptyNode) <*> tree2)

      putStrLn "Tests that prove that MyTree behaves as a Monad."

      print (tree1 >>= (\x -> MyFilledNode (x+200) MyEmptyNode MyEmptyNode))
      print (tree2 >>= (\x -> MyFilledNode (tail x) MyEmptyNode MyEmptyNode))

      putStrLn "Program ends."

The output of the previous program follows:

Program begins.
Tests that prove that MyTree behaves as a type constructor.
MyFilledNode 5 (MyFilledNode 3 MyEmptyNode MyEmptyNode) (MyFilledNode 2 MyEmptyNode MyEmptyNode)
MyFilledNode "ABC" (MyFilledNode "AB" MyEmptyNode MyEmptyNode) (MyFilledNode "ABCDEF" MyEmptyNode MyEmptyNode)
Tests that prove that MyTree behaves as a Functor.
MyFilledNode 10 (MyFilledNode 6 MyEmptyNode MyEmptyNode) (MyFilledNode 4 MyEmptyNode MyEmptyNode)
MyFilledNode 3 (MyFilledNode 2 MyEmptyNode MyEmptyNode) (MyFilledNode 6 MyEmptyNode MyEmptyNode)
Tests that prove that MyTree behaves as an Applicative.
MyFilledNode 10 MyEmptyNode MyEmptyNode
MyFilledNode "AB" MyEmptyNode MyEmptyNode
Tests that prove that MyTree behaves as a Monad.
MyFilledNode 205 MyEmptyNode MyEmptyNode
MyFilledNode "BC" MyEmptyNode MyEmptyNode
Program ends.

 

Second type of tree: good as a Functor, bad as an Applicative, good as a Monad.

There is a type of tree that is easy to understand as a structure and that solves the problem that we had with the binary tree (mis)behaving as Monad. This tree holds an element at each leaf, whereas each node has no elements; it only has a left subtree and a right subtree.

data MyTree a = MyLeaf a
              | MyNode (MyTree a) (MyTree a)

The structure of this type of tree is exactly what makes it easy and intuitive to implement it as a Monad. But before we discuss that, let us see how it should behave as a Functor and as an Applicative.

This type of tree provides an intuitive Functor: just as in the case of the binary tree, we apply the function we are given to each leaf element and also to each subtree all the way down.

This type of tree has the same problems functioning as an Applicative that we encountered in our study of the binary tree. The only case where both the binary tree and this type of tree perhaps could function relatively adequately is when the functions tree and the elements tree have exactly the same structure and depths. But when we have an arbitrary functions tree and an arbitrary elements tree, as it may well be the case, we have no intuitive way to create an adequate Applicative. In the program that follows, I provide a rudimentary, unthoughtful, just plain stupid implementation for an Applicative: I only consider a functions tree with only one function(!) and I apply this function to the elements tree.

The great thing about this type of tree is that we can provide a very useful implementation of it as a Monad. Indeed, as you will see in the following program, we apply the function a -> m b to each leaf and also bind it to both subtrees in each node. Indeed, because each element is tuck away in a leaf, we are left with subtrees only in the nodes, a situation that allows us to apply the function a -> b to leaf elements  as well as subtrees.

The problem we had with binary trees was that the element coexisted with the subtrees in each node. Thus, a function a -> m b that essentially returned a tree, had no space in the binary tree structure to place three trees where an element and two trees should be. By separating the element and the subtrees in this type of tree, we can elevate it into an intuitive and useful Monad.

module Main where

import Control.Applicative

data MyTree a = MyLeaf a
              | MyNode (MyTree a) (MyTree a)
              deriving (Show)

instance Functor MyTree where
   fmap f (MyLeaf x) = MyLeaf (f x)
   fmap f (MyNode x y) = MyNode (fmap f x) (fmap f y)

instance Applicative MyTree where
   pure = MyLeaf
   (MyLeaf f) <*> (MyLeaf x) = MyLeaf (f x)
   (MyLeaf f) <*> (MyNode x y) = MyNode (fmap f x) (fmap f y)

instance Monad MyTree where
   return = MyLeaf
   (MyLeaf x) >>= f = f x
   (MyNode x y) >>= f = MyNode (x >>= f) (y >>= f)

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that MyTree behaves as a type constructor."

      let tree1 = MyNode (MyLeaf 3) (MyNode (MyLeaf 4) (MyLeaf 5))
      print tree1

      let tree2 = MyNode (MyLeaf "ABC") (MyNode (MyLeaf "DEFG") (MyLeaf "HIJKL"))
      print tree2

      putStrLn "Tests that prove that MyTree behaves as a Functor."

      print (fmap (*2) tree1)
      print (fmap length tree2)

      putStrLn "Tests that prove that MyTree behaves as an Applicative."

      print ((MyLeaf (*2)) <*> tree1)
      print ((MyLeaf init) <*> tree2)

      putStrLn "Tests that prove that MyTree behaves as a Monad."

      print (tree1 >>= (\x -> MyLeaf (x+200)))
      print (tree2 >>= (\x -> MyLeaf (tail x)))

      putStrLn "Program ends."

The output of the previous program follows:

Program begins.
Tests that prove that MyTree behaves as a type constructor.
MyNode (MyLeaf 3) (MyNode (MyLeaf 4) (MyLeaf 5))
MyNode (MyLeaf "ABC") (MyNode (MyLeaf "DEFG") (MyLeaf "HIJKL"))
Tests that prove that MyTree behaves as a Functor.
MyNode (MyLeaf 6) (MyNode (MyLeaf 8) (MyLeaf 10))
MyNode (MyLeaf 3) (MyNode (MyLeaf 4) (MyLeaf 5))
Tests that prove that MyTree behaves as an Applicative.
MyNode (MyLeaf 6) (MyNode (MyLeaf 8) (MyLeaf 10))
MyNode (MyLeaf "AB") (MyNode (MyLeaf "DEF") (MyLeaf "HIJK"))
Tests that prove that MyTree behaves as a Monad.
MyNode (MyLeaf 203) (MyNode (MyLeaf 204) (MyLeaf 205))
MyNode (MyLeaf "BC") (MyNode (MyLeaf "EFG") (MyLeaf "IJKL"))
Program ends.

 

Third type of tree: good as a Functor, good as an Applicative, good as a Monad.

There is a third type of tree that functions well as a Functor, Applicative, and Monad! The structure of this remarkable type is as follows:

data MyTree a = MyNode a [MyTree a]

I mentioned this type of tree at the end of my blog post titled “Trees in Haskell”.  I thought I would close my presentation there, because the gentleman with the chainsaw seemed to get a little upset. But now (and having looked over my shoulder) I can continue.

The two previous types of trees that we studied had one thing in common, they were lousy Applicatives. Well, this type of tree is a great Functor, Applicative, and Monad. Let us see why.

This type of tree has the characteristic of having the element together with the subtrees in the node, as the binary tree does. But the difference in this type of tree is that the subtrees are tucked in a list. This is a huge improvement. It means that in each node, the number of subtrees can be as many as we need. The subtrees can expand “horizontally” in number, something that the other types of trees did not allow. We will see how the concept of the list of subtrees permits this type of tree to be a successful, useful and intuitive Functor, Applicative, and Monad.

First of all, as a Functor, fmap applies the function to the element of the Node as well as to each element/subtree in the list. Easy enough.

As an Applicative, we have to program <*> in order to accommodate a tree of functions and a tree of elements. Let us call the tree of functions as (MyNode f treeFunctionList) and let us call the tree of elements as (MyNode x treeElementList). First of all, our Applicative should apply the function f to element x, and the output should be the element of the resulting node. The list that will accompany this element will include (i) all the outputs of all applications of the function f to the list of the elements (map (fmap f) treeElementList) , as well as (ii) all the applications of all functions in the list of functions to all elements in the list of elements (map (<*> (MyNode x treeElementList)) treeFunctionList). Thus, the Node will have f x as element and it will also have a list of every possible application of each function from the tree of functions and each element from the list of elements. The reason all these can be accommodated is that we have a list, i.e. a “horizontally” expanding structure that can keep all possible combinations of application of functions to elements.

Let us now see why this type of tree can also function as a useful Monad. According to the Monad declaration, the function a -> m b, that we apply to the tree m a we receive as input, should produce a tree m b as output. In our case, in order for our Monad to be intuitive and useful,  we should apply the function f :: a -> m b to (i) the root element of the input tree, as follows: f x, as well as (ii) the treelist of the input tree, as follows: map (>>= f) treeList. The application of the function f to the root element x will produce a tree, thus an element and a treelist. The element will be the root element and the treelist will be the first part of the resulting list, the second part being the result of map (>>= f) treeList.

Again, what makes all this possible is that we have a list of trees next to our root element and we can use this list to tuck in the trees that are produced from all the operations. For example, the input’s root element alone, with the application of the function f produces a whole tree. And a whole tree is also each subtree of the list that accompanies the input’s root element. Thus, it is the list’s unlimited expansion capability that can hold all these trees that are produced and that can make this Monad functional and useful.

module Main where

import Control.Applicative

data MyTree a = MyNode a [MyTree a]
                deriving (Show)

instance Functor MyTree where
   fmap f (MyNode x treeList) = MyNode (f x) (map (fmap f) treeList)

instance Applicative MyTree where
   pure x = MyNode x []
   (MyNode f treeFunctionList) <*> (MyNode x treeElementList) =
      MyNode (f x) ( (map (fmap f) treeElementList) ++ (map (<*> (MyNode x treeElementList)) treeFunctionList) )

instance Monad MyTree where
   return x = MyNode x []
   MyNode x treeList >>= f = MyNode x' (treeList' ++ map (>>= f) treeList)
      where MyNode x' treeList' = f x

main :: IO ()
main  =
   do
      putStrLn "Program begins."

      putStrLn "Tests that prove that MyTree behaves as a type constructor."

      let tree1 = MyNode 5 [MyNode 3 [], MyNode 2 []]
      print tree1

      let tree2 = MyNode "ABC" [MyNode "DEFG" [], MyNode "HIJKL" []]
      print tree2

      putStrLn "Tests that prove that MyTree behaves as a Functor."

      print (fmap (*2) tree1)
      print (fmap length tree2)

      putStrLn "Tests that prove that MyTree behaves as an Applicative."

      print ((MyNode (*2) []) <*> tree1)
      print ((MyNode (*2) [MyNode (+100) [], MyNode (+1000) []]) <*> tree1)
      print ((MyNode init []) <*> tree2)
      print ((MyNode init [MyNode reverse [MyNode tail []]]) <*> tree2)

      putStrLn "Tests that prove that MyTree behaves as a Monad."

      print (tree1 >>= (\x -> MyNode (x+200) []))
      print (tree2 >>= (\x -> MyNode (tail x) []))

      putStrLn "Program ends."

The output of the previous program follows:

Program begins.
Tests that prove that MyTree behaves as a type constructor.
MyNode 5 [MyNode 3 [],MyNode 2 []]
MyNode "ABC" [MyNode "DEFG" [],MyNode "HIJKL" []]
Tests that prove that MyTree behaves as a Functor.
MyNode 10 [MyNode 6 [],MyNode 4 []]
MyNode 3 [MyNode 4 [],MyNode 5 []]
Tests that prove that MyTree behaves as an Applicative.
MyNode 10 [MyNode 6 [],MyNode 4 []]
MyNode 10 [MyNode 6 [],MyNode 4 [],MyNode 105 [MyNode 103 [],MyNode 102 []],MyNode 1005 [MyNode 1003 [],MyNode 1002 []]]
MyNode "AB" [MyNode "DEF" [],MyNode "HIJK" []]
MyNode "AB" [MyNode "DEF" [],MyNode "HIJK" [],MyNode "CBA" [MyNode "GFED" [],MyNode "LKJIH" [],MyNode "BC" [MyNode "EFG" [],MyNode "IJKL" []]]]
Tests that prove that MyTree behaves as a Monad.
MyNode 205 [MyNode 203 [],MyNode 202 []]
MyNode "BC" [MyNode "EFG" [],MyNode "IJKL" []]
Program ends
Advertisements

About Dimitrios Kalemis

I am a systems engineer specializing in Microsoft products and technologies. I am also an author. Please visit my blog to see the blog posts I have written, the books I have written and the applications I have created. I definitely recommend my blog posts under the category "Management", all my books and all my applications. I believe that you will find them interesting and useful. I am in the process of writing more blog posts and books, so please visit my blog from time to time to see what I come up with next. I am also active on other sites; links to those you can find in the "About me" page of my blog.
This entry was posted in Development. Bookmark the permalink.