Functional Programming

Concepts of Programming Languages

Sebastian Macke

Rosenheim Technical University

Last lecture

2

The error interface

func divide(a, b int) (int, error) {
    if b == 0 {
        return 0, errors.New("division by zero")
    }
    return a / b, nil
}

func main() {
    // Successful division
    result, err := divide(10, 0)
    if err != nil {
        fmt.Println("Error:", err)
    } else {
        fmt.Println("Result:", result)
    }
}

The error is just an interface with one method that should return the error message: 

type error interface {
    Error() string
}
3

What is Functional programming?

4

History

Functional programming is old, but some major languages have adapted them quite recently

5

Functional programming languages are categorized into two groups

These types of functional languages support only the functional paradigms and have no state. For example − Haskell.

These types of functional languages support the functional paradigms and imperative style programming. For example all of the major languages today.

6

Impure Functional Languages

7

Function as variable

func main() {
    ADD := func(x, y int) int {
        return x + y
    }
    fmt.Println(ADD(1, 2)) // -> returns 3
    fmt.Println("The type of ADD is", reflect.TypeOf(ADD).Kind())
}

ANOTHERADD := ADD;
ANOTHERADD(1, 2);
func main() {
    fmt.Println(func(x, y int) int { return x + y }(3, 4)) // -> returns 7
}
8

Function as parameter.

func do(f func(int), loops int) {
    for i := 0; i < loops; i++ {
        f(i)
    }
}

func main() {
    printvalue := func(i int) { fmt.Println(i) }
    do(printvalue, 5)
}
9

Function as return value.

type areaFunc func(int, int) int

func getAreaFunc() areaFunc {
    return func(x, y int) int {
        return x * y
    }
}

func main() {
    areaF := getAreaFunc()
    res := areaF(2, 4)
    fmt.Println(res)
}
10

Why functional programming is better - Odd Number Filter

    array := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
    filteredArray := []int{}
    for _, v := range array {
        if v%2 == 0 {
            filteredArray = append(filteredArray, v)
        }
    }
    fmt.Println(filteredArray)

    array := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
    filteredArray := stream.OfSlice(array).
        Filter(func(n int) bool { return n%2 == 0 }).
        ToSlice()
    fmt.Println(filteredArray)
11

Why functional programming is better - Sorting

Java: 

class IntComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer i1, Integer i2) {
        return i1.compareTo(i2);
    }
}

class SortDemo {
    public static void main(String[] args) {
        Integer[] array = { 3, 2, 1, 5, 8, 6 };
        Arrays.sort(array, new IntComparator());
        System.out.println(Arrays.toString(array));
    }
}
12

Why functional programming is better - Sorting

    array := []int{10, 5, 3, 7, 1, 0, 4, 6}
    sortedArray := stream.OfSlice(array).
        Sorted(func(a, b int) int { return a - b }).
        ToSlice()
    fmt.Println(sortedArray)
13

Closures

// intSeq returns another function, which we define anonymously in the body of intSeq.
// The returned function closes over the variable i to form a closure.
func intSeq() func() int {
    i := 0
    return func() int {
        i++
        return i
    }
}
func main() {
    // We call intSeq, assigning the result (a function) to nextInt.
    // This function value captures its own i value, which will be updated each time we call nextInt.
    nextInt := intSeq()
    // See the effect of the closure by calling nextInt a few times.
    fmt.Println(nextInt())
    fmt.Println(nextInt())

    // To confirm that the state is unique to that particular function, create and test a new one.
    newInts := intSeq()
    fmt.Println(newInts())
}
14

Closures II

Access array outside of the function for sorting 

func main() {
    data := []int{27, 15, 8, 9, 12, 4, 17, 19, 21, 23, 25}
    sort.SliceStable(data, func(i, j int) bool {
        return data[i] < data[j]
    })
    fmt.Println(data)
}
15

Exercise 5.1 - Warm Up

This is a Bubble Sort algorithm for ints. 

func BubbleSort(data []int) {
    for i := 0; i < len(data); i++ {
        for j := 0; j < len(data)-1; j++ {
            if data[j] > data[j+1] {
                data[j], data[j+1] = data[j+1], data[j] // Swap the values

            }
        }
    }
}

func main() {
    data := []int{27, 15, 8, 9, 12, 4, 17, 19, 21, 23, 25}
    BubbleSort(data)
    fmt.Println(data)
}

