Tree datastructures: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: added syntax colouring the hard way, phix/basics) |
(→{{header|Haskell}}: added solution) |
||
Line 295: | Line 295: | ||
Round trip test satisfied? true |
Round trip test satisfied? true |
||
</pre> |
</pre> |
||
=={{header|Haskell}}== |
|||
The task is all about the isomorphism between different representations of a nested list structure. Therefore the solution is given in terms of the isomorphisms. |
|||
<lang haskell>{-# LANGUAGE FlexibleInstances #-} |
|||
{-# LANGUAGE MultiParamTypeClasses #-} |
|||
{-# LANGUAGE UndecidableSuperClasses #-} |
|||
{-# LANGUAGE TypeApplications #-} |
|||
import Data.List (span) |
|||
-- A nested tree structure. |
|||
-- Using `Maybe` allows encoding several zero-level items |
|||
-- or irregular lists (see test example) |
|||
data Nest a = Nest (Maybe a) [Nest a] |
|||
deriving Eq |
|||
instance Show a => Show (Nest a) where |
|||
show (Nest (Just a) []) = show a |
|||
show (Nest (Just a) s) = show a ++ show s |
|||
show (Nest Nothing []) = "\"\"" |
|||
show (Nest Nothing s) = "\"\"" ++ show s |
|||
-- An indented tree structure. |
|||
type Indent a = [(Int, a)] |
|||
-- class for isomorphic types |
|||
class Iso b a => Iso a b where |
|||
from :: a -> b |
|||
-- A bijection from nested form to indent form |
|||
instance Iso (Nest a) (Indent a) where |
|||
from = go (-1) |
|||
where |
|||
go n (Nest a t) = |
|||
case a of |
|||
Just a -> (n, a) : foldMap (go (n + 1)) t |
|||
Nothing -> foldMap (go (n + 1)) t |
|||
-- A bijection from indent form to nested form |
|||
instance Iso (Indent a) (Nest a) where |
|||
from = revNest . foldl add (Nest Nothing []) |
|||
where |
|||
add t (d,x) = go 0 t |
|||
where |
|||
go n (Nest a s) = |
|||
case compare n d of |
|||
EQ -> Nest a $ Nest (Just x) [] : s |
|||
LT -> case s of |
|||
h:t -> Nest a $ go (n+1) h : t |
|||
[] -> go n $ Nest a [Nest Nothing []] |
|||
GT -> go (n-1) $ Nest Nothing [Nest a s] |
|||
revNest (Nest a s) = Nest a (reverse $ revNest <$> s) |
|||
-- A bijection from indent form to a string |
|||
instance Iso (Indent String) String where |
|||
from = unlines . map process |
|||
where |
|||
process (d, s) = replicate (4*d) ' ' ++ s |
|||
-- A bijection from a string to indent form |
|||
instance Iso String (Indent String) where |
|||
from = map process . lines |
|||
where |
|||
process s = let (i, a) = span (== ' ') s |
|||
in (length i `div` 4, a) |
|||
-- A bijection from nest form to a string via indent form |
|||
instance Iso (Nest String) String where |
|||
from = from @(Indent String) . from |
|||
-- A bijection from a string to nest form via indent form |
|||
instance Iso String (Nest String) where |
|||
from = from @(Indent String) . from</lang> |
|||
Testing: |
|||
<lang haskell>test = unlines |
|||
[ "RosettaCode" |
|||
, " rocks" |
|||
, " code" |
|||
, " comparison" |
|||
, " wiki" |
|||
, " mocks" |
|||
, " trolling" |
|||
, "Some lists" |
|||
, " may" |
|||
, " be" |
|||
, " irregular" ] |
|||
itest :: Indent String |
|||
itest = from test |
|||
ttest :: Nest String |
|||
ttest = from test</lang> |
|||
<pre>λ> mapM_ print itest |
|||
(0,"RosettaCode") |
|||
(1,"rocks") |
|||
(2,"code") |
|||
(2,"comparison") |
|||
(2,"wiki") |
|||
(1,"mocks") |
|||
(2,"trolling") |
|||
(0,"Some lists") |
|||
(3,"may") |
|||
(2,"be") |
|||
(1,"irregular") |
|||
λ> ttest |
|||
""["RosettaCode"["rocks"["code","comparison","wiki"],"mocks"["trolling"]], |
|||
"Some lists"[""[""["may"],"be"],"irregular"]] |
|||
λ> putStr $ from (from test :: Indent String) |
|||
RosettaCode |
|||
rocks |
|||
code |
|||
comparison |
|||
wiki |
|||
mocks |
|||
trolling |
|||
Some lists |
|||
may |
|||
be |
|||
irregular |
|||
λ> putStr $ from (from test :: Nest String) |
|||
RosettaCode |
|||
rocks |
|||
code |
|||
comparison |
|||
wiki |
|||
mocks |
|||
trolling |
|||
Some lists |
|||
may |
|||
be |
|||
irregular |
|||
λ> test == from (from test :: Nest String) |
|||
True |
|||
λ> test == from (from test :: Indent String) |
|||
True |
|||
λ> itest == from (from itest :: String) |
|||
True |
|||
λ> itest == from (from itest :: Nest String) |
|||
True |
|||
λ> ttest == from (from ttest :: String) |
|||
True |
|||
λ> ttest == from (from ttest :: Indent String) |
|||
True</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |