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.

(b) Implement this monad in Haskell

Comments

  • 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)
Sign In or Register to comment.