Rewrite it, so that the Bubble Sort algorithm takes a comparison function as input 

BubbleSort(data, func(i, j int) bool {return data[i] > data[j]})
16

Closures in JavaScript

const object1 = {
    prop: 42,

    func: function () {
        return this.prop;
   },
};

console.log(object1.prop)  // 42
console.log(object1.func())  // 42  // At creation time, this points to test.prop

const object2 = {
    prop: 43,
    func: object1.func  // take the function defined in object1.
}

console.log(object2.prop)  // 43
console.log(object2.func())  // 43. Now "this" points to object2.
17

Pure Functions

18

What is a pure function?

Examples: exp, sin, cos, max, min.

Advantages

19

Every Function can be made pure

var count = 0
func increment() {
    count++
}
func incrementPure(count int) int {
    return count + 1 // This function is pure because it does not modify external state
}
var array []int
newarray := append(array, 1)
20

Pure Functional Languages

21

Functional Programming – Characteristics

The most prominent characteristics of functional programming are as follows

22

Functional programming offers the following advantages

Functional programming does not support state, so there are no side-effect results and we can write error-free codes.

Functional programs consist of independent units that can run concurrently. As a result, such programs can be more efficient.

Functional programming supports lazy evaluation like Lazy Lists, Lazy Maps, etc.

Functional programming supports distributed computing

23

Many Functional Languages only support Single Argument Functions

// ADD with 2 parameters
ADD := func(x, y int) int {
    return x + y
}
ADD(1,2) -> 3
// Curried ADD
ADDC := func(x int) func(int) int {
    return func(y int) int {
        return x + y
    }
}
ADDC(1)(2) -> 3
24

Currying allows for Partial Application

// Curried ADD
ADDC := func(x int) func(int) int {
    return func(y int) int {
        return x + y
    }
}
partialApplicatedFunction := ADDC(1)
.... Do something else
partialApplicatedFunction(3) -> 4
25

Functional Composition

Functions can be composed to new functions
g(f(x)) -> (g ◦ f)(x) 

// Function f()
f := func(x int) int {
    return x * x
}

// Function g()
g := func(x int) int {
    return x + 1
}

// Functional Composition: (g◦f)(x)
gf := func(x int) int {
    return g(f(x))
}

fmt.Printf("%v\n", gf(2)) // --> 5
26

Functional Composition (2)

Functions can be composed with functions as parameters 

package main

import "fmt"

type function func(any) any

func main() {
    compose := func(g, f function) function {
        return func(x any) any {
            return g(f(x))
        }
    }

    square := func(x any) any { return x.(int) * x.(int) }

    fmt.Printf("%v\n", compose(square, square)(2)) // --> 4*4 = 16
    fmt.Printf("%v\n", compose(compose(square, square), square)(2))
}
27

Famous Functional Languages

28

History: The Lambda Calculus

Professor Graham Hutton explains the Lambda Calculus (Cool Stuff :-)

29

The Lambda Calculus

Format


λ input . output

is equivalent to 

    function (input) {
        return  output
    }

That's all

30

Lambda calculus

Variables
x
- A variable can be itself a function
- There are no datatypes (number, logical values)

Functions
λx.x (here the identity function as an example)
- Functions have no internal state

Applications
(λx.x) a
- here the application of the identity function to a returns a)
- also a can be a function
- Parenthesis help to avoid ambiguity.

31

Lambda Calculus in Go: Combinators

// This is the key: A recursive function definition for all functions!!!
type fnf func(fnf) fnf

func main() {
    // Boolean TRUE as function: λx.λy.x
    TRUE := fnf(func(x fnf) fnf {
        return func(y fnf) fnf {
            return x
        }
    })

    // Boolean FALSE as function: λx.λy.y
    FALSE := fnf(func(x fnf) fnf {
        return func(y fnf) fnf {
            return y
        }
    })

    fmt.Println(TRUE.ToBool())
    fmt.Println(FALSE.ToBool())
}
32

Lambda Calculus in Go: Helper for printing

// ToBool Returns an actual bool for a Church Boolean
func (f fnf) ToBool() bool {
    // λx.x is a function which returns itself (the ID)
    ID := func(x fnf) fnf { return x }
    var ret bool
    f(func(f fnf) fnf { ret = true; return f })(func(f fnf) fnf { ret = false; return f })(ID)
    return ret
}
33

