{{ message }}

Instantly share code, notes, and snippets.

# ryanivandsouza/whyfp-higher-order.clj

Last active Dec 25, 2020
Why FP Matters - Part 2 ๐ - Higher-order Functions
 ;; Clojure ;; fold' f a [] = a ;; fold' f a (x:xs) = f x (fold' f a xs) (defn fold' [f a xs] (if (empty? xs) a (f (first xs) (fold' f a (rest xs))))) ;; sum'' = fold' (+) 0 (def sum'' (partial fold' + 0)) (sum'' '(1 2 3 4)) ;; mul'' = fold' (*) 1 (def mul'' (partial fold' * 1)) (mul'' '(1 2 3 4)) ;; all'' = fold' (&&) True (def all'' (partial fold' 'and true)) (all'' '(true, true, false, true)) ;; all'' = fold' (&&) True (def any'' (partial fold' 'or false)) (any'' '(true, true, false, true)) ;; lst'' = fold' (:) [] (def lst'' (partial fold' cons nil)) (lst'' '(1 2 3 4)) ;; append'' xs ys = fold' (:) ys xs (defn append'' [xs ys] (fold' cons ys xs)) (append'' '(1 2 3) '(4 5 6)) ;; map' f = fold' ((:) . f) [] (defn map' [f xs] (fold' #(cons (f %1) %2) nil xs)) (map' #(* 2 %) '(1 2 3 4)) ;; summatrix = sum'' . map' sum'' (def summatrix (comp sum'' (partial map' sum''))) (summatrix '((1 2 3 4) (1 2 3 4))) ;; data Node label = Node label [Node label] ;; foldnode' f g a (Node label children) = ;; f label (foldnodes' f g a children) (defn foldnode [f g a [label children]] (f label (foldnodes f g a children))) ;; foldnodes' f g a [] = a ;; foldnodes' f g a (node:nodes) = ;; g (foldnode' f g a node) (foldnodes' f g a nodes) (defn foldnodes [f g a nodes] (if (empty? nodes) a (g (foldnode f g a (first nodes)) (foldnodes f g a (rest nodes))))) ;; foldtree' f g a node = foldnode' f g a node (defn foldtree [f g a node] (foldnode f g a node)) (def numberNodes '(1 ((2 ((4 nil))) (5 nil)))) ;; 1 ;; + ;; | ;; 2<----->5 ;; + ;; | ;; v ;; 4 ;; sumtree' = foldtree' (+) (+) 0 (def sumtree (partial foldtree + + 0)) (sumtree numberNodes) ;; labels' = foldtree' (:) (++) [] (def labelstree (partial foldtree cons concat nil)) (labelstree numberNodes) ;; maptree' f = foldtree' (Node . f ) (:) [] (defn maptree [f xs] (foldtree #(list (f %1) %2) cons nil xs)) (maptree #(* 2 %) numberNodes)
 // C# using System; using System.Collections.Generic; using System.Linq; namespace whyfp { // data Node label = Node label [Node label] public class Node { public T Label { get; set; } public IEnumerable> Children { get; set; } } public class Program { public static Func Add = (int x, int y) => x + y; public static Func Product = (int x, int y) => x * y; public static Func And = (bool x, bool y) => x && y; public static Func Or = (bool x, bool y) => x || y; public static Func, IEnumerable> Cons(T x) => (xs) => Enumerable.Repeat(x, 1).Concat(xs); public static IEnumerable Cons2(T x, IEnumerable xs) => Cons(x)(xs); // fold' f a [] = a // fold' f a (x:xs) = f x (fold' f a xs) public static Func, U> Fold(Func f, U a) => (xs) => xs.Any() ? f(xs.First(), Fold(f, a)(xs.Skip(1))) : a; // sum'' = fold' (+) 0 public static Func, int> Sum = Fold(Add, 0); // mul'' = fold' (*) 1 public static Func, int> Mul = Fold(Product, 1); // all'' = fold' (&&) True public static Func, bool> All = Fold(And, true); // any'' = fold' (||) False public static Func, bool> Any = Fold(Or, true); // lst'' = fold' (:) [] public static IEnumerable Lst(IEnumerable xs) => Fold>(Cons2, Enumerable.Empty())(xs); // append'' xs ys = fold' (:) ys xs public static IEnumerable Append(IEnumerable xs, IEnumerable ys) => Fold>(Cons2, ys)(xs); public static Func Compose(Func f, Func g) => x => g(f(x)); // map' f = fold' ((:) . f) [] public static Func, IEnumerable> Map(Func f) => Fold>((t, us) => Compose(f, Cons)(t)(us), Enumerable.Empty()); // summatrix = sum'' . map' sum'' public static Func>, int> SumMatrix = Compose(Map(Sum), Sum); // foldtree' f g a node = foldnode' f g a node public static Func, C> FoldTree(Func f, Func g, B a) => node => FoldNode(f, g, a, node); // foldnode' f g a (Node label children) = f label (foldnodes' f g a children) public static C FoldNode(Func f, Func g, B a, Node node) => f(node.Label, FoldNodes(f, g, a, node.Children)); // foldnodes' f g a [] = a // foldnodes' f g a (node:nodes) = g (foldnode' f g a node) (foldnodes' f g a nodes) public static B FoldNodes(Func f, Func g, B a, IEnumerable> nodes) => nodes.Any() ? g(FoldNode(f, g, a, nodes.First()), FoldNodes(f, g, a, nodes.Skip(1))) : a; // maptree' f = foldtree' (Node . f ) (:) [] public static Node MapTree(Func f, Node node) => FoldTree>, Node>( (label, children) => new Node{ Label = f(label), Children = children }, Cons2, Enumerable.Empty>())(node); // sumtree' = foldtree' (+) (+) 0 public static Func, int> SumTree = FoldTree(Add, Add, 0); // labels' = foldtree' (:) (++) [] public static Func, IEnumerable, IEnumerable> Concat2 = (ys, xs) => ys.Concat(xs); public static Func, IEnumerable> Labels = FoldTree, IEnumerable>(Cons2, Concat2, Enumerable.Empty()); static void Main(string[] args) { System.Console.WriteLine(Sum(new [] { 1, 2, 3, 4})); System.Console.WriteLine(Mul(new [] { 1, 2, 3, 4})); System.Console.WriteLine(All(new [] { true, true, false, true})); System.Console.WriteLine(Any(new [] { true, true, false, true})); System.Console.WriteLine(Lst(new [] { 1, 2, 3, 4})); System.Console.WriteLine(Append(new [] { 4, 5, 6}, new [] { 1, 2, 3})); System.Console.WriteLine(Map((int x) => x * 2 )(new [] { 1, 2, 3, 4})); // [[1, 2, 3, 4], [1, 2, 3, 4]] var m = new List> { new List{ 1, 2, 3}, new List{ 1, 2, 3} }; System.Console.WriteLine(SumMatrix(m)); // numberNodes = Node 1 [Node 2 [Node 4 []], Node 5 []] // 1 // + // | // 2<----->5 // + // | // v // 4 var numberNodes = new Node { Label = 1, Children = new[]{ new Node{ Label = 2, Children = new []{ new Node{ Label = 4, Children = Enumerable.Empty>() } } }, new Node{ Label = 5, Children = Enumerable.Empty>() } } }; System.Console.WriteLine(SumTree(numberNodes)); System.Console.WriteLine(Labels(numberNodes)); System.Console.WriteLine(MapTree(x => x * x, numberNodes)); } } }
 // F# // Learn more about F# at http://fsharp.org open System // fold' f a [] = a // fold' f a (x:xs) = f x (fold' f a xs) let rec fold f a l = match l with | [] -> a | x::xs -> f x (fold f a xs) // sum'' = fold' (+) 1 let sum = fold (+) 0 printfn "%d"<| sum [1; 2; 3; 4] // mul'' = fold' (*) 1 let mul = fold (*) 1 printfn "%d"<| mul [1; 2; 3; 4] // all'' = fold' (&&) True let all = fold (&&) true printfn "%b"<| all [true; true; false; true] // any'' = fold' (||) False let any = fold (||) false printfn "%b"<| any [true; true; false; true] // lst'' = fold' (:) [] let cons x xs = x::xs let lst<'a> = fold cons [] printfn "%A"<| lst [1; 2; 3; 4] // append'' xs ys = fold' (:) ys xs let append xs ys = fold cons ys xs printfn "%A"<| append [1; 2; 3] [4; 5; 6] // map' f = fold' ((:) . f) [] let map f = fold (f >> cons) [] printfn "%A"<| map ((*) 2) [1; 2; 3; 4] // summatrix = sum'' . map' sum'' let summatrix = map sum >> sum printfn "%d" <| summatrix [[1; 2; 3; 4]; [1; 2; 3; 4]] // data Node label = Node label [Node label] type tree<'a> = | Node of 'a * list> // foldnode' f g a (Node label children) = f label (foldnodes' f g a children) // foldnodes' f g a [] = a // foldnodes' f g a (node:nodes) = g (foldnode' f g a node) (foldnodes' f g a nodes) let rec foldNode f g a node = match node with | Node(label, children) -> f label (foldNodes f g a children) and foldNodes f g a nodes = match nodes with | [] -> a | n::ns -> g (foldNode f g a n) (foldNodes f g a ns) // foldtree' f g a node = foldnode' f g a node let foldTree f g a node = foldNode f g a node // numberNodes = Node 1 [Node 2 [Node 4 []], Node 5 []] // 1 // + // | // 2<----->5 // + // | // v // 4 let numberNodes = Node(1, [Node(2, [Node(4, [])]); Node(5, [])]) // sumtree' = foldtree' (+) (+) 0 let sumTree = foldTree (+) (+) 0 printfn "%d" <| sumTree numberNodes // labels' = foldtree' (:) (++) [] let labelsTree = foldTree cons (@) [] printfn "%A" <| labelsTree numberNodes // maptree' f = foldtree' (Node . f ) (:) [] let makeNode label children = Node(label, children) let mapTree f = foldTree (f >> makeNode) cons [] // maptree' (* 2) numberNodes numberNodes |> mapTree ((*) 2) |> labelsTree |> printfn "%A" [] let main argv = 0 // return an integer exit code
 -- Haskell fold' f a [] = a fold' f a (x:xs) = f x (fold' f a xs) sum'' = fold' (+) 0 sum'' [1, 2, 3, 4] mul'' = fold' (*) 1 mul'' [1, 2, 3, 4] all'' = fold' (&&) True all'' [True, True, False, True] any'' = fold' (||) False any'' [True, True, False, True] lst'' = fold' (:) [] lst'' [1, 2, 3, 4] append'' xs ys = fold' (:) ys xs append'' [4, 5, 6] [1, 2, 3] map' f = fold' ((:) . f) [] map (* 2) [1, 2, 3, 4] sumMatrix' = sum'' . map' sum'' sumMatrix' [[1, 2, 3, 4], [1, 2, 3, 4]] data Node label = Node label [Node label] foldtree' f g a node = foldnode' f g a node foldnode' f g a (Node label children) = f label (foldnodes' f g a children) foldnodes' f g a [] = a foldnodes' f g a (node:nodes) = g (foldnode' f g a node) (foldnodes' f g a nodes) numberNodes = Node 1 [Node 2 [Node 4 []], Node 5 []] -- 1 -- + -- | -- 2<----->5 -- + -- | -- v -- 4 sumtree' = foldtree' (+) (+) 0 sumTree' numberNodes labelsTree' = foldtree' (:) (++) [] labelsTree' numberNodes maptree' f = foldtree' (Node . f ) (:) [] maptree' (* 2) numberNodes
 package com.company; import java.util.Optional; import java.util.function.Function; import java.util.function.Supplier; import java.util.stream.Collectors; import java.util.stream.Stream; @FunctionalInterface interface Function2 { public Result apply(T1 t1, T2 t2); } // data Node label = Node label [Node label] class Node{ public T label; public Supplier>> children; public Node(T label, Supplier>> children) { this.label = label; this.children = children; } } public class Main { public static void main(String[] args) { Supplier> ns = () -> Stream.of(1, 2, 3, 4); Supplier> bs = () -> Stream.of(true, true, true, true); System.out.println(sum(ns)); System.out.println(mul(ns)); System.out.println(all(bs)); System.out.println(any(bs)); System.out.println(lst(ns).get().collect(Collectors.toList())); System.out.println(append(ns, ns).get().collect(Collectors.toList())); System.out.println(sumMatrix(() -> Stream.of(ns, ns))); // numberNodes = Node 1 [Node 2 [Node 4 []], Node 5 []] Node numberNodes = new Node( 1, () -> Stream.of( new Node( 2, () -> Stream.of( new Node(4, Stream::empty))), new Node(5, Stream::empty))); System.out.println(sumTree(numberNodes)); System.out.println(labelsTree(numberNodes).get().collect(Collectors.toList())); System.out.println(labelsTree(mapTree(x -> x * 2, numberNodes)).get().collect(Collectors.toList())); } // fold' f a [] = a // fold' f a (x:xs) = f x (fold' f a xs) static S fold(Function2 fn, S a, Supplier> xs) { Optional x = xs.get().findFirst(); return x.isPresent() ? fn.apply(x.get(), fold(fn, a, () -> xs.get().skip(1))) : a; } public static Integer add(Integer x, Integer y) { return x + y; } public static Integer product(Integer x, Integer y) { return x * y; } public static Boolean and(Boolean x, Boolean y) { return x && y; } public static Boolean or(Boolean x, Boolean y) { return x || y; } // sum'' = fold' (+) 0 public static Integer sum(Supplier> xs) { return fold(Main::add, 0, xs); } // mul'' = fold' (*) 1 public static Integer mul(Supplier> xs) { return fold(Main::product, 1, xs); } // all'' = fold' (&&) True public static Boolean all(Supplier> xs) { return fold(Main::and, true, xs); } // any'' = fold' (||) False public static Boolean any(Supplier> xs) { return fold(Main::or, false, xs); } public static Supplier> cons(T x, Supplier> xs) { return () -> Stream.concat(Stream.of(x), xs.get()); } // lst'' = fold' (:) [] public static Supplier> lst(Supplier> xs) { return fold(Main::cons, Stream::empty, xs); } // append'' xs ys = fold' (:) ys xs public static Supplier> append(Supplier> xs, Supplier> ys) { return fold(Main::cons, ys, xs); } // map' f = fold' ((:) . f) [] public static Supplier> map(Function f, Supplier> xs) { return fold((x , y) -> cons(f.apply(x), y), Stream::empty, xs); } // sumMatrix' = sum'' . map' sum'' public static Integer sumMatrix(Supplier>>> m) { return sum(map(x -> sum(x), m)); } // foldtree' f g a node = foldnode' f g a node public static C foldTree(Function2 f, Function2 g, B a, Node node) { return foldNode(f, g, a, node); } // foldnode' f g a (Node label children) = f label (foldnodes' f g a children) private static C foldNode(Function2 f, Function2 g, B a, Node node) { return f.apply(node.label, foldNodes(f, g, a, node.children)); } // foldnodes' f g a [] = a // foldnodes' f g a (node:nodes) = g (foldnode' f g a node) (foldnodes' f g a nodes) private static B foldNodes(Function2 f, Function2 g, B a, Supplier>> nodes) { Optional> node = nodes.get().findFirst(); return node.isPresent() ? g.apply(foldNode(f, g, a, node.get()), foldNodes(f, g, a, () -> nodes.get().skip(1))) : a; } // sumtree' = foldtree' (+) (+) 0 public static Integer sumTree(Node node) { return foldTree(Main::add, Main::add, 0, node); } // labelsTree' = foldtree' (:) (++) [] public static Supplier> labelsTree(Node node) { Supplier> nil = Stream::empty; return foldTree(Main::cons, Main::append, nil, node); } // maptree' f = foldtree' (Node . f ) (:) [] public static Node mapTree(Function f, Node node) { Supplier>> nil = Stream::empty; return foldTree((label, children) -> new Node(f.apply(label), children), Main::cons, nil, node); } }
 // ECMAScript 6+ // fold' f a [] = a // fold' f a (x:xs) = f x (fold' f a xs) var fold = g => a => ([x, ...xs]) => x ? g(x)(fold(g)(a)(xs)) : a var add = x => y => x + y var mul = x => y => x * y var and = x => y => x && y var or = x => y => x || y // sum'' = fold' (+) 0 var sum = fold(add)(0) console.log(sum([1, 2, 3, 4])); // mul'' = fold' (*) 1 var product = fold(mul)(1) console.log(product([1, 2, 3, 4])); // all'' = fold' (&&) True var all = fold(and)(true) console.log(all([true, true, false, true])); // any'' = fold' (||) False var any = fold(or)(false) console.log(any([true, true, false, true])); var cons = x => xs => [x, ...xs] // append'' xs ys = fold' (:) ys xs var append = x => y => fold(cons)(y)(x) console.log(append([1, 2, 3, 4])([1, 2, 3, 4])); var compose = f => g => x => f(g(x)) // map' f = fold' ((:) . f) [] var map = f => fold(compose(cons)(f))([]) console.log(map(x => x * 2)([1, 2, 3, 4])) // summatrix = sum'' . map' sum'' var summatrix = compose(sum)(map(sum)) // [[1, 2, 3, 4], [1, 2, 3, 4]] var matrix = [[1, 2, 3, 4], [1, 2, 3, 4]] console.log(summatrix(matrix)) // data Node label = Node label [Node label] var makeNode = label => children => ({ label, children }) // foldtree' f g a node = foldnode' f g a node var foldtree = f => g => a => node => foldNode(f)(g)(a)(node) // foldnode' f g a (Node label children) = f label (foldnodes' f g a children) var foldNode = f => g => a => ({ label, children }) => f(label)(foldNodes(f)(g)(a)(children)) // foldnodes' f g a [] = a // foldnodes' f g a (node:nodes) = g (foldnode' f g a node) (foldnodes' f g a nodes) var foldNodes = f => g => a => ([node, ...nodes]) => node ? g(foldNode(f)(g)(a)(node))(foldNodes(f)(g)(a)(nodes)) : a // numberNodes = Node 1 [Node 2 [Node 4 []], Node 5 []] // 1 // + // | // 2<----->5 // + // | // v // 4 var numberNodes = makeNode(1)([makeNode(2)([makeNode(4)([])]), makeNode(5)([])]) console.log(numberNodes); // sumtree' = foldtree' (+) (+) 0 var sumTree = foldtree(add)(add)(0) // sumTree' numberNodes console.log(sumTree(numberNodes)) // labelsTree' = foldtree' (:) (++) [] var concat = xs => ys => append(xs)(ys) var labelsTree = foldtree(cons)(concat)([]) // labelsTree' numberNodes console.log(labelsTree(numberNodes)) // maptree' f = foldtree' (Node . f ) (:) [] mapTree = f => foldtree(compose(makeNode)(f))(cons)([]) // maptree' (* 2) numberNodes mapTree(x => x * 2)(numberNodes) console.log(mapTree(x => x * 2)(numberNodes))
 # Python 3 # fold' f a [] = a # fold' f a (x:xs) = f x (fold' f a xs) def fold(f, a, xs): if xs: return f(xs[0], fold(f, a, xs[1:])) else: return a add = lambda x, y: x + y product = lambda x, y: x * y _and = lambda x, y: x and y _or = lambda x, y: x or y cons = lambda x, xs: [x, *xs] # sum'' = fold' (+) 0 sum = lambda xs: fold(add, 0, xs) print(sum([1, 2, 3, 4])) # mul'' = fold' (*) 1 mul = lambda xs: fold(product, 1, xs) print(mul([1, 2, 3, 4])) # all'' = fold' (&&) True all = lambda xs: fold(_and, True, xs) print(all([True, True, False, True])) # any'' = fold' (||) False any = lambda xs: fold(_or, False, xs) print(any([True, True, False, True])) # lst'' = fold' (:) [] lst = lambda xs: fold(cons, [], xs) print(lst([1, 2, 3, 4])) # append'' xs ys = fold' (:) ys xs append = lambda xs, ys: fold(cons, ys, xs) print(append([1, 2, 3], [4, 5, 6])) def compose(f, g): return lambda x: f(g(x)) # map' f = fold' ((:) . f) [] def map(f, xs): return fold(lambda x, xs: cons(f(x), xs) , [], xs) print(map((lambda x: x * 2), [1, 2, 3, 4])) # summatrix = sum'' . map' sum'' def summatrix(m): return sum(map(sum, m)) print(summatrix([[1, 2, 3, 4], [1, 2, 3, 4]])) # data Node label = Node label [Node label] class Node(object): def __init__(self, label, children): self.label = label self.children = children # foldtree' f g a node = foldnode' f g a node def foldtree(f, g, a, node): return foldnode(f, g, a, node) # foldnode' f g a (Node label children) = # f label (foldnodes' f g a children) def foldnode(f, g, a, node): return f(node.label, foldnodes(f, g, a, node.children)) # foldnodes' f g a [] = a # foldnodes' f g a (node:nodes) = # g (foldnode' f g a node) (foldnodes' f g a nodes) def foldnodes(f, g, a, nodes): if nodes: first, *rest = nodes return g(foldnode(f, g, a, first), foldnodes(f, g, a, rest)) else: return a # numberNodes = Node 1 [Node 2 [Node 4 []], Node 5 []] numberNodes = Node(1, [Node(2, [Node(4, [])]), Node(5, [])]) # -- 1 # -- + # -- | # -- 2<----->5 # -- + # -- | # -- v # -- 4 def sumtree(xs): return foldtree(add, add, 0, xs) print(sumtree(numberNodes)) def concat(xs, ys): return [*xs, *ys] # labelsTree' = foldtree' (:) (++) [] def labelstree(xs): return foldtree(cons, concat, [], xs) print(labelstree(numberNodes)) # maptree' f = foldtree' (Node . f ) (:) [] def maptree(f, xs): return foldtree(lambda label, children: Node(f(label), children) , cons, [], xs) print(labelstree(maptree(lambda x: x * 2, numberNodes)))
 // Scala - dotty v3.0.0-M1 object Main { def main(args: Array[String]): Unit = { println("Why FP Matters - Higher-order Functions! ๐") } // fold' f a [] = a // fold' f a (x:xs) = f x (fold' f a xs) def fold[A, B](f: (A, B) => B, a: B)(xs: List[A]): B = { xs match { case Nil => a case x :: xs => f(x, fold(f, a)(xs)) } } // sum'' = fold' (+) 0 def sum = fold[Int, Int](_ + _, 0) sum(List(1, 2, 3, 4)) // mul'' = fold' (*) 1 def mul = fold[Int, Int](_ * _, 1) mul(List(1, 2, 3, 4)) // all'' = fold' (&&) True def all = fold[Boolean, Boolean](_ && _, true) all(List(true, true, false, true)) // any'' = fold' (||) False def any = fold[Boolean, Boolean](_ || _, false) any(List(true, true, false, true)) // lst'' = fold' (:) [] def lst[A] = fold[A, List[A]](_ :: _, Nil) lst(List(1, 2, 3, 4)) // append'' xs ys = fold' (:) ys xs def append[A](xs: List[A], ys: List[A]) = fold[A, List[A]](_ :: _, xs)(ys) append(List(4, 5, 6), List(1, 2, 3)) // map' f = fold' ((:) . f) [] def map[A, B](f: Function[A, B]) = fold[A, List[B]](f(_:A) :: _, Nil) map[Int, Int](_ * 2)(List(1, 2, 3, 4)) // summatrix = sum'' . map' sum'' def sumMatrix = map(sum) andThen sum sumMatrix( List( List(1, 2, 3, 4), List(1, 2, 3, 4) ) ) // data Node label = Node label [Node label] case class Node[A](var label: A, var children: List[Node[A]]) // foldtree' f g a node = foldnode' f g a node def foldTree[A, B, C](f: Function2[A, B, C], g: Function2[C, B, B], a: B)(node: Node[A]) = foldNode(f, g, a, node) // foldnode' f g a (Node label children) = f label (foldnodes' f g a children) def foldNode[A, B, C](f: Function2[A, B, C], g: Function2[C, B, B], a: B, node: Node[A]): C = { val Node(label, children) = node f(label, foldNodes(f, g, a, children)) } // foldnodes' f g a [] = a // foldnodes' f g a (node:nodes) = g (foldnode' f g a node) (foldnodes' f g a nodes) def foldNodes[A, B, C](f: Function2[A, B, C], g: Function2[C, B, B], a: B, nodes: List[Node[A]]): B = { nodes match { case n :: ns => g(foldNode(f, g, a, n), foldNodes(f, g, a, ns)) case Nil => a } } // numberNodes = Node 1 [Node 2 [Node 4 []], Node 5 []] // 1 // + // | // 2<----->5 // + // | // v // 4 val numberNodes = new Node[Int]( label = 1, children = List( new Node[Int]( label = 2, children = List( new Node[Int]( label = 4, Nil ) ) ), new Node[Int]( label = 5, children = Nil ) ) ) // sumtree' = foldtree' (+) (+) 0 def sumTree = foldTree[Int, Int, Int]((_ + _), (_ + _), 0) sumTree(numberNodes) // labels' = foldtree' (:) (++) [] def labels[A] = foldTree[A, List[A], List[A]]((_ :: _), (_ ++ _), List[A]()) labels(numberNodes) // maptree' f = foldtree' (Node . f ) (:) [] def mapTree[A, B](f: Function1[A, B]) = foldTree( (l:A, c:List[Node[B]]) => new Node(f(l), c), _ :: _, Nil ) mapTree[Int, Int](2 * _)(numberNodes) }