Programming III
Matthew Barnes, Mathias Ritter
Introduction to functional programming 5
Types, Classes and Functions 9
List Comprehension and Recursion 19
Declaring Types and Classes 24
Directions, trails and zippers 30
Indexed collections of Nodes, Edges 31
Structured data type with cyclic dependencies 31
Inductive approach with graph constructors 33
Evaluation Order and Laziness 35
Main Function, File Handling, Random Numbers 52
Use of monads: Error handling 58
Use of monads: Non-determinism 60
Functional Programming in Java 67
More general function types 70
Closure: lambda vs anonymous inner classes (AICs) 72
Functional programming and lists 77
External vs internal iteration 77
flatMap - Streams as Monads 80
Functional Programming in JavaScript 84
Functional vs Imperative Style 84
Functional Programming in JS with Rambda 85
Introduction to functional programming 93
Types, Classes and Functions 94
List Comprehension and Recursion 96
Evaluation Order and Laziness 98
Functional Programming in Java 101
Functional programming in JavaScript 103
Functional programming in JS with Rambda 103
Set theory |
Haskell |
|
add5 :: Int -> Int |
Function |
Description |
Example |
head |
Selects the first element in the list |
head [1, 2, 3, 4] |
tail |
Removes the first element in a list |
tail [1, 2, 3, 4] |
length |
Calculates the length of a list |
length [1, 2, 3, 4] |
!! |
Selects the nth element of a list |
[1, 2, 3, 4] !! 2 |
take |
Selects the first n elements of a list |
take 2 [1, 2, 3, 4] |
drop |
Removes the first n elements of a list |
drop 2 [1, 2, 3, 4] |
++ |
Appends two lists |
[1, 2] ++ [3, 4] |
sum |
Calculates the sum of the elements in a list |
sum [1, 2, 3, 4] |
product |
Calculates the product of the elements in a list |
product [1, 2, 3, 4] |
reverse |
Reverses a list |
reverse [1, 2, 3, 4] |
repeat |
Creates an infinite list of repeated elements |
repeat 5 |
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 |
(£) x y = x + y |
-- do this |
Implicit grouping |
Explicit grouping |
a = b + c where b = 1 c = 2 d = a * 2 |
a = b + c |
e :: t |
:type head
['j','g','c'] |
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 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] |
add :: Int -> (Int -> Int) |
mult :: Int → (Int → (Int → Int)) |
fst :: (a,b) → a |
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 |
Ord |
Supports operators like < and > |
isBigger x y = x > y |
Show |
Supports being converted into a string |
toString x = show x |
Read |
Supports strings being converted into this |
fromString x = read x |
Num |
Is either Int, Integer, Float or Double |
double x = x * 2 |
Integral |
Is either Int or Integer (supports div and mod) |
divmod x y = (div x y + mod x y) |
Fractional |
Is either Float or Double (supports / and recip, which means ‘reciprocal’) |
negrecip x = -1 * recip x |
Pattern matching |
Guarded equations |
fact 0 = 1 |
fact n | n == 0 = 1 |
Steps |
Value of n |
Explanation |
fact n | n == 0 = 1
| n == 1 = 1 |
2 |
Here, we start by inputting the value of ‘n’ into the factorial function. |
fact n | n == 0 = 1
| n == 1 = 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 |
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 |
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 |
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 |
1 |
Here, we input the value of ‘n’ into the factorial function again. |
fact n | n == 0 = 1
| n == 1 = 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 |
1 |
That was false, so we move on to the next predicate. |
fact n | n == 0 = 1
| n == 1 = 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 :: Float -> Float -> Float -> String |
add x y = let z = x + y in |
quadadd a b c d = |
quadadd a b c d = |
not :: Bool -> Bool |
nonzero :: Int -> Bool nonzero 0 = False nonzero _ = True |
(&&) :: Bool -> Bool -> Bool |
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 |
fetch :: Int -> [a] -> a |
add :: Int -> Int -> Int
|
(\x -> \y -> x + y) 5 6 or (\x y -> x + y) 5 6 |
add5 :: Int -> Int |
(+5) |
> zip ['a', 'b',
'c'] [1, 2, 3, 4] |
STICKY FINGAAS!!!
pairs :: [a] -> [ (a,a) ] |
sorted :: Ord a => [a] -> Bool |
fac 0 = 1 |
length :: [a] -> Int |
drop 0 xs = xs |
evens :: [a] -> [a]
|
Tail recursion |
No tail recursion |
fac' :: Int -> Int -> Int |
fac :: Int -> Int |
func1 :: (a -> b) -> a func2 :: a -> (b -> a) |
map (\x -> x + 5) [1,2,3]
map (+5) [1,2,3] |
filter (\x -> x == 5) [1,2,3,4,5]
filter (==5) [1,2,3,4,5] |
foldr (\x acc -> x + acc) 0 [1,2,3] foldr (+) 0 [1,2,3] |
sqrt 3^2 + 4^2 |
sqrt $ 3^2 + 4^2 |
odd x = not (even x) |
odd = not . even |
type Pos = (Int, Int) |
type Pair a b = (a,b) |
type Pair a b = (a, b) |
type Pos = (Int,Int) |
data Pair = PairInt Int Int | PairString String String |
-- RIGHT
PairInt 5 6
-- W R O N G
PairInt "killer queen" "bites the dust" |
data Maybe a = Nothing | Just a |
data BinaryTree a = Leaf a | Node a (BinaryTree a) (BinaryTree a) |
getLeftBranch :: BinaryTree a -> BinaryTree a |
newtype Pair = Pair (Int, Int) |
class Tree a where |
instance Tree BinaryTree where |
data RBTree a = |
blackH (Leaf _ ) = 0
where maxlr = max (blackH l) (blackH r) |
data Expr = Val Int | Add Expr Expr | Sub Expr Expr |
-- Data type for propositional expression |
class Functor f where |
fmap id = id |
fmap (g.h) = fmap g . fmap h |
instance Functor BinaryTree where |
fmap (\x -> x + 10) (Node 5 (Leaf 3) (Leaf 6)) |
data Direction = L | R |
type Trail = [Direction] |
data BinaryTree a = Leaf a | Node a (BinaryTree a) (BinaryTree a) deriving (Show) |
ZIPPER MAN!
graph :: Int -> [ Int ] |
type Table a = Array Vertex a |
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 |
data GGraph a = GGNode a [GGraph a]
|
empty :: Graph a b |
type Adj b = [ (b,Node) ] |
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
| isEmpty g = empty |
data Nat = Zero | Succ Nat |
add :: Nat -> Nat -> Nat |
Base Case |
Inductive Case |
add Zero (add y z) -- START |
add (Succ x) (add y z) -- START |
take 1 [1, 2, 3, 4...] |
replicate 10 (6π^2) |
take 1 [1, 2, 3, 4...] |
Solution A (the good one) |
Solution B (the crap one) |
ones = 1 : ones |
replicate 0 _ = [] |
Step |
Code |
1 |
square $! (1 + 2) |
2 |
square $! (3) |
3 |
square 3 |
4 |
9 |
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
λx→x
λx→λy→y
λx→λx→x
λx→λy→λz→y |
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 |
|
Expression |
Environment |
Before beta reduction |
(λx -> e1) e2 |
Nothing |
After beta reduction |
e1 |
x is mapped to e2 |
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. |
# |
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. |
# |
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. |
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 |
do p1 <- act1 . . .
pn <- actn |
firstThird :: IO (Char,Char) |
putStr :: String → IO () putStr xs |
putStrLn :: String → IO () putChar '\n' |
getLine :: IO String if x == '\n' then return [] else do xs <- getLine return (x:xs) |
type FilePath = String |
class Functor f => Applicative f where |
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 :: Int -> String |
do |
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 |
class Applicative m => Monad m where |
return x >>= f = f x |
mx >>= return = mx |
(mx >>= f) >>= g = mx >>= (\x -> (f x >>= g)) |
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 :: Expr -> Maybe Int
n <- eval x |
Just 10 >>= (\x -> Just (x + 10)) >>= (\x -> Just (x * 2)) |
xs >>= f = [ y | x <- xs, y <- f x ] |
type KnightPos = (Int,Int)
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 :: 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 |
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. |
filterM :: Monad m => (a -> m Bool) -> [a] -> m [a] |
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 |
class Double { |
double :: Num a => a -> a |
@FunctionalInterface
interface Function<T, R> { |
JButton testButton = new JButton("Test Button"); |
JButton testButton = new JButton("Test Button"); |
// single argument, no parentheses, omitting
"return" |
interface MapList<T,U> { |
public class MyMapList<T, U> implements MapList<T, U> { |
MyMapList<Integer, Integer> mapper = new MyMapList<>();
// newList1 = [2, 6, 12, 4, 10, 8] // newList2 = [2, 4, 7, 3, 6, 5] |
void fn() { |
private static class MyClosure { |
List<Integer> list = ...; // [-5, 4, -3, -2, 1] // newList3 = [5, 4, 3, 2, 1] |
List<Integer> list = ...; // [-5, 4, -3, -2, 1] // newList3 = [5, 4, 3, 2, 1] |
private static <T> void listAll(Function<Person, T> f,
List<Person> ps) { |
List<Person> people = List.of( ... ); // a list of some people |
class FactNonExample {
f.apply(i-1); |
public class FactExample {
new Recursive<>(); |
Iterator it = shapes.getIterator() |
shapes.forEach(s -> s.setColor(Color.RED)); |
String[] array = ... |
Stream<Integer> stream = Stream.of(1, 2, 3, 4); |
interface Stream<T> { <R> Stream<R> map(Function<T, R> mapper); … } |
Stream.of(1, 2, 3, 4) |
interface Stream<T> { |
Stream.of(1, 2, 3, 4) |
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> |
Stream<Integer> str = Stream.of(10, 2, 33, 45); |
public class Perfect { |
public static void main(String[] args) { |
8128 is a perfect number. |
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 |
var sumOfSquares = function(list) { |
var sumOfSquares = pipe(map(square),
reduce(add, 0)); |
var data = { |
var getIncompleteTaskSummariesForMember_imperative
= function(memberName) { |
Get all tasks from data |
|
Imperative |
Functional |
.then(function(data) { |
.then(get('tasks')) |
var get = curry(function(prop, obj) { |
var get = function(prop) { |
Filtering tasks by member name - first version |
|
Imperative |
Functional |
.then(function(tasks) {
{ |
.then(filter(function(task) {
task.member ==
memberName; |
var propEq = function(prop, val) { |
var propEq = function(prop, val) { |
var propEq = use(pipe).over(get, eq); |
Filtering tasks by member name - improved version |
|
Imperative |
Functional |
.then(function(tasks) {
{ |
.then(filter( propEq('member', memberName) )) |
Rejecting all tasks that are completed |
|
Imperative |
Functional |
.then(function(tasks) { |
.then(reject( |
Only keep some properties of every task |
|
Imperative |
Functional |
.then(function(tasks) { |
.then(map(pick( ['id', 'dueDate', 'title', 'priority'] ))) |
Sorting tasks by due date |
|
Imperative |
Functional |
.then(function(tasks) { |
.then(sortBy(get('dueDate'))); |
var propEq = use(pipe).over(get, eq); // TODO: move to library? |
isThisOne x | x == 1 = True |
type String = [Char] |
data Pair = PairInt Int Int | PairString String String |
newtype Pair = Pair (Int, Int) |
class Functor f where |
instance Functor Tree where |
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 |
“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. |
(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).