Why FP Matters - Part 2 🎈 - Higher-order Functions

whyfp-higher-order.clj

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

whyfp-higher-order.cs

// C#

using System;
using System.Collections.Generic;
using System.Linq;

namespace whyfp
{
    // data Node label = Node label [Node label]
    public class Node<T>
    {
        public T Label { get; set; }
        public IEnumerable<Node<T>> Children { get; set; }
    }

    public class Program
    {
        public static
        Func<int, int, int>
        Add = (int x, int y) => x + y;

        public static
        Func<int, int, int>
        Product = (int x, int y) => x * y;

        public static
        Func<bool, bool, bool>
        And = (bool x, bool y) => x && y;

        public static
        Func<bool, bool, bool>
        Or = (bool x, bool y) => x || y;

        public static
        Func<IEnumerable<T>, IEnumerable<T>>
        Cons<T>(T x) => (xs) => Enumerable.Repeat(x, 1).Concat(xs);

        public static
        IEnumerable<T>
        Cons2<T>(T x, IEnumerable<T> xs) => Cons(x)(xs);

        // fold'  f a [] = a
        // fold'  f a (x:xs) = f x (fold' f a xs)
        public static
        Func<IEnumerable<T>, U>
        Fold<T, U>(Func<T, U, U> f, U a) => (xs) => xs.Any()
            ? f(xs.First(), Fold(f, a)(xs.Skip(1)))
            : a;

        // sum'' = fold' (+) 0
        public static
        Func<IEnumerable<int>, int>
        Sum = Fold(Add, 0);

        // mul'' = fold' (*) 1
        public static
        Func<IEnumerable<int>, int>
        Mul = Fold(Product, 1);

        // all'' = fold' (&&) True
        public static
        Func<IEnumerable<bool>, bool>
        All = Fold(And, true);

        // any'' = fold' (||) False
        public static
        Func<IEnumerable<bool>, bool>
        Any = Fold(Or, true);

        // lst'' = fold' (:) []
        public static
        IEnumerable<T>
        Lst<T>(IEnumerable<T> xs) =>
            Fold<T, IEnumerable<T>>(Cons2, Enumerable.Empty<T>())(xs);

        // append'' xs ys = fold' (:) ys xs
        public static
        IEnumerable<T>
        Append<T>(IEnumerable<T> xs, IEnumerable<T> ys) =>
            Fold<T, IEnumerable<T>>(Cons2, ys)(xs);

        public static
        Func<T, V>
        Compose<T, U, V>(Func<T, U> f, Func<U, V> g) => x => g(f(x));

        // map' f = fold' ((:) . f) []
        public static
        Func<IEnumerable<T>, IEnumerable<U>>
        Map<T, U>(Func<T, U> f) =>
            Fold<T, IEnumerable<U>>((t, us) => Compose(f, Cons)(t)(us), Enumerable.Empty<U>());

        // summatrix = sum'' . map' sum''
        public static
        Func<IEnumerable<IEnumerable<int>>, int>
        SumMatrix = Compose(Map(Sum), Sum);

        // foldtree' f g a node = foldnode' f g a node
        public static
        Func<Node<A>, C>
        FoldTree<A, B, C>(Func<A, B, C> f, Func<C, B, B> g, B a) =>
            node => FoldNode<A, B, C>(f, g, a, node);

