Tree from nesting levels: Difference between revisions
→{{header|Haskell}}: Added a lossless round-trip :: treeFromSparseLevels ⇄ sparseLevelsFromTree
(Added C++ implementation) |
(→{{header|Haskell}}: Added a lossless round-trip :: treeFromSparseLevels ⇄ sparseLevelsFromTree) |
||
Line 342:
For display purposes, we can either show the list of Tree records directly, or use the drawForest and drawTree functions defined in the standard Data.Tree module.
We can '''reverse''' the translation, from tree back to sparse list, without loss of information, by using a standard fold.
See ''sparseLevelsFromTree'' below:
<lang haskell>{-# LANGUAGE TupleSections #-}
import Data.Bifunctor (bimap)
import Data.Tree (Forest, Tree (..), drawTree, foldTree)
------------------ TREE FROM NEST LEVELS -----------------
treeFromSparseLevels =
Node Nothing
. forestFromNestLevels
. rooted
. normalised
sparseLevelsFromTree :: Tree (Maybe Int) -> [Int]
sparseLevelsFromTree = foldTree go
where
go Nothing xs = concat xs
go (Just x) xs = x : (concat xs)
forestFromNestLevels :: [(Int, a)] -> Forest a
Line 368 ⟶ 377:
main :: IO ()
main =
mapM_
putStrLn ("From: " <> show xs)
in
>>
( "Back to:
)
----------- MAPPING TO A STRICTER DATA STRUCTURE ---------
Line 407 ⟶ 416:
| otherwise = (x, Just x) : normalised (y : xs)</lang>
{{Out}}
<pre>From: []
Nothing
Back to: []
From: [1,2,4]
Nothing
|
Line 422 ⟶ 433:
`- Just 4
Back to: [1,2,4]
From: [3,1,3,1]
Nothing
|
Line 440 ⟶ 453:
`- Just 1
Back to: [3,1,3,1]
From: [1,2,3,1]
Nothing
|
Line 452 ⟶ 467:
`- Just 1
Back to: [1,2,3,1]
From: [3,2,1,3]
Nothing
|
Line 470 ⟶ 487:
`- Just 3
Back to: [3,2,1,3]
From: [3,3,3,1,1,3,3,3]
Nothing
|
Line 495 ⟶ 514:
|
`- Just 3
Back to: [3,3,3,1,1,3,3,3]</pre>
=={{header|Julia}}==
|