7
1
Background (F#)
Let there be trees:
type Tree<'T> = Node of 'T * Tree<'T> list
Now lets fold them nicely with a function called...
foldTree f:('a -> 'b -> 'c) -> g:('c -> 'b -> 'b) -> a:'b -> t:Tree<'a> -> 'c
...taking two functions f
and g
, an initial state a
and of course a tree structure t
. Similar to the well known function fold which operates on lists, this function should "merge" siblings with g
and parents with their children with f
resulting in an accumulated simple value.
Example (F#)
The tree...
// 1
// / \
// 2 3
// / \ \
// 4 5 6
let t = Node (1, [Node (2, [Node (4, []); Node (5, [])]); Node (3, [Node (6, [])])])
...passed to foldTree
with the operators for addition and multiplication along with the initial state 1
...
let result = foldTree (+) (*) 1 t
// = (1 + ((2 + ((4 + a) * ((5 + a) * a))) * ((3 + ((6 + a) * a)) * a)))
// = (1 + ((2 + ((4 + 1) * ((5 + 1) * 1))) * ((3 + ((6 + 1) * 1)) * 1)))
...should return the value 321
to result
.
The Challenge
In any programming language, define the function foldTree
in the most concise way you can come up with. Fewest number of characters wins.
1I don't understand how folding is being generalized to trees. In what order do the mergings happens? Could you please give a worked example? Also, are our answers allowed to use imperative constructs? – xnor – 2015-05-18T23:43:56.720
1@xnor each subtree is folded recursively; then the list of results is folded by a right-fold of
g
with starting valuea
, and combined with the node's value throughf
. Judging by the types. – Will Ness – 2015-05-19T00:49:06.187Please some more examples? – edc65 – 2015-05-19T05:50:01.237
@xnor, personally I'm most interested in functional approaches. However, I will not dismiss any answer using other programming paradigms. – Good Night Nerd Pride – 2015-05-19T06:40:18.957
@edc65, I extended the example a little bit. Hope that clears things up for you. – Good Night Nerd Pride – 2015-05-19T17:52:33.533
1The title seems to conflict with the statement In any programming language... – Kyle Kanos – 2015-05-19T20:29:12.100
That's correct. I changed it. – Good Night Nerd Pride – 2015-05-20T06:02:55.117