It looks like you're new here. If you want to get involved, click one of these buttons!
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.
(b) Implement this monad in Haskell
Comments
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:
\( A \mapsto A \)
\( X \mapsto \mu(X) \)
b)
In Haskell the Data Structure would be represented as:
The return should create a singleton tree with only a single leaf:
And the join operation will collapse a Tree of Trees:
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)