How to traverse a tree in Clojure while collecting the value from each node node? -


i want create function collects value each node in binary tree. in clojuredocs, found several functions traversing tree/graph, such tree-seq, prewalk, , postwalk.

https://clojuredocs.org/clojure.core/tree-seq

https://clojuredocs.org/clojure.walk/prewalk

https://clojuredocs.org/clojure.walk/postwalk

can of these used accumulate value of nodes traversed? clojure newby, don't see how it. if know how (in clojure or similar lispy language), please show me. ideally, answer understandable clojure newby;-)

my binary tree represented nodes this: (value left-child right-child). example:

( 2 (7 nil nil) (88 (5 nil nil) nil) )

from example, i'd function return (2 7 88 5).

note: traversal method isn't important. want learn technique collecting node values.

well, tree-seq give node sequence (of depth first walk). can other transformation on it, including (map some-value-extractor-fn (tree-seq ... values in each node. need pick tree representation , appropriate functions representation tree-seq can know internal node , children are. instance, using definition of tree nested list:

nested list tree

the nodes our tree branch lists, can identify using list?.their children values following first, i.e. rest. can define tree-seq using standard functions:

(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )      (tree-seq list? rest))

but has bit of garbage - each nil appears member of seq, each value we're interested in appears both in list node , member in , on. can clean filter or remove - instance can discard leaf values , take internal nodes:

(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )      (tree-seq list? rest)      (filter list?)) ;;=> ((2 (7 nil nil) (88 (5 nil nil) nil)) (7 nil nil) (88 (5 nil nil) nil) (5 nil nil))

and map first on those:

(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )      (tree-seq list? rest)      (filter list?)      (map first)) ;;=>(2 7 88 5)

alternatively try discard internal , nil nodes of tree, taking leaves value: 

(->> '( 2 (7 nil nil) (88 (5 nil nil) nil) )      (tree-seq list? seq)      (remove (some-fn list? nil?))) ;;=>(2 7 88 5)

note in strategy had use seq rather rest, want first value in list child of node. (some-fn list? nil?) bit of higher order functions - builds function checks if input satisfies either of predicates list? or nil? (or both).

nested map tree

if want maybe more general tree definition, each node can contain multiple values plus variable number of children, can define tree nested maps: {:value 2 :children [{:value 7} {:value 88 :children [{:value 5}]}]}

in case, looking @ maps nodes simplest. our possibly branching nodes maps - check map?. stored children in key :children, keyword , function. use function children. 

(->> {:value 2 :children [{:value 7} {:value 88 :children [{:value 5}]}]}       (tree-seq map? :children))  ;;=> ({:value 2, :children [{:value 7} {:value 88, :children [{:value 5}]}]} {:value 7} {:value 88, :children [{:value 5}]} {:value 5})

and need map on nodes data want out of them: 

(->> {:value 2 :children [{:value 7} {:value 88 :children [{:value 5}]}] }       (tree-seq map? :children)      (map :value)) ;;=> (2 7 88 5)

Comments

Post a Comment

Popular posts from this blog

c# - Validate object ID from GET to POST -

i have method allows user access comment have made on site. have post method lets them update comment. my normal solution send entire comment model through, let them update it, update on database when post back. involve sending commentid through in hiddenfor , can manipulated. how can verify commentid sent in get method same i'm getting in post , not able alter comment wish? how can verify commentid sent in method same i'm getting in post? basically have validate following things in post - user logged-in user. authenticated users post comments. commentid in post , should valid commentid , should present in database. userid associated logged-in user should same userid associated comment . comment should contain userid column, can check @ time of update. to make sure update happens comment has been sent in get - hold commentid in session , in post action compare commentid value in session .
Read more

node.js - Custom Model Validator SailsJS -

when using custom model validator checks record within model. return within spread doesn't seem end control flow. //post.js model /** * custom validator **/ types: { isuservalid: function(user_id) { var promise = require('bluebird'); promise.all([ user.findone({id: user_id}) ]) .spread(function(user) { console.log(user); if (user === null || user === undefined) { console.log('failed'); return false; }else{ console.log('passed'); return true; } }); } }, my response standard validation failed response. { "error": "e_validation", "status": 400, "summary": "1 attribute invalid", "model": "post", "invalidattributes": { "owner": [ { "rule": "isuservalid", ...
Read more

php - Find a regex to take part of Email -

i have following emails need extract part from: bestellnummer xxx: 1 von xxx, 1er pack ------------- anfang der nachricht ------------- foo bar baz foo bar baz // <<<<< need text here ------------- ende der nachricht ------------- ------------- anfang der nachricht ------------- foo bar baz foo bar baz ------------- ende der nachricht ------------- there 0 unlimited occurences of ------------- anfang der nachricht ------------- ------------- ende der nachricht ------------- and i'm able extract first part regex: $re = "/------------- .*? -------------.?(.*?).?------------- .*? -------------/s"; but, i'm quite new on learning regex, i'm pretty sure there must better regex extract part (foo bar baz foo bar baz) of text between ------------- anfang der nachricht ------------- ------------- ende der nachricht ------------- as can in different languages, i'm using .? to match between hyphens. i...
Read more