        // foldnode' f g a (Node label children) = f label (foldnodes' f g a children)
        public static
        C
        FoldNode<A, B, C>(Func<A, B, C> f, Func<C, B, B> g, B a, Node<A> node) =>
            f(node.Label, FoldNodes<A, B, C>(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<A, B, C>(Func<A, B, C> f, Func<C, B, B> g, B a, IEnumerable<Node<A>> nodes) =>
            nodes.Any()
                ? g(FoldNode<A, B, C>(f, g, a, nodes.First()), FoldNodes<A, B, C>(f, g, a, nodes.Skip(1)))
                : a;

        // maptree' f = foldtree' (Node . f ) (:) []
        public static
        Node<U>
        MapTree<T, U>(Func<T, U> f, Node<T> node) =>
            FoldTree<T, IEnumerable<Node<U>>, Node<U>>(
                (label, children) => new Node<U>{ Label = f(label), Children = children },
                Cons2,
                Enumerable.Empty<Node<U>>())(node);

        // sumtree' = foldtree' (+) (+) 0
        public static
        Func<Node<int>, int> SumTree = FoldTree(Add, Add, 0);

        // labels' = foldtree' (:) (++) []
        public static
        Func<IEnumerable<int>, IEnumerable<int>, IEnumerable<int>>
        Concat2 = (ys, xs) => ys.Concat(xs);
        
        public static
        Func<Node<int>, IEnumerable<int>>
        Labels = FoldTree<int, IEnumerable<int>, IEnumerable<int>>(Cons2, Concat2, Enumerable.Empty<int>());

        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<IEnumerable<int>> {
                new List<int>{ 1, 2, 3},
                new List<int>{ 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<int>
            {
                Label = 1,
                Children = new[]{
                    new Node<int>{
                        Label = 2,
                        Children = new []{
                            new Node<int>{
                                Label = 4,
                                Children = Enumerable.Empty<Node<int>>()
                            }
                        }
                    },
                    new Node<int>{
                        Label = 5,
                        Children = Enumerable.Empty<Node<int>>()
                    }
                }
            };

            System.Console.WriteLine(SumTree(numberNodes));
            System.Console.WriteLine(Labels(numberNodes));
            System.Console.WriteLine(MapTree<int, int>(x => x * x, numberNodes));
        }
    }
}

whyfp-higher-order.fs

// 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<tree<'a>>

// 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"

[<EntryPoint>]
let main argv =
    0 // return an integer exit code

whyfp-higher-order.hs

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

whyfp-higher-order.java

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<T1, T2, Result> {
    public Result apply(T1 t1, T2 t2);
}

// data Node label = Node label [Node label]
class Node<T>{
    public T label;
    public Supplier<Stream<Node<T>>> children;

    public Node(T label, Supplier<Stream<Node<T>>> children) {
        this.label = label;
        this.children = children;
    }
}

public class Main {
    public static void main(String[] args) {
        Supplier<Stream<Integer>> ns = () -> Stream.of(1, 2, 3, 4);
        Supplier<Stream<Boolean>> 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<Integer> numberNodes = new Node<Integer>(
                1,
                () -> Stream.of(
                        new Node<Integer>(
                                2,
                                () -> Stream.of(
                                        new Node<Integer>(4, Stream::empty))),
                        new Node<Integer>(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 <T, S> S fold(Function2<T, S, S> fn, S a, Supplier<Stream<T>> xs) {
        Optional<T> 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<Stream<Integer>> xs) {
        return fold(Main::add, 0, xs);
    }

    // mul'' = fold' (*) 1
    public static Integer mul(Supplier<Stream<Integer>> xs) {
        return fold(Main::product, 1, xs);
    }

    // all'' = fold' (&&) True
    public static Boolean all(Supplier<Stream<Boolean>> xs) {
        return fold(Main::and, true, xs);
    }

    // any'' = fold' (||) False
    public static Boolean any(Supplier<Stream<Boolean>> xs) { return fold(Main::or, false, xs); }

    public static<T> Supplier<Stream<T>> cons(T x, Supplier<Stream<T>> xs) {
        return () -> Stream.concat(Stream.of(x), xs.get());
    }

    // lst'' = fold' (:) []
    public static <T> Supplier<Stream<T>> lst(Supplier<Stream<T>> xs) {
        return fold(Main::cons, Stream::empty, xs);
    }

    // append'' xs ys = fold' (:) ys xs
    public static <T> Supplier<Stream<T>> append(Supplier<Stream<T>> xs, Supplier<Stream<T>> ys) {
        return fold(Main::cons, ys, xs);
    }

    // map' f = fold' ((:) . f) []
    public static <T, R> Supplier<Stream<R>> map(Function<T, R> f, Supplier<Stream<T>> xs) {
        return fold((x , y) -> cons(f.apply(x), y), Stream::empty, xs);
    }

    // sumMatrix' = sum'' . map' sum''
    public static Integer sumMatrix(Supplier<Stream<Supplier<Stream<Integer>>>> m) {
       return sum(map(x -> sum(x), m));
    }

    // foldtree' f g a node = foldnode' f g a node
    public static <A, B, C> C foldTree(Function2<A, B, C> f, Function2<C, B, B> g, B a, Node<A> node) {
        return foldNode(f, g, a, node);
    }

    // foldnode' f g a (Node label children) = f label (foldnodes' f g a children)
    private static <A, B, C> C foldNode(Function2<A,B,C> f, Function2<C,B,B> g, B a, Node<A> 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 <A, B, C> B foldNodes(Function2<A,B,C> f, Function2<C,B,B> g, B a, Supplier<Stream<Node<A>>> nodes) {
        Optional<Node<A>> 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<Integer> node) {
        return foldTree(Main::add, Main::add, 0, node);
    }

     // labelsTree' = foldtree' (:) (++) []
     public static <T> Supplier<Stream<T>> labelsTree(Node<T> node) {
        Supplier<Stream<T>> nil = Stream::empty;
        return foldTree(Main::cons, Main::append, nil, node);
     }

    // maptree' f = foldtree' (Node . f ) (:) []
    public static <T, R> Node<R> mapTree(Function<T, R> f, Node<T> node) {
        Supplier<Stream<Node<R>>> nil = Stream::empty;
        return  foldTree((label, children) -> new Node(f.apply(label), children), Main::cons, nil, node);
    }
}

whyfp-higher-order.js

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

whyfp-higher-order.py

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

whyfp-higher-order.scala

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

Why FP Matters - Part 2½ 🍰 - Slicing complexity with Higher-order Functions