Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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<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));
}
}
}
// 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
-- 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<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);
}
}
// 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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment