Most concise way to fold tree structures

Question

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.

Answer 1

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.

Answer 2

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#

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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))