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

- All Categories 2.4K
- Chat 505
- Study Groups 21
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 2
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- Baez ACT 2019: Online Course 339
- Baez ACT 2019: Lectures 79
- Baez ACT 2019: Exercises 149
- Baez ACT 2019: Chat 50
- UCR ACT Seminar 4
- General 75
- Azimuth Code Project 111
- Statistical methods 4
- Drafts 10
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 148
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 718

Options

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)`