Tree datastructures: Difference between revisions

And less instructively – just relying a little passively on the existing Data.Tree,

we might also write something like:

<lang haskell>import Data.Bifunctor (bimap, first)

import Data.Char (isSpace)

import Data.List (find)

import Data.Tree (Forest, Tree (..), drawTree)

-------- MAPPINGS BETWEEN INDENTED LINES AND TREES -------

forestFromNestLevels :: [(Int, a)] -> Forest a

forestFromNestLevels = go

where

go [] = []

go ((n, v) : xs) =

uncurry (:) $

bimap (Node v . go) go (span ((n <) . fst) xs)

indentLevelsFromLines :: [String] -> [(Int, String)]

indentLevelsFromLines xs =

let pairs = first length . span isSpace <$> xs

indentUnit = maybe 1 fst (find ((0 <) . fst) pairs)

in first (`div` indentUnit) <$> pairs

outlineFromForest ::

(String -> a -> String) ->

String ->

Forest a ->

String

outlineFromForest showRoot tabString forest =

let go indent node =

showRoot indent (rootLabel node) :

(subForest node >>= go ((<>) tabString indent))

in unlines $ forest >>= go ""

-------------------------- TESTS -------------------------

main :: IO ()

main = do

putStrLn "Trees from indented text:\n"

let trees =

forestFromNestLevels $

indentLevelsFromLines test

putStrLn $ drawTree $ Node "" trees

putStrLn "Indented text from trees:\n"

putStrLn $ outlineFromForest (<>) " " trees

test :: [String]

test =

[ "RosettaCode",

" rocks",

" code",

" comparison",

" wiki",

" mocks",

" trolling",

"Some lists",

" may",

" be",

" irregular"

]</lang>

{{Out}}

<pre>Trees from indented text:

|

+- RosettaCode

| |

| +- rocks

| | |

| | +- code

| | |

| | +- comparison

| | |

| | `- wiki

| |

| `- mocks

| |

| `- trolling

|

`- Some lists

|

+- may

|

+- be

|

`- irregular

Indented text from trees:

RosettaCode

rocks

code

comparison

wiki

mocks

trolling

Some lists

may

be

irregular</pre>