[Haskell-cafe] Multiway tree vs rose tree

[Ivan Lazar Miljenovic]

On 11 May 2015 at 22:50, Tara Athan <taraathan at gmail.com> wrote:
> Hi - I am new to this list, and the only archive I could find is the Mailman
> archive, which is next to impossible to search. So this may be a topic that
> has been previously discussed, I don't know...
>
> The documentation at
> https://hackage.haskell.org/package/containers-0.3.0.0/docs/Data-Tree.html
> says that a rose tree is another name for multiway tree. But this is not
> true according to my understanding of the accepted definition in the CS
> literature (see e.g.
> http://doc.utwente.nl/66626/1/db-utwente-0000003528.pdf)
> Rose trees do not have labels at the nodes, only at the leaves (aka tips).

There are various different definitions of tree structures (I once
started a literature review of this, but never finished it).  Note
that if you allow values in all nodes, you can always represent a tree
where only leaves have values of type `a' as an arbitrary tree with
nodes of type `Maybe a' (but you can't statically enforce this, at
least with the definition in Data.Tree: for that, you would have to
generalise the tree structure even more to have a distinct type
variable just for the leaf nodes with a new constructor, thus
complicating usage of the data structure).


-- 
Ivan Lazar Miljenovic
Ivan.Miljenovic at gmail.com
http://IvanMiljenovic.wordpress.com