Computer Science / Software Engineering Notes Network

Programming III

Matthew Barnes, Mathias Ritter

Introduction to functional programming        5

Features of Haskell        5

Bare basics        5

Standard prelude        6

Standard list functions        6

Function application        7

Useful GHCi Commands        7

Naming requirements        7

Layout rules        8

Types, Classes and Functions        9

Types        9

Basic types        9

Compound types        10

List values        10

Curried functions        10

Polymorphism        11

Classes        12

Functions        14

Guarded equations        14

‘where’ vs ‘let’ and ‘in’        16

Pattern matching        17

Lambda expressions        18

Operator sections        19

List Comprehension and Recursion        19

List comprehension        19

Zips        20

Recursion        20

Tail recursion        21

Higher Order Functions        23

Map, filter and fold        23

Dollar operator        23

Function composition        24

Declaring Types        24

Declaring Types and Classes        24

‘type’        24

‘data’        25

‘newtype’        26

‘class’        26

‘instance’        26

Trees        27

Red-Black Trees        27

Abstract Syntax Trees        28

Functors        28

Directions, trails and zippers        30

Graphs        31

Indexed collections of Nodes, Edges        31

Structured data type with cyclic dependencies        31

Inductive approach with graph constructors        33

Evaluation Order and Laziness        35

Equational reasoning        35

Redex        36

Beta-reduction        36

Call-By-Name        37

Call-By-Value        38

Modularity        38

Strict application        39

Interpreters and Closures        40

Part 1 - Substitutions        40

Lambda calculus        40

Beta reduction syntax        41

Alpha conversion        41

Part 2 - Machines        42

Environments        42

Frames        43

Continuations        44

CEK-machines        44

Closures        45

Example sequence        47

Functional I/O and Monads        50

I/O in Haskell        50

IO a        50

Actions        51

Do notation        51

Main Function, File Handling, Random Numbers        52

Applicatives        53

Monads        56

Use of monads: Error handling        58

Use of monads: Chaining        59

Use of monads: Non-determinism        60

mapM        61

fitlerM        64

Functional Programming in Java        67

Functions as Objects        67

Functional Interfaces        68

ActionListener        69

Lambda Syntax        70

More general function types        70

Closure: lambda vs anonymous inner classes (AICs)        72

Method references        74

Recursion        75

Programming with Streams        77

Functional programming and lists        77

External vs internal iteration        77

Streams in Java        77

Common operations        79

Map - Streams as Functors        79

flatMap - Streams as Monads        80

More stream operations yay        80

State of Streams        81

Optional        82

Parallel streams        82

Functional Programming in JavaScript        84

Functional vs Imperative Style        84

Functional Features        85

Functional Programming in JS with Rambda        85

Iterative Approach        86

Get a property        88

Filtering        88

Rejecting        90

New objects from old        90

Sorting        91

Functional Approach        91

TL;DR        93

Introduction to functional programming        93

Types, Classes and Functions        94

List Comprehension and Recursion        96

Higher Order Functions        96

Declaring Types        97

Evaluation Order and Laziness        98

Interpreters and Closures        99

Functional I/O and Monads        99

Functional Programming in Java        101

Programming with Streams        102

Functional programming in JavaScript        103

Functional programming in JS with Rambda        103

Recommended Reading        104


Introduction to functional programming

Features of Haskell

Bare basics

Set theory

Haskell

add5 :: Int -> Int
add5 x = x +
5

Standard prelude

Standard list functions

Function

Description

Example

head

Selects the first element in the list

head [1, 2, 3, 4]
-- will output '1'

tail

Removes the first element in a list

tail [1, 2, 3, 4]
-- will output [2, 3, 4]

length

Calculates the length of a list

length [1, 2, 3, 4]
-- will output 4

!!

Selects the nth element of a list

[1, 2, 3, 4] !! 2
-- will output 3

take

Selects the first n elements of a list

take 2 [1, 2, 3, 4]
-- will output [1, 2]

drop

Removes the first n elements of a list

drop 2 [1, 2, 3, 4]
-- will output [3, 4]

++

Appends two lists

[1, 2] ++ [3, 4]
-- will output [1, 2, 3, 4]

sum

Calculates the sum of the elements in a list

sum [1, 2, 3, 4]
-- will output 10

product

Calculates the product of the elements in a list

product [1, 2, 3, 4]
-- will output 24

reverse

Reverses a list

reverse [1, 2, 3, 4]
-- will output [4, 3, 2, 1]

repeat

Creates an infinite list of repeated elements

repeat 5
-- will output [5, 5, 5, 5, ...]

Function application

Useful GHCi Commands

Command

Meaning

:load name

Load script name

:reload

Reload current script

:set editor name

Set editor to name

:edit name

Edit script name

:edit

Edit current script

:type expr

Show type of expression

:?

Show all commands

:quit

Quit GHCi

Naming requirements

(£) x y = x + y
5 £ 6 -- output will be 11

Layout rules

-- do this
a =
10
b =
20
c =
30

-- do not do this
a =
10
  b =
20
 c =
30

Implicit grouping

Explicit grouping

a = b + c

  where

    b = 1

    c = 2

d = a * 2

a = b + c
 
where
   {b =
1;
   c =
2}
d = a *
2


Types, Classes and Functions

Types

e :: t

:type head ['j','g','c']
-- will output head ['j','g','c'] :: Char

Basic types

Basic type

Description

Type name

Examples

Booleans

Can be either true or false, it is 1 bit in size. Can be used with &&, || or ‘not’ operators.

Bool

True :: Bool

False :: Bool

Characters

Stores one character. It’s 2 words in size.

Char

‘j’ :: Char

‘#’ :: Char

‘4’ :: Char

Strings

Stores a bunch of characters. They’re not really a basic type, because they’re just lists of characters.

String

“The World”:: [ Char ]

“MUDA” :: [ Char ]

“duwang” :: [ Char ]

“Joseph Joestar” :: [ Char ]

Numbers

Int, Integer, Float, Double etc are all numbers

The difference between “Int” and “Integer” is that “Int” is fixed in size and “Integer” is dynamic.

Int

Integer

Float

Double

7 :: Int

3.4 :: Float

9.56 :: Double

3587352 :: Int

Compound types

Compound type

Description

Type name

Examples

Lists

A collection of an element, of which all are the same type

[ T ]

(where T is the type of the elements)

[ 6, 7, 3 ] :: [ Int ]

[‘j’, ‘x’] :: [ Char ]

Tuples

Tuples are fixed-size (immutable) lists. They can have any type at any position.

( T1, T2, T3 ... )

With Tn being the types of the tuple elements

(4, 7.8, “ora”) :: (Int, Float, [Char])

Functions

Functions take an input and spit an output out. The type of the input and output can be anything, even compound types.

T -> U

(With T being the input type and U being the output type)

add :: (Int,Int) -> Int

add (5,6) = 11

ora n = intercalate " " (take n (repeat "ora"))

