Skip to content

Instantly share code, notes, and snippets.

@chriseidhof

chriseidhof/presentation.md

Created June 28, 2014 13:00
Show Gist options
  • Save chriseidhof/8b109d27701d745e6bcd to your computer and use it in GitHub Desktop.
Save chriseidhof/8b109d27701d745e6bcd to your computer and use it in GitHub Desktop.
Download ZIP
MobileOptimized Presentation
Raw
presentation.md

[fit] Functional Programming in

[fit] Swift

Chris Eidhof - objc.io - June 28, Minsk

Apple decides everything, and we will like it.

-- Charles McCathie Nevile

Why?

You can keep writing normal OOP code. But some things are easier when done in a functional way.

What is Functional Programming?

Functions

func add(x: Int, y: Int) -> Int {
  return x + y
}

No side-effects

func add(x: Int, y: Int) -> Int {
  return x + y + Int(arc4random())
}

add(1,2)
1176275535

Referential Transparency

The same input should always give the same output.

Avoid State

Purity

A pure function has no side-effects:

  • No use of global variables
  • No reading of files
  • No use of functions that are not pure

Pure functions are referentially transparent

In Practice

Most of your code should be pure, only small bits have side-effects.

Example

Suppose we build a library for describing diagrams:

  • Describing a diagram: pure
  • Calculating the layout of a diagram: pure
  • Executing the actual drawing: side-effect

Why?

This will make your code a lot easier to change, reuse and test.

Functional Programming Basics

Our data set

let cities : Dictionary<String,Int> = 
   [ "Минск":     1834200 
   , "Борисов":   147100
   , "Солигорск": 102300
   , "Молодечно": 94200
   , "Жодино":    61800
   ]

let names = Array(cities.keys)
let populations = Array(cities.values)

Names

[Жодино, Минск, Молодечно, Солигорск, Борисов]

Populations

[61800, 1834200, 94200, 102300, 147100]

Map

func addCity(s: String) -> String {
  return s + "is a city"
}

names.map(addCity)
[Жодиноis a city, Минскis a city, Молодечноis a city, Солигорскis a city, Борисовis a city]

Filter

func isMinsk(s: String) -> Bool {
  return s == "Минск"
}

names.filter(isMinsk)
[Минск]

Filter, simplified

names.filter({ (s: String) -> Bool in
  return s == "Минск"
})
[Минск]

Filter, more simplified

names.filter({ s in
  return s == "Минск"
})
[Минск]

Filter, even more simplified

names.filter({ 
  return $0 == "Минск"
})
[Минск]

Filter, simplest

names.filter { $0 == "Минск" }
[Минск]

populations.filter { $0 > 100000 }
[1834200, 102300, 147100]

Sum of an array

func sum(arr: Int[]) -> Int {
  var result = 0
  for i in arr {
    result += i
  }
  return result
}

sum(Array(1..10))
45

Product of an array

func product(arr: Int[]) -> Int {
  var result = 1
  for i in arr {
    result *= i
  }
  return result
}

product(Array(1..10))
362880

Reduce

func reduce(initialValue: Int, 
            combine: (Int,Int) -> Int, 
            arr: Int[]) -> Int {
  var result = initialValue
  for i in arr {
    result = combine(result,i)
  }
  return result
}

Reduce

reduce(0, +, Array(1..10))
45

reduce(1, *, Array(1..10))
362880

Sum and Product

let sum     = { reduce(0,+,$0) }

let product = { reduce(1,*,$0) }

Concatenate

func concat(strings: String[]) -> String {
    var result = ""
    for x in strings {
        result += x
    }
    return result
}

concat(names)
ЖодиноМинскМолодечноСолигорскБорисов

Generics

func reduce<A>(initialValue: A, 
               combine: (A,A) -> A, 
               arr: A[]) -> A {
  var result = initialValue
  for i in arr {
    result = combine(result,i)
  }
  return result
}
reduce("", +, names)
ЖодиноМинскМолодечноСолигорскБорисов

Adding line-breaks

reduce("", { $0 + "\n" + $1 }, names)
Жодино
Минск
Молодечно
Солигорск
Борисов

Making reduce more generic

func reduce<A,R>(initialValue: R, 
                 combine: (R,A) -> R,
                 arr: A[]) -> R {
    var result = initialValue
    for i in arr {
        result = combine(result,i)
    }
    return result
}

Define map in terms of reduce

func map<A,B>(array: A[], f: A -> B) -> B[] {
    return reduce([], { (var arr: B[], el: A) in
        arr += f(el)
        return arr
    }, array)
}

map(Array(1..10), { $0 * 2})
( 2, 4, 6, 8, 10, 12, 14, 16, 18)

Define filter in terms of reduce

func filter<A>(array: A[], f: A -> Bool) -> A[] {
    return reduce([], { (var arr, el) in
        if (f(el)) {
            arr += el
        }
        return arr
    }, array)
}

let isEven = { $0 % 2 == 0 }

filter(Array(1..10), isEven)
( 2, 4, 6, 8)

...

QuickSort

func partition(v: Int[], left: Int, right: Int) -> Int {
    var i = left
    for j in (left + 1)..(right + 1) {
        if v[j] < v[left] {
            i += 1
            (v[i], v[j]) = (v[j], v[i])
        }
    }
    (v[i], v[left]) = (v[left], v[i])
    return i
}
 
func quicksort(v: Int[], left: Int, right: Int) {
    if right > left {
        let pivotIndex = partition(v, left, right)
        quicksort(v, left, pivotIndex - 1)
        quicksort(v, pivotIndex + 1, right)
    }
}

// Source: https://gist.github.com/fjcaetano/b0c00a889dc2a17efad9

