7
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I 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? \$\endgroup\$ – xnor May 18 '15 at 23:43
  • 1
    \$\begingroup\$ @xnor each subtree is folded recursively; then the list of results is folded by a right-fold of g with starting value a, and combined with the node's value through f. Judging by the types. \$\endgroup\$ – Will Ness May 19 '15 at 0:49
  • \$\begingroup\$ Please some more examples? \$\endgroup\$ – edc65 May 19 '15 at 5:50
  • \$\begingroup\$ @xnor, personally I'm most interested in functional approaches. However, I will not dismiss any answer using other programming paradigms. \$\endgroup\$ – Good Night Nerd Pride May 19 '15 at 6:40
  • 1
    \$\begingroup\$ The title seems to conflict with the statement In any programming language... \$\endgroup\$ – Kyle Kanos May 19 '15 at 20:29
6
\$\begingroup\$

Haskell, 37 35:

data T a=a:*[T a]

(f%g)z(x:*t)=x`f`foldr(g.(f%g)z)z t

not counting the type definition. With it, 54 52 (shortened by using infix operator, similarly to the answer by proud haskeller, but in a different way).

Ungolfed:

data Tree a = Node a [Tree a]

foldTree :: (a -> b -> c) -> (c -> b -> b) -> b -> Tree a -> c
foldTree f g z (Node x t) = f x $ foldr (g . foldTree f g z) z t
                       -- = f x . foldr g z . map (foldTree f g z) $ t

--      1
--     / \
--    2   3
--   / \   \
--  4   5   6

t = Node 1 [Node 2 [Node 4 [], Node 5 []],
            Node 3 [Node 6 []]]

result = foldTree (+) (*) 1 t   -- ((+)%(*)) 1 t        {-
       = 1 + product [2 + product[ 4 + product[], 5 + product[]],
                      3 + product[ 6 + product[]]]
       = 1 + product [2 + 5*6, 3 + 7]
       = 321                                            -}

   -- product [a,b,c,...,n] = foldr (*) 1 [a,b,c,...,n] 
   --     = a * (b * (c * ... (n * 1) ... ))             

This is the redtree ("reduce tree") function from John Hughes paper, "Why Functional Programming Matters", where it is presented in a more verbose formulation.

\$\endgroup\$
  • \$\begingroup\$ Interesting... I'm looking at the paper right now, but I can't find this particular definition of foldtree in there. Are you referencing the version of the paper published in “Research Topics in Functional Programming” ed. D. Turner, Addison-Wesley, 1990, pp 17–42.? \$\endgroup\$ – Good Night Nerd Pride May 18 '15 at 23:13
  • 1
    \$\begingroup\$ Ok, that's basically the same three-liner he gave in the updated version of the paper.I found this shortcut with foldr while learning functional programming with Hughes' paper and was wondering why he didn't use it. Especially considering that his defintion of foldtree is a bit loose about types there. Turns out my finding wasn't that special after all :( \$\endgroup\$ – Good Night Nerd Pride May 18 '15 at 23:23
  • 1
    \$\begingroup\$ change that frowny to smiley and all will be okay! :) it's good that you discovered this yourself too. the paper was first written very long time ago, in 1984. \$\endgroup\$ – Will Ness May 18 '15 at 23:25
  • 2
    \$\begingroup\$ 2 bytes to save: use an infix constructor instead of N, e.g. :# and f x$... instead of f x(...). \$\endgroup\$ – nimi May 19 '15 at 19:09
  • \$\begingroup\$ interestingly, when i was thinking of my solution, I came up with that improvement too but I dropped it because the two improvements couldn't be used together. oh well. \$\endgroup\$ – proud haskeller May 28 '15 at 12:40
4
\$\begingroup\$

F#, 70 61

let rec r f g a (Node(n,c))=f n<|List.foldBack(g<<r f g a)c a

Not going to win the contest, but I think you can't get less with F#

\$\endgroup\$
3
\$\begingroup\$

Haskell, 35

data T a=a:>[T a]
h(%)g a(e:>l)=e%foldr(g.h(%)g a)a l

the data type declaration is not counted.

\$\endgroup\$
3
\$\begingroup\$

Prolog, 85

Logic programming

b([],A,A). b([E|N],A,R):-b(N,A,T),c(E,A,Y),g(Y,T,R). c((C,S),A,R):-b(S,A,T),f(C,T,R).

Ungolfed

b([],A,A).
b([Element|Siblings],A,R):-
      b(Siblings,A,RSiblings),c(Element,A,RElement),
      g(RElement,RSiblings,R).

c((Parent,Children),A,R):-
      b(Children,A,RChildren),f(Parent,RChildren,R).

Functions f and g

f(A,B,R):-R is A+B.
g(A,B,R):-R is A*B.

Example

c((1,[(2,[(4,[]),(5,[])]),(3,[(6,[])])]),1,R).

Try it online

Edit: correction of error signaled by Will Ness, thanks for the feedback

\$\endgroup\$
1
\$\begingroup\$

Mathematica, 48

Head@#~#2~Fold[##3,#0[x,##2]~Table~{x,List@@#}]&

Example:

In[1]:= foldTree = Head@#~#2~Fold[##3,#0[x,##2]~Table~{x,List@@#}]&;

In[2]:= foldTree[1[2[4[], 5[]], 3[6[]]], Plus, Times, 1]

Out[2]= 321
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 62

Javascript seems functional enough, function objects can be easily defined and passed as parameters.

Define a node as an object {v:value, c:list of children}, the example tree is:

t={v:1, c:[{v:2,c:[{v:4},{v:5}]},{v:3,c:[{v:6}]}]}

(here the c is optional. Making c a mandatory field with value [] if there are no children, the fold function can be 5 chars shorter)

and the fold function is:

F=(t,a,f,g)=>{
  var r=a
  t.c && t.c.forEach(t=>r=g(r,F(t,a,f,g)))
  return f(t.v,r)
}

Golfed (there is little to golf)

F=(t,a,f,g,r=a)=>(t.c&&t.c.map(t=>r=g(r,F(t,a,f,g))),f(t.v,r))

Test In Firefox

t={v:1, c:[{v:2,c:[{v:4},{v:5}]},{v:3,c:[{v:6}]}]}

F=(t,a,f,g,r=a)=>(t.c&&t.c.map(t=>r=g(r,F(t,a,f,g))),f(t.v,r))

document.write(F(t, 1, (a,b)=>a+b, (a,b)=>a*b))

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.