ora :: Int -> [Char]

List values

Curried functions

add :: Int -> (Int -> Int)

or

add ::
Int -> Int -> Int

mult :: Int → (Int → (Int → Int))
mult x y z = x*y*z

Polymorphism

fst :: (a,b) → a
head :: [a] → a
take ::
Int → [a] → [a]
zip :: [a] → [b] → [(a,b)]
id :: a → a

Classes

Num a

(+) :: (Num a) => a -> a -> a

showDouble :: (Show a, Num a) => a -> String

showDouble x = show (x + x)

Class name

Description

Example

Eq

Supports == and /= operations

isEqual x y = x == y
isEqual ::
Eq a => a -> a -> Bool

Ord

Supports operators like < and >

isBigger x y = x > y
isBigger ::
Ord a => a -> a -> Bool

Show

Supports being converted into a string

toString x = show x
toString ::
Show a => a -> String

Read

Supports strings being converted into this

fromString x = read x
fromString ::
Read a => String -> a

Num

Is either Int, Integer, Float or Double

double x = x * 2
double ::
Num a => a -> a

Integral

Is either Int or Integer (supports div and mod)

divmod x y = (div x y + mod x y)
divmod ::
Integral a => a -> a -> a

Fractional

Is either Float or Double (supports / and recip, which means ‘reciprocal’)

negrecip x = -1 * recip x
negrecip ::
Fractional a => a -> a

Functions

Guarded equations

Pattern matching

Guarded equations

fact 0 = 1
fact n = n * fact (n -
1)

{- Keep in mind that this only works for a .hs file, it will not work on the GHCi interface unless you use :{ and :} -}

fact n | n == 0 = 1
      | n ==
1 = 1
      | otherwise = n * fact (n -
1)

{- In theory, you should be able to leave out the n == 1 bit, but GHCi didn't like it when I tried that. -}

Steps

Value of n

Explanation

fact n | n == 0 = 1

       | n == 1 = 1
      | otherwise = n * fact (n - 1)

2

Here, we start by inputting the value of ‘n’ into the factorial function.

fact n | n == 0 = 1

       | n == 1 = 1
      | otherwise = n * fact (n - 1)

2

Now, we look at the first guarded equation predicate. If this is true, we do whatever is on the right of the equals sign next to it. If this is false, we move on to the next predicate.

fact n | n == 0 = 1

       | n == 1 = 1
      | otherwise = n * fact (n - 1)

2

It’s false, so we look at the next predicate below it. The same rule applies here.

fact n | n == 0 = 1

       | n == 1 = 1
     
| otherwise = n * fact (n - 1)

2

It’s false, so we move on to the next predicate. The same rule applies here. ‘otherwise’ is like ‘else’ in Java or C, it’s used when all other predicates are false. It’s syntactic sugar for “True”.

fact n | n == 0 = 1

       | n == 1 = 1
      | otherwise
= n * fact (n - 1)

2

‘otherwise’ is always true, so we do what’s on the right of the equals sign here. This is the recursive clause, so we do the function again, but with n - 1.

fact n | n == 0 = 1

       | n == 1 = 1
      | otherwise = n * fact (n - 1)

1

Here, we input the value of ‘n’ into the factorial function again.

fact n | n == 0 = 1

       | n == 1 = 1
      | otherwise = n * fact (n - 1)

1

We check the first predicate. If it’s true, we do whatever is on the right. If not, move on to the next predicate.

fact n | n == 0 = 1

       | n == 1 = 1
      | otherwise = n * fact (n - 1)

1

That was false, so we move on to the next predicate.

fact n | n == 0 = 1

       | n == 1 = 1
       | otherwise = n * fact (n - 1)

1

That predicate was true, so we do what’s on the right of the equals sign next to it. It just says 1, so we return 1.

quadroots :: Float -> Float -> Float -> String
quadroots a b c | a ==
0 = error "Not quadratic"
               | b*b
-4*a*c == 0 = "Root is " ++ show (-b/2*a)
               | otherwise =
"Upper Root is "
                      ++ show ((-b + sqrt(abs(b*b
-4*a*c)))/2*a))
                      ++
"and Lower Root is "
                      ++ show ((-b - sqrt(abs(b*b
-4*a*c)))/2*a))

‘where’ vs ‘let’ and ‘in’

quadroots :: Float -> Float -> Float -> String
quadroots a b c | a==
0 = error "Not quadratic"
               | discriminant==
0 = "Root is " ++ show centre
               | otherwise =
"Upper Root is "
                      ++ show (centre + offset)
                      ++
" and Lower Root is "
                      ++ show (centre - offset)
   
where discriminant = abs(b*b-4*a*c)
    centre = -b/
2*a
    offset = sqrt(discriminant/
2*a)

add x y = let z = x + y in
   z

quadadd a b c d =
   
let { e = a + b; f = c + d } in
       e + f

quadadd a b c d =
   
let e = a + b in
       
let f = c + d in
           e + f

Pattern matching

not :: Bool -> Bool
not
False = True
not
True = False

nonzero :: Int -> Bool

nonzero 0 = False

nonzero _ = True 

(&&) :: Bool -> Bool -> Bool
True && b = b
False && _ = False

True && ((5 * 3 + 1) < (8 * 2 - 6))

foo (x,_) = x

foo [5, a, 4] = a

tail (x:xs) = xs

addFirstTwoFromList (x:y:xs) = x + y
oneElementOnly (x:[]) =
True

fetch :: Int -> [a] -> a
fetch _ [] = error
"Empty List"
fetch
0 (x:_) = x
fetch n (_:xs) = fetch (n
-1) xs

Lambda expressions

add :: Int -> Int -> Int
add x y = x + y


add
5 6

(\x -> \y -> x + y) 5 6

or

(\x y -> x + y) 5 6

Operator sections

add5 :: Int -> Int
add5 x = x +
5

(+5)

List Comprehension and Recursion

List comprehension

Zips

> zip ['a', 'b', 'c'] [1, 2, 3, 4]
[ ('a',
1), ('b', 2), ('c', 3) ]

STICKY FINGAAS!!!

pairs :: [a] -> [ (a,a) ]
pairs xs = zip xs (tail xs)

> pairs [
1,2,3,4]
[(
1,2),(2,3),(3,4)]

sorted :: Ord a => [a] -> Bool
sorted xs = and [ x≤y | (x,y) <- pairs xs ]

Recursion

fac 0 = 1
fac n = n * fac (n
-1)

length :: [a] -> Int
length [] =
0
length (x:xs) =
1 + length xs

drop 0 xs = xs
drop _ [] = []
drop n (_:xs) = drop (n
-1) xs

evens :: [a] -> [a]
evens [] = []
evens (x:xs) = x : odds xs


odds :: [a]
-> [a]
odds [] = []
odds (x:xs) = evens xs

Tail recursion

Tail recursion

No tail recursion

