03 March 2015 6 6K Report

For a particular application area, I found a need for a "monadic tree", defined essentially as follows:

Let M be a monad (as in functional programming).

Let an MTree[E] be the least fixed point (in N) of N[E] = M[E or N[E]], where "or" is shorthand for an Either bifunctor.

For example, if M is Set, then SetTree = Set[E or SetTree[E]] is a model of a tree  of arbitrary, but finite, depth and arbitrary (possibly infinite) breadth where there is no order among branches, and all the leaves are of type E.

I have not found any mention of this monad among the references I am familiar with, or through googling. I needed to be sure it was a monad, so I wrote a proof of the monad laws for myself[1] and also tested the monad laws through some implementations [2]. But I find it hard to believe that no one has created this monad before. Is there a publication already in the literature proving that this recursive definition does generate a monad from any other monad?

Also, my proof is only applicable to M-trees of finite depth, and I am curious about the infinite depth trees that could be generated from this recursion. But I am not familiar with the category-theoretical methods that might be used to investigate it.

[1] https://github.com/API4KBs/api4kbs/blob/currying/Monad_Trees.pdf

[2] https://github.com/ag-csw/Java4CL

Similar questions and discussions