Haskell How to convert general tree to Data.Tree -


i have declared general tree follows

data generaltree = emptytree | node [generaltree a]

i have built instance of generaltree. want convert tree type declared in data.tree. how do it?

i want write function follows type

converttree :: generaltree -> tree

but i'm having trouble dealing empty tree because there no counterpart in data.tree definition of tree.

the maybe can use @ top level of tree, due definition of tree a. avoid conversion of 'pure' emptytree, sound there can't equivalent value in targeted type. said in first answer way accommodate later occurrence of emptytree take advantage of linear recursive nature of list allowing easy way skip them.

finally, top node must wrap result maybe type avoid conversion of pure emptytree. then, can reasonably work on sub-forest without worry.

this lead version, easiest follow. 

convertgtree :: generaltree -> maybe (tree a) convertgtree emptytree             = nothing convertgtree (gnode forestgtree) = (node forest)            forest = buildforest forestgtree       buildforest :: [generaltree a] -> [tree a]       buildforest []     = []       buildforest (x:xs) = case x of           gnode n forest -> (node n (buildforest forest)) : (buildforest xs)          _              -> buildforest xs

an illustration test, 

>>> let testgeneraltree = gnode "0" [gnode "1" [gnode "2" [], emptytree], gnode "3" [emptytree]] >>> putstrln . drawtree . fromjust . convertgtree $ testgeneraltree 0 | +- 1 |  | |  `- 2 | `- 3

using unfoldtree , returning tree (maybe a)

first, avoid use of node data constructor it's in use tree data type or encounter name's collision. why we've chosen redefine this,

data generaltree = emptytree | gnode [generaltree a]      deriving (show)

you can deal emptytree mean of intermediate maybe type.
start, pass buildsafetree function use unfoldtree behind scene.
helper manage case , return nothing when encounter emptytree value.
when safe tree build, can clean using cleansafetree, trick reside in cleanforest skip nothing value case of statement.

the code below, 

testgeneraltree = gnode "0" [gnode "1" [gnode "2" [], emptytree], gnode "3" [emptytree]]  converttree :: generaltree -> tree converttree = cleansafetree . buildsafetree  buildsafetree :: generaltree -> tree (maybe a) buildsafetree =    unfoldtree helper             helper :: generaltree -> (maybe a, [generaltree a])        helper emptytree       = (nothing, [])        helper (gnode trees) = (just a, trees)   cleansafetree :: tree (maybe a) -> tree  cleansafetree tree@(node (just root) forest) =    node root (cleanforest forest)             cleanforest :: forest (maybe a) -> forest       cleanforest []     = []       cleanforest (x:xs) = case x of           node nothing _      -> cleanforest xs         node (just x) trees -> (node x (cleanforest trees)) : (cleanforest xs)

some test, 

>>> testgeneraltree  gnode "0" [gnode "1" [gnode "2" [],emptytree],gnode "3" [emptytree]]  >>> putstrln . drawtree .  converttree $ testgeneraltree 0 | +- 1 |  | |  `- 2 | `- 3  >>> putstrln . drawtree . fmap show . buildsafetree $ testgeneraltree "0" | +- "1" |  | |  +- "2" |  | |  `- nothing | `- "3"    |    `- nothing

using unfoldforest shorter. 

converttrees :: generaltree -> tree converttrees (gnode forest) =    node (cleanforest . unfoldforest helper $ forest)            -- build forest of tree (maybe a) generaltree       totreemaybe :: generaltree -> (maybe a, [generaltree a])       totreemaybe emptytree           = (nothing, [])       totreemaybe (gnode subforest) = (just , subforest)       -- clean maybe a, forest of tree maybe       frommaybe :: forest (maybe a) -> forest       frommaybe []     = []       frommaybe (x:xs) = case x of             node nothing _     -> cleanforest xs         node (just x) trees -> (node x (cleanforest trees)) : (cleanforest xs)

a monadic version using unfoldtreem return maybe (tree a)

a solution using unfoldtreemonadic 

convertmonadictrees :: generaltree -> maybe (tree a) convertmonadictrees = unfoldtreem helper      helper :: generaltree -> maybe (a, [generaltree a])      helper emptytree       = nothing     helper (gnode trees) = (a, trees)

the main difference, it's returning nothing if generaltree contain emptytree value discarded. 

>>> testgeneraltree2  gnode 0 [gnode 1 [gnode 2 [],emptytree],gnode 3 [emptytree]] >>> convertmonadictrees testgeneraltree2 nothing

Comments

Post a Comment

Popular posts from this blog

linux - xterm copying to CLIPBOARD using copy-selection causes automatic updating of CLIPBOARD upon mouse selection -

i've tried various ways coerce xterm (versions 285 , 292) copy selection clipboard clipboard whenever press ctrl-shift-c. promising way far has been, in ~/.xresources, put this: xterm*vt100.translations: #override \ ctrl shift <keypress> c: copy-selection(clipboard) \n\ ctrl shift <keypress> v: insert-selection(clipboard) ctrl-shift-v works perfectly, copying has nuance... if restart xterm, highlighting text puts things in primary clipboard; expected, proper, default behavior. if hit ctrl-shift-c, copies current selection clipboard clipboard. the bug, however, if highlight text after first time pressed ctrl-shift-c, you'll see highlighting copies both primary and clipboard. cannot figure out how stop xterm updating clipboard upon selection... , doesn't make sense me in first place. i said, @ specific point in time, copy selection clipboard... yet starts updating automatically upon selection after doing once... anyone have workaround...
Read more

c++ - qgraphicsview horizontal scrolling always has a vertical delta -

Image
i've subclassed qgraphicsview custom canvas used in cad application. i've reimplemented qgraphicsview::wheelevent check keyboard modifiers control key and, if control key pressed, zoom. i'm trying implement horizontal scroll when user holds shift , uses wheel. the problem i'm having horizontal scrolling always scrolls 0.279. not huge problem, hugely annoying , points else being wrong. so, here questions: is right way implement horizontal scrolling? if not, is? how eliminate delta of 0.279? thanks in advance. code , sample output below void myview::zoom(int delta) { double factor = pow(1.2, delta/abs(delta)); this->scale(factor, factor); } void myview::scrollhorizontal(int level) { qpointf center = maptoscene(viewport()->rect().center()); qdebug() << "center: " << center.x() << ", " << center.y(); centeron(qpointf(center.x() - level, center.y())); } void myview::wheelevent(qwheeleve...
Read more