Tree datastructures: Difference between revisions
Content added Content deleted
m (→Functional) |
|||
Line 29: | Line 29: | ||
Show all output on this page. |
Show all output on this page. |
||
=={{header|Haskell}}== |
|||
Using the rose tree constructor in the standard Data.Tree module. |
|||
Parses the initial tree from outline text, and writes out the flat |
|||
and nested structures in a minimal JSON format: |
|||
<lang haskell>{-# LANGUAGE OverloadedStrings #-} |
|||
import qualified Data.Text.Lazy.Encoding as E |
|||
import qualified Data.Text.Lazy.IO as T |
|||
import qualified Data.Text.Lazy as T |
|||
import Control.Arrow (first) |
|||
import Data.Char (isSpace) |
|||
import Data.Bool (bool) |
|||
import Data.Tree |
|||
import Data.Aeson |
|||
import Data.Aeson.Text |
|||
-- TREES -> LIST OF LEVELS -> TREES |
|||
nestLevelsFromForest :: [Tree a] -> [(Int, a)] |
|||
nestLevelsFromForest xs = |
|||
let go level node = |
|||
(level, rootLabel node) : (subForest node >>= go (succ level)) |
|||
in xs >>= go 0 |
|||
forestFromNestLevels |
|||
:: Ord t |
|||
=> [(t, a)] -> Forest a |
|||
forestFromNestLevels pairs = |
|||
let go [] = [] |
|||
go ((n, s):xs) = |
|||
let (firstTreeLines, rest) = span ((n <) . fst) xs |
|||
in Node s (go firstTreeLines) : go rest |
|||
in go pairs |
|||
-- INITIAL PARSE TREE OF OUTLINE -------------------------- |
|||
nestLevelsFromLines xs = |
|||
let pairs = T.span isSpace <$> xs |
|||
indentUnit = |
|||
foldr |
|||
(\x a -> |
|||
let w = (T.length . fst) x |
|||
in bool a w (w < a && 0 < w)) |
|||
maxBound |
|||
pairs |
|||
in first (flip div indentUnit . T.length) <$> pairs |
|||
-- DISPLAY OF JSON SERIALISATION -------------------------- |
|||
showJSON |
|||
:: ToJSON a |
|||
=> a -> T.Text |
|||
showJSON = E.decodeUtf8 . encode . toJSON |
|||
-- TEST --------------------------------------------------- |
|||
forestA :: Forest T.Text |
|||
forestA = (forestFromNestLevels . nestLevelsFromLines) (T.lines outline) |
|||
nestLevels :: [(Int, T.Text)] |
|||
nestLevels = nestLevelsFromForest forestA |
|||
forestB :: [Tree T.Text] |
|||
forestB = forestFromNestLevels nestLevels |
|||
main :: IO () |
|||
main = |
|||
mapM_ |
|||
T.putStrLn |
|||
[ "Initial parse tree of outline:\n" |
|||
, showJSON forestA |
|||
, "\nList of nest levels from parse tree:\n" |
|||
, showJSON nestLevels |
|||
, "\nTree rebuilt from nest levels:\n" |
|||
, showJSON forestB |
|||
] |
|||
outline :: T.Text |
|||
outline = |
|||
"RosettaCode\n\ |
|||
\ rocks\n\ |
|||
\ code\n\ |
|||
\ comparison\n\ |
|||
\ wiki\n\ |
|||
\ knocks\n\ |
|||
\ golfing"</lang> |
|||
{{Out}} |
|||
<pre>Initial parse tree of outline: |
|||
[["RosettaCode",[["rocks",[["code",[]],["comparison",[]],["wiki",[]]]],["knocks",[["golfing",[]]]]]]] |
|||
List of nest levels from parse tree: |
|||
[[0,"RosettaCode"],[1,"rocks"],[2,"code"],[2,"comparison"],[2,"wiki"],[1,"knocks"],[2,"golfing"]] |
|||
Tree rebuilt from nest levels: |
|||
[["RosettaCode",[["rocks",[["code",[]],["comparison",[]],["wiki",[]]]],["knocks",[["golfing",[]]]]]]]</pre> |
|||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |