101companies

Headline

A tree with an arbitrary number of sub-trees per node

Illustration

Such a tree could carry information in all nodes, in which case we speak of a node-labeled rose tree: 

data NLTree a = NLTree a [NLTree a]
  deriving (Eq, Show, Read)

For instance: 

sampleNLTree = 
  NLTree 1 [
    NLTree 2 [],
    NLTree 3 [NLTree 4 []],
    NLTree 5 []]

Labeling in a rose tree may also be limited to the leaves, in which case we speak of a leaf-labeled rose tree: 

data LLTree a = Leaf a | Fork [LLTree a]
  deriving (Eq, Show, Read)

For instance: 

sampleLLTree = 
  Fork [
    Leaf 1,
    Fork [Leaf 2],
    Leaf 3]

For what it matters, we can make the type constructors for rose trees functors and foldable types: 

instance Functor NLTree
  where
    fmap f (NLTree x ts) = NLTree (f x) (fmap (fmap f) ts)

instance Foldable NLTree
  where
    foldr f z (NLTree x ts) = foldr f z (x : concat (fmap toList ts))

instance Functor LLTree
  where
    fmap f (Leaf x) = Leaf (f x)
    fmap f (Fork ts) = Fork (fmap (fmap f) ts)

instance Foldable LLTree
  where
    foldr f z (Leaf x) = x `f` z
    foldr f z (Fork ts) = foldr f z (concat (fmap toList ts))

The fmap definitions basically push fmap into the subtrees while using the list instance of fmap to process lists of subtrees. The foldr definitions basically reduce foldr on trees to 'foldr' on lists by apply toList on subtrees. Here we note that toList can be defined for any foldable type as follows: 

toList :: Foldable t => t a -> [a]
toList = foldMap (\x->[x])

(C) 2012-2024 softlang.org and contributors

There are no revisions for this page.

User contributions

    This user never has never made submissions.

    User edits

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.

    Syntax for editing wiki

    For you are available next options:

    will make text bold.

    will make text italic.

    will make text underlined.

    will make text striked.

    will allow you to paste code headline into the page.

    will allow you to link into the page.

    will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

    will allow you to paste image into the page.

    is list with bullets.

    is list with numbers.

    will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

    will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

    will allow your to insert code snippets from @worker.