Functional QuickSort

func qsort(var array: Int[]) -> Int[] {
    if array.count == 0 { return [] }
    let pivot = array.removeAtIndex(0)
    let lesser = array.filter { $0 < pivot }
    let greater = array.filter { $0 >= pivot }
    return qsort(lesser) + [pivot] + qsort(greater)
}
qsort(populations)
[61800, 94200, 102300, 147100, 1834200]

let citiesAndPopulations = cities.keysAndValues
> [ (Жодино, 61800)
> , (Минск, 1834200) 
> , (Молодечно, 94200)
> , (Солигорск, 102300)
> , (Борисов, 147100)]

Sort by name

func qsortWith<A>(var array: A[], 
                  compare: (A,A) -> Bool)
                 -> A[] {
    if array.count == 0 { return [] }
    let pivot = array.removeAtIndex(0)
    let lesser = array.filter  { !compare(pivot,$0) }
    let greater = array.filter { compare(pivot,$0) }
    return qsortWith(lesser,compare) + 
           [pivot] + 
           qsortWith(greater,compare)
}

Sort by name

qsortWith(citiesAndPopulations) { (l,r) in l.0 > r.0 }
[(Солигорск, 102300), 
 (Молодечно, 94200),
 (Минск, 1834200),
 (Жодино, 61800),
 (Борисов, 147100)]

Sort by population

qsortWith(citiesAndPopulations) { (l,r) in l.1 > r.1 }
[(Минск, 1834200),
 (Борисов, 147100),
 (Солигорск, 102300),
 (Молодечно, 94200),
 (Жодино, 61800)]

...

Diagrams

empty: Diagram
func rect(#width: Double, #height: Double) -> Diagram
func circle(#radius: Double) -> Diagram
@infix func ||| (l: Diagram, r: Diagram) -> Diagram

Example diagram

let blueSquare = square(1).fill(NSColor.blueColor())
let redSquare = square(2).fill(NSColor.redColor())
let greenCircle = circle(radius:1).fill(NSColor.greenColor())
let cyanCircle = circle(radius: 1).fill(NSColor.cyanColor()) 

example = blueSquare ||| cyanCircle ||| redSquare ||| greenCircle

inline 100%

Reduce

func hcat(d: Diagram[]) -> Diagram {
  return reduce(empty, |||, d)
}
example = hcat([blueSquare, cyanCircle, redSquare, greenCircle])

Bar diagrams

func barGraph(input: (String,Double)[]) -> Diagram {
    return hcat(normalize(values).map { x in
        return rect(width: 1, height: 3*x).alignBottom()
    })
}

inline 100%

Adding labels

func barGraph(input: (String,Double)[]) -> Diagram {
    let values : Double[] = input.map { $0.1 }
    let bars =  hcat(normalize(values).map { x in
        return rect(width: 1, height: 3*x).alignBottom()
    })
    let labels = hcat(input.map { x in
        return text(width: 1, height: 0.3, text: x.0).alignTop()
    })
    return bars --- labels
}

inline 100%

Diagrams API

Almost all functions are pure: create a diagram, combine diagrams, color diagrams.

Only the rendering is impure.

...

QuickCheck

Using functional programming to automate testing

Check if qsort gives the same result as sort

func prop_sort(ls: Int[]) -> Bool {
    return qsort(ls) == sort(ls)
}

Idea

Let's generate a lot of random integer arrays, and run them through our property. Makes it easier to find mistakes.

Running our checker

check(prop_sort)
true

Let's build QuickCheck

func check<X : Arbitrary>(prop : Array<X> -> Bool) -> Bool {
    for _ in 0..numberOfIterations {
        let randomLength = Int(arc4random() % 50)
        let array : X[] = Array(0..randomLength).map { 
          _ in return X.arbitrary() 
        }
        if(!prop(array)) {
          println("Property doesn't hold: \(array)")
          return false
        }
    }
    return true
}

Running our checker

check(prop_sort)
true

Checking our checker

check { (x: Int[]) in
  qsort(x) == x
}
Property doesn't hold: [459, 9052, 1750, 3572, 3101, 3104, 1675, 148, 4781, 5031, 
4769, 6738, 2946, 4396, 3190, 4217, 9975, 5143, 7339, 7180, 2041, 6552, 6780, 
3839, 7279, 1060, 375, 1096, 5957, 5484, 2832, 8705, 9202, 2158, 3015, 303, 1911,
9846, 8316, 3300]
false

Better errors

protocol Smaller {
  func smaller() -> Self?
}

extension Array : Smaller {
  func smaller() -> Array<T>? {
    if self.count == 0 { return nil }
    var copy = self
    copy.removeAtIndex(0)
    return copy
  }
}

Better errors

func check1<X : Arbitrary>(prop : Array<X> -> Bool) -> Bool {
    for _ in 0..numberOfIterations {
        let randomLength = Int(arc4random() % 50)
        let array : X[] = Array(0..randomLength).map { 
          _ in return X.arbitrary() 
        }
        if(!prop(array)) {
            let smallerValue = iterateWhile(array, { !prop($0) }) {
              $0.smaller() 
            } 
            println("Property doesn't hold: \(smallerValue)")
            return false
        }
    }
    return true
}

Let's see the results

check1 { (x: Int[]) in
  qsort(x) == x
}
Property doesn't hold: [6890, 465]
false

Conclusion

This is powerful stuff

You can start using this in your Swift code.

We're just at the beginning

Swift also allows for much easier OOP, and we can mix and match whatever we want.

There are a lot more cool things

  • Enums
  • Pattern matching
  • Optionals
  • Applicative Functors and Monads

fit

@chriseidhof

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment