In Category Theory, the List functor is the Free Monoid over a given type (i.e. object) T. One can then consider the category of endofunctors over types and define a monad over the functor List, where the $\mu$ natural transformation is responsible for flattening the list of lists into a simple list (e.g. [[1],[2],[3]] -> [1,2,3]).
Now, I'm interested in something a bit more general. I want to be able to construct list with arbitrary "nesting" and then flatten it (e.g. [1,[2,3],[[4],5]] -> [1,2,3,4,5]).
At first, I thought that this case would be covered by the List Monad… But it seems not to be the case. Indeed, if we think of [1,[2,3]], this is of type List Union{Int, List{Int}}, and not a List List Int… Thus, the $\mu$ function does not work…
Finally, my question is what is the Category Theory interpretation of such "arbitrary" list of lists.
Best Answer
You can view arbitrarily-nested lists as representing an ordered tree. This is also known as a rose tree (though that term appears to be used in several contexts). The ordered tree construction forms a monad, where the unit is given by the singleton tree, and the multiplication is given by interpreting "ordered trees whose leaves are ordered trees" simply as ordered trees. Algebraically, the list monad is given by the free monoid construction, while the ordered tree monad is given by the free (nonsymmetric) operad construction. There is a monad morphism from the ordered tree monad to the list monad, given by flattening the ordered tree: this is the flattening construction you describe.
As you suspect, the free monad on the list functor is the ordered tree monad (e.g. as mentioned in these slides).