fac' :: Int -> Int -> Int
fac' acc
0 = acc
fac' acc n = fac' (n*acc) (n
-1)

fac'
1 5 -- Start
fac'
5 4
fac'
20 3
fac'
60 2
fac'
120 1
fac'
120 0
120

fac :: Int -> Int
fac
1 = 1
fac n = n * fac (n
-1)

fac
5 -- Start
5 * fac 4
5 * 4 * fac 3
5 * 4 * 3 * fac 2
5 * 4 * 3 * 2 * fac 1
5 * 4 * 3 * 2 * 1
120


Higher Order Functions

func1 :: (a -> b) -> a

func2 :: a -> (b -> a)

Map, filter and fold

map (\x -> x + 5) [1,2,3]

map (+5) [1,2,3]
-- result is [6,7,8]

filter (\x -> x == 5) [1,2,3,4,5]

filter (==5) [1,2,3,4,5]
-- result is [5]

foldr (\x acc -> x + acc) 0 [1,2,3]

foldr (+) 0 [1,2,3]

Dollar operator

sqrt 3^2 + 4^2

sqrt $ 3^2 + 4^2

Function composition

odd x = not (even x)

odd = not . even

Declaring Types

Declaring Types and Classes

‘type’

type Pos = (Int, Int)

type Pair a b = (a,b)

type Pair a b = (a, b)

f :: (
Integral a, Integral b) => Pair a b -> Pair a b
f (x,y) = (x+
1, y+1)

type Pos = (Int,Int)
type Translation = Pos -> Pos    -- Niiicee!!

type Tree = (Int, [Tree])        -- Ohh noo!!

‘data’

data Pair = PairInt Int Int | PairString String String

-- RIGHT

PairInt 5 6
PairString "filthy acts" "at a reasonable price"

-- W R O N G

PairInt "killer queen" "bites the dust"
PairString 4 4

data Maybe a = Nothing | Just a

data BinaryTree a = Leaf a | Node a (BinaryTree a) (BinaryTree a)

Node 4 (Node 3 (Leaf 1) (Leaf 2)) Leaf 5 -- you could have this, for example

getLeftBranch :: BinaryTree a -> BinaryTree a
getLeftBranch (
Leaf a) = Leaf a
getLeftBranch (
Node a x y) = x

‘newtype’

newtype Pair = Pair (Int, Int)

‘class’

class Tree a where
   flatten :: a b -> [b]

‘instance’

instance Tree BinaryTree where
   flatten (
Leaf v) = [v]
   flatten (
Node v x y) = [v] ++ flatten x ++ flatten y

Trees

Red-Black Trees

data RBTree a =
 
Leaf a
 |
RedNode a (RBTree a) (RBTree a)
 |
BlackNode a (RBTree a) (RBTree a)

blackH (Leaf _ ) = 0
blackH (
RedNode _ l r) = maxlr

  where maxlr = max (blackH l) (blackH r)
blackH (
BlackNode _ l r) = 1 + maxlr
 
where maxlr = max (blackH l) (blackH r)

Abstract Syntax Trees

data Expr = Val Int | Add Expr Expr | Sub Expr Expr
eval ::
Expr -> Int
eval (
Val n) = n
eval (
Add e1 e2) = eval e1 + eval e2
eval (
Sub e1 e2) = eval e1 - eval e2

-- Example
eval (
Add (Val 10) (Val 20)) -- Would return 30
eval (
Sub (Val 20) (Val 5)) -- Would return 15

-- Data type for propositional expression
data Prop = Const Bool
|
Var Char
|
Not Prop
|
And Prop Prop
|
Imply Prop Prop

-- Data type for a single pair of variable to value
type Subst = [ (Char, Bool) ]

-- Takes a var, a substitution pair and returns the value that the var is paired with
find ::
Char -> Subst -> Bool
find k t = head [ v | (k',v) <- t, k == k' ]

-- Evaluates a propositional expression
eval ::
Subst -> Prop -> Bool
eval s (
Const b) = b
eval s (
Var c) = find c s
eval s (
Not p) = not $ eval s p
eval s (
And p q) = eval s p && eval s q
eval s (
Imply p q) = eval s p <= eval s q

-- Examples
eval [] (
And (Const False) (Const True)) -- Would return False
eval [('a',
True)] (Var 'a') -- Would return True

Functors

class Functor f where
 fmap :: (a -> b) -> f a -> f b

instance Functor [] where
 fmap = map

instance Functor Maybe where
 fmap _
Nothing = Nothing
 fmap g (
Just x) = Just (g x)

fmap id = id

fmap (g.h) = fmap g . fmap h

instance Functor BinaryTree where
 fmap g (
Leaf v) = Leaf (g v)
 fmap g (
Node v x y) = Node (g v) (fmap g x) (fmap g y)

fmap (\x -> x + 10) (Node 5 (Leaf 3) (Leaf 6))
-- this will return: Node 15 (Leaf 13) (Leaf 16))

Directions, trails and zippers

data Direction = L | R
type Directions = [ Direction ]

elemAt ::
Directions -> Tree a -> a
elemAt _ (
Leaf x) = x
elemAt (
L:ds) (Node _ l _) = elemAt ds l  
elemAt (
R:ds) (Node _ _ r) = elemAt ds r  
elemAt [] (
Node x _ _) = x

-- Examples
elemAt [
L] (Node 5 (Leaf 3) (Leaf 4)) -- returns 3
elemAt [
R, L] (Node 5 (Leaf 6) (Node 2 (Leaf 8) (Leaf 9))) -- returns 8

type Trail = [Direction]

goLeft :: (
Tree a, Trail) -> (Tree a, Trail)
goLeft (
Node _ l _ , ts) = (l , L:ts)
goRight :: (
Tree a, Trail) -> (Tree a, Trail)
goRight (
Node _ _ r , ts) = (r , R:ts)

-- Examples
(goLeft . goRight) (a, [])
-- for some tree 'a', this will return (b, [L, R]) where 'b' is the subtree if you go right, then left in 'a'

data BinaryTree a = Leaf a | Node a (BinaryTree a) (BinaryTree a) deriving (Show)

data Direction a = L (BinaryTree a) | R (BinaryTree a) deriving (Show)
type Trail a = [ Direction a ]

parentInDirection (
L p) = p
parentInDirection (
R p) = p

goLeft :: (
BinaryTree a, Trail a) -> (BinaryTree a, Trail a)
goLeft (
Leaf x, ts)           = (Leaf x, ts)
goLeft ( p@(
Node _ l _) , ts) = (l, (L p):ts)

goRight :: (
BinaryTree a, Trail a) -> (BinaryTree a, Trail a)
goRight (
Leaf x, ts)           = (Leaf x, ts)
goRight ( p@(
Node _ _ r) , ts) = (r, (R p):ts)

goUp :: (
BinaryTree a, Trail a) -> (BinaryTree a, Trail a)
goUp (tree, ts) = (parent, restOfList)
 
