#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

# Question 3.7 - The tree monad.

Recall that a binary tree with leaves valued in A is an element of the initial F-algebra where F is the functor:

$$FA : Set \rightarrow Set;$$

$$X \rightarrow A + X \times X;$$

$$(f : X \rightarrow Y ) \mapsto (idA + f \times f): A + X \times X \rightarrow A + Y \times Y$$

(a) Define a monad T : Set → Set that maps a set A to the set of trees with leaves valued in A.

• Options
1.

a) So first, we must define an $$\eta$$ for this Monad. In this case, it will receive a value of A and returns a Tree of A, as such, it should map the value to the leaf:

$$\eta(a) \mapsto A$$

The join function $$\mu$$ will map a Tree of Tree of A and should return a Tree of A:

$$\mu : A + (A + X \times X) \times (A + X \times X) \rightarrow A + X \times X$$

You can enumerate some situations:

1. If it receives a leaf, this leaf will contain a Tree of A, so we can just return the content of this leaf:

$$A \mapsto A$$

1. If it receives a node $$X \times X$$, the left and right children will be of type Tree of Tree of A, but we should return a new node with the left and right children being of the type Tree of A. Well...we do have a function that does that for us:

$$X \mapsto \mu(X)$$

b)

In Haskell the Data Structure would be represented as:

Tree a = Leaf a | Node (Tree a) (Tree a)

The return should create a singleton tree with only a single leaf:

return x = Leaf x

And the join operation will collapse a Tree of Trees:

join (Leaf x) = x -- since x is of type Tree a, the return value is of the correct type

join (Node l r) = Node (join l) (join r)

Comment Source:a) So first, we must define an \$$\eta \$$ for this Monad. In this case, it will receive a value of A and returns a Tree of A, as such, it should map the value to the leaf: \$$\eta(a) \mapsto A \$$ The join function \$$\mu \$$ will map a Tree of Tree of A and should return a Tree of A: \$$\mu : A + (A + X \times X) \times (A + X \times X) \rightarrow A + X \times X \$$ You can enumerate some situations: 1. If it receives a leaf, this leaf will contain a Tree of A, so we can just return the content of this leaf: \$$A \mapsto A \$$ 2. If it receives a node \$$X \times X \$$, the left and right children will be of type Tree of Tree of A, but we should return a new node with the left and right children being of the type Tree of A. Well...we do have a function that does that for us: \$$X \mapsto \mu(X) \$$ b) In Haskell the Data Structure would be represented as: > Tree a = Leaf a | Node (Tree a) (Tree a) The return should create a singleton tree with only a single leaf: > return x = Leaf x And the join operation will collapse a Tree of Trees: > join (Leaf x) = x -- since x is of type Tree a, the return value is of the correct type > join (Node l r) = Node (join l) (join r)