Lambda Calculus in Go: Boolean Logic

    // Boolean Logic
    NOT := func(p fnf) fnf { return p(FALSE)(TRUE) } // λb.b False True
    AND := func(p fnf) fnf { return func(q fnf) fnf { return p(q)(p) } }
    OR := func(p fnf) fnf { return func(q fnf) fnf { return p(p)(q) } }
    EQ := func(p fnf) fnf { return func(q fnf) fnf { return p(q)(NOT(q)) } }

    fmt.Println(NOT(FALSE).ToBool())
    fmt.Println(NOT(TRUE).ToBool())

    fmt.Println(AND(FALSE)(TRUE).ToBool())
    fmt.Println(OR(FALSE)(FALSE).ToBool())
    fmt.Println(EQ(TRUE)(TRUE).ToBool())
}
34

Lambda Calculus in JavaScript

TRUE = a => b => a;
FALSE = a => b => b;
NOT = f => a => b => f(b)(a);

ToBool = f => f(() => true)(() => false)()

console.log( ToBool(TRUE) ) // -> true
console.log( ToBool(FALSE) ) // -> false

console.log( ToBool(NOT(TRUE)) )  // -> false
console.log( ToBool(NOT(FALSE)) ) // -> true

Fundamentals of Lambda Calculus & Functional Programming in JavaScript

35

Exercise

36

Functions as First Class Citizens in Go

37

Sample from the Go Standard Library

// Map returns a copy of the string s with all its characters modified
// according to the mapping function. If mapping returns a negative value, the character is
// dropped from the string with no replacement.
func Map(mapping func(rune) rune, s string) string
s := "Hello, world!"
s = strings.Map(func(r rune) rune {
    return r + 1
}, s)
fmt.Println(s) // --> Ifmmp-!xpsme"
38

Go does not have an API similar to Java Streams

    // array of generic interfaces.
    stringSlice := []any{"a", "b", "c", "1", "D"}

    // Map/Reduce
    result := ToStream(stringSlice).
        Map(toUpperCase).
        Filter(notDigit).
        Reduce(concat).(string)

    if result != "A,B,C,D" {
        t.Error(fmt.Sprintf("Result should be 'A,B,C,D' but is: %v", result))
    }
    // lambda (inline)
39

Exercise 5.2 - Map / Filter / Reduce

Exercise 5.2

Map/Reduce is a famous functional construct implemented in many parallel and distributed collection frameworks like Hadoop, Apache Spark, Java Streams (not distributed but parallel), C# Linq 

type Stream interface {
    Map(m Mapper) Stream
    Filter(p Predicate) Stream
    Reduce(a Accumulator) Any
}
40

Generic Mapper, Predicate and Accumulator

// Predicate function returns true if a given element should be filtered.
type Predicate func(any) bool

// Mapper function maps a value to another value.
type Mapper func(o1 any) any

// Accumulator function returns a combined element.
type Accumulator func(any, any) any
41

Exercise 5.2 - Word Count (WC)

Word Count is a famous algorithm for demonstrating the power of distributed collections and functional programming. Word Count counts how often a word (string) occurs in a collection. It is easy to address that problem with shared state (a map), but this solution does not scale well. The question here is how to use a pure functional algorithm to enable parallel and distributed execution.

After running Word Count, you should get the following result: 

INPUT:  []Any{"a", "a", "b", "b", "D", "a"}
OUTPUT: "a:3, b:2, D:1, "

Questions

42

Classic Word Count Sample

// Classic wordcount sample
// ========================
func TestWordCount(t *testing.T) {
    strings := []any{"a", "a", "b", "b", "D", "a"}

    // Map/Reduce
    result := ToStream(strings).
        Map(func(o any) any {
            result := []Pair{Pair{o, 1}}
            return result
        }).
        Reduce(sumInts).([]Pair)

    for _, e := range result {
        fmt.Printf("%v:%v, ", e.k, e.v) // "a:3, b:2, D:1, "
    }
}
43

Questions

44

Thank you

Tags: go, programming, master

Sebastian Macke

Rosenheim Technical University

Sebastian.Macke@th-rosenheim.de

https://www.qaware.de

Use the left and right arrow keys or click the left and right edges of the page to navigate between slides.
(Press 'H' or navigate to hide this message.)