where
   latestMove = head ts
   restOfList = tail ts
   parent = parentInDirection latestMove

-- Example
(goUp . goLeft) (tree, [])
-- this will return (tree, []) because goLeft followed by goUp effectively does nothing, like taking a step forward then taking a step back

ZIPPER MAN!

Graphs

Indexed collections of Nodes, Edges

graph :: Int -> [ Int ]

type Table a = Array Vertex a
type Graph = Table [ Vertex ]

Structured data type with cyclic dependencies

data Graph a = GNode a (Graph a)

mkGraph :: [ (a , Int) ] -> Graph a

ID

Value

Next node

1

London

3

2

Berlin

4

3

Rome

2

4

Morioh

1

mkGraph :: [ (a, Int) ] -> Graph a
mkGraph table = table' !!
0
 
where table' =
 map (\(x,n) ->
GNode x (table'!!n) ) table

data GGraph a = GGNode a [GGraph a]


mkGGraph :: [ (a, [
Int]) ] -> GGraph a
mkGGraph table = table' !!
0
 
where table' =
 map (\(x,ns) ->
GGNode x (map (table'!!) ns ) table

Inductive approach with graph constructors

empty :: Graph a b
embed ::
Context a b -> Graph a b -> Graph a b

type Adj b = [ (b,Node) ]
type Context a b = (Adj b , Node, a , Adj b)

match :: Node -> Graph a b -> Decomp a b

type Decomp a b = ( Maybe (Context a b), Graph a b )

matchAny :: Graph a b -> Decomp a b

gmap :: (Context a b -> Context c b) -> Graph a b -> Graph c b
gmap f g

  | isEmpty g = empty
 | otherwise = embed (f c) (gmap f g')
   
where (c, g') = matchAny g


Evaluation Order and Laziness

Equational reasoning

data Nat = Zero | Succ Nat

add :: Nat -> Nat -> Nat
add
Zero m = m
add (
Succ n) m = Succ (add n m)

Base Case

Inductive Case

add Zero (add y z) -- START
add (add
Zero y) z -- GOAL

 add
Zero (add y z)
= { defn
of add }
 add y z
= { defn
of add 'backwards'}
 add (add
Zero y) z

add (Succ x) (add y z) -- START
add ( (add (
Succ x) y) z ) -- GOAL

 add (
Succ x) (add y z)
= { defn
of add }
 
Succ (add x (add y z) )
= { inductive hypothesis }
 
Succ (add (add x y) z)
= { defn
of add 'backwards'}
 add (
Succ (add x y) z )
= { defn
of add 'backwards'}
 add ( (add (
Succ x) y) z )

Redex

Beta-reduction

Call-By-Name

take 1 [1, 2, 3, 4...]

replicate 10 (6π^2)

Call-By-Value

take 1 [1, 2, 3, 4...]

Modularity

Solution A (the good one)

Solution B (the crap one)

ones = 1 : ones

take
0 _ = []
take _ [] = []
take n (x:xs) =
   x : take (n
-1) xs

take
300 ones

replicate 0 _ = []
replicate n x =
   x : replicate (n
-1) x

replicate
300 1

Strict application

Step

Code

1

square $! (1 + 2)

2

square $! (3)

3

square 3

4

9


Interpreters and Closures

Part 1 - Substitutions

Lambda calculus

Rule

Description

Format

Example

Variable

It’s just a variable on it’s own.

Just some symbol on it’s own

x

x

y

Function abstraction

A function definition

A lambda character, followed by a variable name, followed by a full stop, followed by the function body which is another lambda expression

λ(some variable).(some lambda expression)

They can be curried to have more parameters

λ(some variable).λ(anothervariable).λ(yet another variable) … .(some lambda expression)

Instead of dots, you can use an arrow, if you wish

λx.x

λx.λy.y

λx.λx.x

λx.λy.λz.y

OR

λxx

λxλyy

λxλxx

λxλyλzy

Function application

A function being applied to some expression

It’s just an expression separated by an expression with a space

(a lambda expression) (another lambda expression)

It represents calling a function with some input

λx.x x

λx.λy.y y

x y

λx.λy.y λy.λy.y

Beta reduction syntax

Alpha conversion

Part 2 - Machines

Environments

Expression

Environment

Before beta reduction

(λx -> e1) e2

Nothing

After beta reduction

e1

x is mapped to e2

Frames

Expression

What do we do?

x

It’s just a variable. We can’t simplify this down any further, so just leave it. It’s terminated.

λx -> e

This is just a lambda term on it’s own. We can’t simplify this any further, so leave it. It’s terminated.

(λx -> e1) e2

This is an application, which can be reduced. First of all, we reduce e2, then we perform beta reduction.

e1 e2

We can simplify this, also. If we’re doing left-most, we simplify e1 then e2, and if we’re doing right-most, we simplify e2 and then e1.

We will be doing left-most for now.

Continuations

CEK-machines

#

C

E

K

C

E

K

1

x

E

K

“lookup x in E”

E

K

2

e1 e2

E

K

e1

E

[-] e2 :: K

3

V

E

[-] e :: K

e

E

V [-] :: K

4

V

E

(λx -> e) [-] :: K

e

E [x := V]

k

R1: x     | E | K                   “lookup x in E” | E          | K

R2: e1 e2 | E | K                    e1              | E          | [-] e2 :: K

R3: V     | E | [-] e :: K           e               | E          | V [-] :: K

R4: V     | E | (λx -> e) [-] :: K   e               | E [x := V] | K

Rule #

Explanation

1

If we see a single variable on it’s own, look it up in the environment and replace it with that corresponding expression.

2

If we see an application, take out the left expression for simplifying and put the right expression onto the stack.

3

If we have a fully simplified expression and there’s an application on the stack that has a left-side missing, put the left side back and take out the right-side for simplifying.

4

If we have a fully simplified expression and there’s a lambda application on the stack that has a right-side missing, perform beta reduction on our terminated value and that function application.

Closures

#

C

E

K

C

E

K

1

x

E1

K

λx -> e

E2

K

2

e1 e2

E

K

e1

E

[-] e2 E :: K

3

λx -> e

E

K

cl(λx -> e, E)

E

K

4

W

E1

[-] e E2 :: K

e

E2

W [-] :: K

5

W

E1

cl(λx -> e, E2) [-] :: K

e

E2 [x := W]

K

R1: x       | E1 | K ⟼ λx -> e | E2 | K where lookup x in E1 is cl(λx -> e, E2)

R2: e1 e2   | E | K ⟼ e1 | E | [-] e2 E :: K

R3: λx -> e | E | K ⟼ cl(λx -> e, E) | E | K

R4: W       | E1 | [-] e E2 :: K ⟼ e | E2 | W [-] :: K

R5: W       | E1 | cl(λx -> e, E2) [-] :: K e | E2 [x := W] | K 

Rule #

Explanation

1

A simple variable look-up, this time with closures. I’m not sure why the slides made it so complicated; it’s just a look-up as far as I can see.

2

If there is an application, pluck out the left-side and put the rest on the continuation stack along with a copy of the current environment.

3

If there is a function, wrap it in a closure along with a copy of the current environment.

4

If we have a terminated value and a right-side only application is on top of the stack, then take the right-side to simplify and put the left-side (our terminated value) back into the stack.

5

If we have a terminated value and a closure on the stack, then pop the closure off the stack, perform beta reduction with the closure function and the terminated value and add the new pairing to the environment.

Example sequence

Step #

Rule # used

C

E

K

Explanation

1

N/A

(λx → λy → x) e1 e2

[]

Nothing has been done yet; this is like our “initial state”.

2

R2

(λx → λy → x) e1

([-] e2 ∅) ::

[]

We have an application, so R2 is applied.

The left side of the application is plucked and stored in control, and a new frame is created and pushed, which stores the other side along with a copy of the environment at the time of creation.

3

R2

(λx → λy → x)

([-] e1 ∅) ::

([-] e2 ∅) ::

[]

There is another application, so R2 is used again.

Like with the previous step, the left-hand side is stored and the right-hand side is pushed as a frame, with a copy of the environment with it.

4

R3

cl(λx → λy → x,

         ∅)

([-] e1 ∅) ::

([-] e2 ∅) ::

[]

A raw function is found! We apply R3.

We create and store a closure of this function with the current environment.

5

R4

e1

cl(λx → λy → x,

         ∅) [-] ::

([-] e2 ∅) ::

[]

We have a closure, and an application is on the stack. We use R4.

This is just like the rule before closures, but this time it’s with closures; we put the left expression back and we now take out the right expression.

6

R5

λy → x

[x := e1]

([-] e2 ∅) ::

[]

We have a terminated value and a closure on the stack, so we use R5.

We take out the environment in the frame and use that (which was nothing to begin with), then we add a new pairing: the parameter of the function in the closure to the expression in the control section. The expression in the function of the closure goes into our control section.

7

R3

cl(λy → x,

       [x := e1])

[x := e1]

([-] e2 ∅) ::

[]

We’ve found another raw function, so yet again, we put a closure around it and add a copy of the current environment to it.

8

R4

e2

cl(λy → x,

     [x := e1]) [-] ::

[]

We’ve got a closure and another application on the stack, so we use R4.

Simply, we put the left-side expression back and take out the right-side expression to simplify.

9

R5

x

[x := e1,

y := e2]

[]

We have a terminating value and a closure on the stack, so we use R5.

Again, the environment in the closure is used and we add an extra pairing of the closure function’s parameter to the expression in the control section.

The body of the closure function is now in the new control section.

10

R1

e1

[x := e1,

y := e2]

[]

We have a single value we need to convert, so we use R1, which looks up the value of x and replaces it with what it finds.

DONE


Functional I/O and Monads

I/O in Haskell

IO a

Actions

Do notation

do p1 <- act1
  p2 <- act2

   .

   .

   .

   pn <- actn
  actfinal

firstThird :: IO (Char,Char)
firstThird =
do x <- getChar
               getChar
               y <- getChar
               return (x,y)

putStr :: String → IO ()
putStr [] = return ()
putStr (x:xs) =
do putChar x

                   putStr xs

putStrLn :: String → IO ()
putStrLn xs =
do putStr xs

                 putChar '\n'

getLine :: IO String
getLine =
do x <- getChar

            if x == '\n' then

              return []

            else

              do

                xs <- getLine

                return (x:xs)

Main Function, File Handling, Random Numbers

type FilePath = String
readFile ::
FilePath -> IO String
writeFile ::
FilePath -> String -> IO ()
appendFile ::
FilePath -> String -> IO ()

Applicatives

class Functor f => Applicative f where
 pure :: a -> f a
 (<*>) :: f (a -> b) -> f a -> f b

pure (\x y -> x + y) <*> [1, 2, 3] <*> [10, 20, 30]

(<*>) :: IO (a -> b) -> IO a -> IO b

mg <*> mx = do g <- mg

               x <- mx

               return (g x)

getChars :: Int -> IO String
getChars
0 = return ""
getChars n = pure (:) <*> getChar <*> getChars (n
- 1)

getChars :: Int -> String
getChars
0 = ""
getChars n = getChar : getChars(n -
1)

do
  str <- getChars
5
  return str

pure id <*> x = x

pure (g x) = pure g <*> pure x

x <*> pure y = pure (\g -> g y) <*> x

x <*> (y <*> z) = (pure (.) <*> x <*> y) <*> z

Monads

class Applicative m => Monad m where
 return :: a -> m a
 (>>=) :: m a -> (a -> m b) -> m b
 return = pure

return x >>= f = f x

mx >>= return = mx

(mx >>= f) >>= g = mx >>= (\x -> (f x >>= g))

Use of monads: Error handling

data Expr = Val Int | Div Expr Expr

eval :: Expr -> Int

eval (Val n) = n

eval (Div x y) = eval x `div` eval y

Just x >>= f

Nothing >>= f

Just (f x)

Nothing

eval :: Expr -> Maybe Int
eval (
Val n) = Just n
eval (
Div x y) = eval x >>= \n ->
                eval y >>= \m ->
                safediv n m

safediv ::
Int -> Int -> Maybe Int
safediv _
0 = Nothing
safediv n m =
Just (n `div` m)

eval :: Expr -> Maybe Int
eval (
Val n) = Just n
eval (
Div x y) = do

                   n <- eval x
                  m <- eval y
                  safediv n m

Use of monads: Chaining

Just 10 >>= (\x -> Just (x + 10)) >>= (\x -> Just (x * 2))

Use of monads: Non-determinism

xs >>= f = [ y | x <- xs, y <- f x ]

type KnightPos = (Int,Int)


moveKnight ::
KnightPos -> [ KnightPos ]

moveKnight (c,r) = filter onBoard

 [ (c+2,r-1), (c+2,r+1), (c-2,r-1), (c-2,r+1),

   (c+1,r-2), (c+1,r+2), (c-1,r-2), (c-1,r+2) ]

  where onBoard (c,r) = c `elem` [1..8] && r `elem` [1..8]

in3moves :: KnightPos -> [ KnightPos ]

in3moves start = return start >>= moveKnight >>= moveKnight >>= moveKnight

mapM

mapM :: Monad m => (a -> m b) -> [a] -> m [b]

mapM f [] = return []

mapM f (x:xs) = do y <- f x

                   ys <- mapM f xs

                   return (y:ys)

do
 y1 <- f x1
 y2 <- f x2
 y3 <- f x3
 .
 .
 .
 yn <- f xn
 return (y1 : y2 : y3 : ... : yn : [])

do

  x1 <- (\x -> [x,-x]) 1

  x2 <- (\x -> [x,-x]) 2

  x3 <- (\x -> [x,-x]) 3

  return (x1 : x2 : x3 : [])

Step #

Code

Values

Explanation

1

do

  x1 <- (\x -> [x,-x]) 1

  x2 <- (\x -> [x,-x]) 2

  x3 <- (\x -> [x,-x]) 3

  return (x1 : x2 : x3 : [])

x1 = N/A

x2 = N/A

x3 = N/A

We’ve just entered the ‘do’ block.

In the ‘Code’ column, the red highlighted bit shows the lines where the computation has already processed.

1

do

  x1 <- [1, -1]

  x2 <- [2, -2]

  x3 <- [3, -3]

  return (x1 : x2 : x3 : [])

x1 = N/A

x2 = N/A

x3 = N/A

Just to make things a bit easier for us, let’s simplify those lambda calls on the right. It’s easy to see what they return, and it’ll just complicate things if we leave them. It doesn’t change anything.

Normally, GHCI will lazily evaluate them, but just for the example’s sake, we’ve simplified those now.

2

do

  x1 <- [1, -1]

  x2 <- [2, -2]

  x3 <- [3, -3]

  return (x1 : x2 : x3 : [])

x1 = 1

x2 = N/A

x3 = N/A

Now, we’re looking at the first line.

Remember how list monads work? The bind operator runs the function on all the values within the list, so the function will run twice here: one with 1 as the input and one with -1 as the input.

But where’s the “function” here? We’re in a do block. Remember, do is syntactic sugar. If you look at this expressed with bind operators, you’ll see that our “function” is just the rest of the do block, the bits that aren’t highlighted in red.

So now, x1 is 1.

3

do

  x1 <- [1, -1]

  x2 <- [2, -2]

  x3 <- [3, -3]

  return (x1 : x2 : x3 : [])

x1 = 1

x2 = 2

x3 = N/A

Again, the same thing applies and the “function” here will be run twice: one with 2 and one with -2.

4

do

  x1 <- [1, -1]

  x2 <- [2, -2]

  x3 <- [3, -3]

  return (x1 : x2 : x3 : [])

x1 = 1

x2 = 2

x3 = 3

Yet again, the function will be called twice and x3 will be 3 and will soon be -3.

5

do

  x1 <- [1, -1]

  x2 <- [2, -2]

  x3 <- [3, -3]

  return (x1 : x2 : x3 : [])

x1 = 1

x2 = 2

x3 = 3

[1, 2, 3]

Now we’re at the return. Because we’re using the list monad, return will bunch these values all into a list, so it’ll return [1, 2, 3].

6

do

  x1 <- [1, -1]

  x2 <- [2, -2]

  x3 <- [3, -3]

  return (x1 : x2 : x3 : [])

x1 = 1

x2 = 2

x3 = -3

We’ve reached return; it’s all over, right? Hold it! Remember how the functions are repeated for each value in the list? Now, the computation falls back to x3. The function is called again and x3 becomes -3.

7

do

  x1 <- [1, -1]

  x2 <- [2, -2]

  x3 <- [3, -3]

  return (x1 : x2 : x3 : [])

x1 = 1

x2 = 2

x3 = -3

[1, 2, -3]

We now get [1, 2, -3] since x3 has a new value.

8

do

  x1 <- [1, -1]

  x2 <- [2, -2]

  x3 <- [3, -3]

  return (x1 : x2 : x3 : [])

x1 = 1

x2 = -2

x3 = N/A

x3 is done for this branch, but now we go further back and x2 becomes -2.

9

do

  x1 <- [1, -1]

  x2 <- [2, -2]

  x3 <- [3, -3]

  return (x1 : x2 : x3 : [])

x1 = 1

x2 = -2

x3 = 3

Now we’re going back into the x3 bit and x3 is going to become 3 and -3, except this time, x2 is -2.

10

do

  x1 <- [1, -1]

  x2 <- [2, -2]

  x3 <- [3, -3]

  return (x1 : x2 : x3 : [])

x1 = 1

x2 = -2

x3 = 3

[1, -2, 3]

We’ve reached return again, and now we’ve got [1, -2, 3].

Hopefully, you get the picture; all the combinations will be reached. I’m going to stop now, because this could go on for a while.

fitlerM

filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
filterM p [] = return []
filterM p (x:xs) =
do b <- p x
                     ys <- filterM p xs
                     return (
if b then x:ys else ys)

do

  y1 <- p x1

  y2 <- p x2

  y3 <- p x3

  .

  .

  .

  yn <- p xn

  return [ x1 if y1 is true       (note: not actual Haskell!)

           x2 if y2 is true

           x3 if y3 is true

           .

           .

           .

           xn if yn is true ]

powerlist = filterM (\x -> [True, False])

Output elements

filterM

mapM

[1,2,3]

1 is inside

2 is inside

3 is inside

1 is positive

2 is positive

3 is positive

[1,2] or [1,2,-3]

1 is inside

2 is inside

3 is not inside

1 is positive

2 is positive

3 is negative

[1,3] or [1,-2,3]

1 is inside

2 is not inside

3 is inside

1 is positive

2 is negative

3 is positive

[1] or [1,-2,-3]

1 is inside

2 is not inside

3 is not inside

1 is positive

2 is negative

3 is negative

[2,3] or [-1,2,3]

1 is not inside

2 is inside

3 is inside

1 is negative

2 is positive

3 is positive

[2] or [-1,2,-3]

1 is not inside

2 is inside

3 is not inside

1 is negative

2 is positive

3 is negative


Functional Programming in Java

Functions as Objects

class Double {
        
int apply(int x) {
                
return 2*x;
        }
}

double :: Num a => a -> a
double x =
2*x

Functional Interfaces

@FunctionalInterface

interface Function<T, R> {
        R
apply(T x);
}

ActionListener

JButton testButton = new JButton("Test Button");
testButton.addActionListener(
new ActionListener(){
 
@Override
 
public void actionPerformed(ActionEvent ae){
      System.out.println(
"Click Detected by Anon Class");
 }
});

 

JButton testButton = new JButton("Test Button");
testButton.addActionListener(
 ae -> System.out.println(
"Click Detected by Anon Class")
);

Lambda Syntax

// single argument, no parentheses, omitting "return"
s -> s.length()
// no arguments, parentheses needed, omitting "return"
() ->
42
// two arguments, explicit types, parentheses needed, omitting "return"
(
int x, int y) -> x+y
// three arguments, implicit types, block body
(x, y, z) -> {
        
if (x > y) return z;
        
else return -z;
}

More general function types

interface MapList<T,U> {
        List<U>
apply(Function<T,U> fun, List<T> list);
}

public class MyMapList<T, U> implements MapList<T, U> {
   
@Override
   
public List<U> apply(Function<T, U> fun, List<T> list) {
       List<U> out =
new ArrayList<>();
       
for (T element : list) {
           out.add(fun.apply(element));
       }
       
return out;
   }
}

MyMapList<Integer, Integer> mapper = new MyMapList<>();
List<Integer> list = …;
// [1, 3, 6, 2, 5, 4]


Function<Integer, Integer> fun1 = x -> x*
2;
List<Integer> newList1 = mapper.apply(fun1, list);

// newList1 = [2, 6, 12, 4, 10, 8] 
List<Integer> newList2 = mapper.apply(x -> x+
1, list);

// newList2 = [2, 4, 7, 3, 6, 5]

Closure: lambda vs anonymous inner classes (AICs)

void fn() {
   
int myVar = 42;
    Supplier<Integer> lambdaFun = () -> myVar;
// does not compile because myVar is not effectively final
    myVar++;
    System.out.println(lambdaFun.get());
}

private static class MyClosure {
   
public int value;
   
public MyClosure(int initValue) { this.value = initValue; }
}
void fn2() {
    MyClosure myClosure =
new MyClosure(42);
    Supplier<Integer> lambdaFun = () -> myClosure.value;
// compiles because the reference is effectively final
    myClosure.value++;
    System.out.println(lambdaFun.get());
// prints 43
}

Method references

List<Integer> list = ...; // [-5, 4, -3, -2, 1]
List<Integer> newList3 = mapper.apply(x -> Math.abs(x), list);

// newList3 = [5, 4, 3, 2, 1]

List<Integer> list = ...; // [-5, 4, -3, -2, 1]
List<Integer> newList3 = mapper.apply(Math::abs, list);

// newList3 = [5, 4, 3, 2, 1]

private static <T> void listAll(Function<Person, T> f, List<Person> ps) {
       
for (Person p : ps) {
           System.out.println(f.apply(p));
       }
}

List<Person> people = List.of( ... ); // a list of some people
listAll(Person::getName, people);
listAll(Person::getHeight, people);

Recursion

class FactNonExample {
   
static Function<Integer,Integer> f = i -> (i==0)? 1 : i *      

                                        f.apply(i-1);
   
int fact(int n) {
       
return f.apply(n);
   }
}

public class FactExample {

   
private class Recursive<I> {
       I f;
   }

   
private Recursive<Function<Integer,Integer>> rec =

                                                      new Recursive<>();

   
public FactExample() {
       rec.f = i -> (i==
0)? 1 : i * rec.f.apply(i-1);
   }

   
int fact(int n) {
       
return rec.f.apply(n);
   }

}


Programming with Streams

Functional programming and lists

External vs internal iteration

Iterator it = shapes.getIterator()
while (it.hasNext()){
   Shape s = it.next();
   s.setColor(Color.RED)
}

shapes.forEach(s -> s.setColor(Color.RED));

Streams in Java

String[] array = ...
Set<String> hash = ...
Stream<String> arrstr = Arrays.stream(array);
Stream<String> hashstr = hash.stream();

Stream<Integer> stream = Stream.of(1, 2, 3, 4);

Common operations

Map - Streams as Functors

interface Stream<T> {

    <R> Stream<R> map(Function<T, R> mapper);

    …

}

Stream.of(1, 2, 3, 4)
     .map(num -> num * num)
     .forEach(System.out::println);
// 1 4 9 16

flatMap - Streams as Monads

interface Stream<T> {
   <R> Stream<R>
flatMap(Function<T, Stream<R>> mapper);
}

Stream.of(1, 2, 3, 4)
   .flatMap(num -> Stream.of(num * num))
   .forEach(System.out::println);
// 1 4 9 16

More stream operations yay

Intermediate Operations

filter

Takes a predicate and returns a stream with elements that satisfy the predicate.

Haskell Equivalent : filter

peek

Takes a consumer and returns a stream with the same elements but also feeds each element to the consumer.

distinct

Returns a stream with duplicate elements removed (it uses .equals for checking equivalency).

Haskell Equivalent : nub

sorted

Returns the stream sorted to their natural order (only for Streams of Comparable elements possible).

Haskell Equivalent : sort

iterate

Takes a unary operator and a start element and produces an infinite stream by repeatedly applying the function.

Haskell Equivalent : iterate

Terminal Operations

forEach

Takes a consumer and feeds each element in the stream to it. Unlike peek it does not produce an output stream.

toArray

Simply converts the stream to an array and closes the stream.

reduce

Similar to a fold in Haskell. Takes a base element, and a binary operator and applies it element wise across the stream by accumulating the result. Note that no guarantee of order is given.

max, min, count

Examples of specific reduce operations

Haskell Equivalent : maximum, minimum, length

collect

Converts the stream to a collection according to a specified Collector and closes the stream.

List<String> jobs = ps.stream() // Stream<Person>
                     .map(x -> x.getJobs())
// Stream<Set<String>>
                     .flatMap(x -> x.stream())
// Stream<String>
                     .distinct()
// Stream<String>
                     .collect(Collectors.toList());
// List<String>

State of Streams

Stream<Integer> str = Stream.of(10, 2, 33, 45);
Stream<Integer> strF = str.filter(x -> x <
30 );
Stream<Integer> strM = str.map(x -> x +
5 ); // Exception thrown here

Optional

Parallel streams

public class Perfect {
   
static boolean perfect(int n){
       
int factorSum = IntStream.range(1, n)
               .filter(x -> (n % x) ==
0)
               .sum();
       
return factorSum == n;
   }
}

public static void main(String[] args) {
   IntStream.range(
1,50000)
           .parallel()
           .filter(Perfect::perfect)
           .forEach(i -> System.out.println(i +
" is a perfect number." ));
}

8128 is a perfect number.
6 is a perfect number.
28 is a perfect number.
496 is a perfect number.


Functional Programming in JavaScript

Object-Oriented

Functional

Data and the operations upon it are tightly coupled

Data is only loosely coupled to functions

Objects hide their implementation of operations from other objects via their interfaces

Functions hide their implementation, and the language’s abstractions speak to functions and the way they are combined or expressed

The central model for abstraction is the data itself

The central model for abstraction is the function, not the data structure

The central activity is composing new objects and extending existing objects by adding new methods to them

The central activity is writing new functions

Functional vs Imperative Style

var sumOfSquares = function(list) {
   
var result = 0;
   
for (var i = 0; i < list.length; i++) {
       result += square(list[i]);
   }
   
return result;
};
console.log(sumOfSquares([2, 3, 5])); // prints 38

var sumOfSquares = pipe(map(square), reduce(add, 0));
console.log(sumOfSquares([2, 3, 5])); // prints 38

Functional Features

Functional Programming in JS with Rambda

var data = {
   result:
"SUCCESS",
   interfaceVersion:
"1.0.3",
   requested:
"10/17/2013 15:31:20".
   lastUpdated:
"10/16/2013 10:52:39",
   tasks: [
       {id:
104, complete: false,            priority: "high",
                 dueDate:
"11/29/2013",      member: "Scott",
                 title:
"Do something",      created: "9/22/2013"},
       {id:
105, complete: false,            priority: "medium",
                 dueDate:
"11/22/2013",      member: "Lena",
                 title:
"Do something else", created: "9/22/2013"},
       {id:
107, complete: true,             priority: "high",
                 dueDate:
"11/22/2013",      member: "Mike",
                 title:
"Fix the foo",       created: "9/22/2013"},
       {id:
108, complete: false,            priority: "low",
                 dueDate:
"11/15/2013",      member: "Punam",
                 title:
"Adjust the bar",    created: "9/25/2013"},
       {id:
110, complete: false,            priority: "medium",
                 dueDate:
"11/15/2013",      member: "Scott",
                 title:
"Rename everything", created: "10/2/2013"},
       {id:
112, complete: true,             priority: "high",
                 dueDate:
"11/27/2013",      member: "Lena",
                 title:
"Alter all quuxes",  created: "10/5/2013"}
       
// , ...
   ]
}

Iterative Approach

var getIncompleteTaskSummariesForMember_imperative = function(memberName) {
   
return fetchData()
       .then(
function(data) {
           
return data.tasks;
       })
       .then(
function(tasks) {
           
var results = [];
           
for (var i = 0, len = tasks.length; i < len; i++) {
               
if (tasks[i].member == memberName) {
                   results.push(tasks[i]);
               }
           }
           
return results;
       })
       .then(
function(tasks) {
           
var results = [];
           
for (var i = 0, len = tasks.length; i < len; i++) {
               
if (!tasks[i].complete) {
                   results.push(tasks[i]);
               }
           }
           
return results;
       })
      .then(
function(tasks) {
           
var results = [], task;
           
for (var i = 0, len = tasks.length; i < len; i++) {
               task = tasks[i];
               results.push({
                   id: task.id,
                   dueDate: task.dueDate,
                   title: task.title,
                   priority: task.priority
               })
           }
           
return results;
       })
       .then(
function(tasks) {
           tasks.sort(
function(first, second) {
               
return first.dueDate - second.dueDate;
           });
           
return tasks;
       });
};

Get a property

Get all tasks from data

Imperative

Functional

.then(function(data) {
   
return data.tasks;
})

.then(get('tasks'))

var get = curry(function(prop, obj) {
   
return obj[prop];
});

var get = function(prop) {
   
return function(obj) {
       
return obj[prop];
   };
};

Filtering

Filtering tasks by member name - first version

Imperative

Functional

.then(function(tasks) {
   
var results = [];
   
for (var i=0, len=tasks.length; i<len; i++)

    {
       
if (tasks[i].member == memberName) {
           results.push(tasks[i]);
       }
   }
   
return results;
})

.then(filter(function(task) {
   
return

       task.member == memberName;
}))

var propEq = function(prop, val) {
   
return function(obj) {
       
return obj[prop] === val;
   };
}

var propEq = function(prop, val) {
   
return pipe(get(prop), eq(val));
}

var propEq = use(pipe).over(get, eq);

Filtering tasks by member name - improved version

Imperative

Functional

.then(function(tasks) {
   
var results = [];
   
for (var i=0; i<tasks.length; i++)

    {
       
if (tasks[i].member == memberName) {
           results.push(tasks[i]);
       }
   }
   
return results;
})

.then(filter(

    propEq('member', memberName)

))

Rejecting

Rejecting all tasks that are completed

Imperative

Functional

.then(function(tasks) {
   
var results = [];
   
for (var i=0; i<tasks.length; i++) {
       
if (!tasks[i].complete) {
           results.push(tasks[i]);
       }
   }
   
return results;
})

.then(reject(
   propEq(
'complete', true)
))

New objects from old

Only keep some properties of every task

Imperative

Functional

.then(function(tasks) {
   
var results = [], task;
   
for (var i=0; i<tasks.length; i++) {
       task = tasks[i];
       results.push({
           id: task.id,
           dueDate: task.dueDate,
           title: task.title,
           priority: task.priority
       })
   }
   
return results;
})

.then(map(pick(

  ['id', 'dueDate', 'title', 'priority']

)))

Sorting

Sorting tasks by due date

Imperative

Functional

.then(function(tasks) {
   tasks.sort(
function(first, second) {
       
return first.dueDate - second.dueDate;
   });
   
return tasks;
});

.then(sortBy(get('dueDate')));

Functional Approach

var propEq = use(pipe).over(get, eq); // TODO: move to library?

var getIncompleteTaskSummariesForMemberFunctional = function(memberName) {
   
return fetchData()
       .then(get(
'tasks')) // Get a Property
       .then(filter(propEq(
'member', memberName))) // Filtering
       .then(reject(propEq(
'complete', true))) // Rejecting
        .then(map(pick(['id', 'dueDate', 'title', 'priority']))) //New Obj
       .then(sortBy(get(
'dueDate'))); // Sorting
};


TL;DR

Introduction to functional programming

Types, Classes and Functions

isThisOne x | x == 1 = True
           | otherwise =
False

List Comprehension and Recursion

Higher Order Functions

Declaring Types

type String = [Char]

data Pair = PairInt Int Int | PairString String String

newtype Pair = Pair (Int, Int)

class Functor f where
 fmap :: (a -> b) -> f a -> f b

instance Functor Tree where
 fmap f (
Leaf v) = Leaf (f v)
 fmap f (
Node v l r) = Node (f v) (fmap f l) (fmap f r)

Evaluation Order and Laziness

Interpreters and Closures

Functional I/O and Monads

Functional Programming in Java

Programming with Streams

Functional programming in JavaScript

Functional features in JS

Functional features not in JS

First-class functions

Lambdas/anonymous functions with closures

Stateless processing

Side-effect free function calls

Tail recursion

Pattern matching

Lazy evaluation

Functional programming in JS with Rambda

“Rambda” function

What does it do

curry(function)

Returns a curried version of function, so you can partially apply it and get new functions. This is used with all the below Rambda functions.

get(prop, obj)

Returns the property prop of the object obj.

filter(predicate, list)

Takes a predicate and a list and checks for each element whether the predicate is true or false.

It creates a new list with all the elements where the predicate is true.

pipe(fn1, fn2, ..., fnn)

Performs function composition from left to right, starting with fn1 and ending with fnn.

eq(obj1, obj2)

Returns true if obj1 and obj2 are equal, and returns false if not.

use(func).over(tf1, tf2, ..., tfn)

Returns a function which accepts N parameters, feeds them to their respective transformers, and then calls func using the results of all these as arguments.

reject(predicate, list)

Like filter, but does the opposite; it keeps elements where the predicate is false and rejects ones where it’s true.

map(function, array/object)

Maps over the array/object, applying the map function to all elements

pick(props, obj)

Similar to get, but props is an array selecting multiple properties to take out. It returns a new object.

sortBy(function, array)

Returns a copy of array sorted by function.

Recommended Reading

(QA 76.55A1 PEY) The Implementation of Functional Programming Languages, Simon L. Peyton Jones; Chapter 2: Gives a clear definition of lambda calculus as well as the lambda calculus techniques necessary for the lambda calculus coursework (assuming it still exists).