Tree datastructures: Difference between revisions
→{{header|JavaScript}}
m (→Functional) |
|||
Line 29:
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}}==
| |||