We have two ways to express calculations:

- [infix] operators:
`4 + 2`

,`a && b`

- function calls:
`div 8 3`

,`take 2 [1,2,3,4,5]`

,`someFunc a b c`

They can be interchanged: `(+)`

and `(&&)`

are functions; ``div``

and ``take``

and ``someFunc``

are operators. i.e. these are equivalent:

Operator | Function |
---|---|

`4 + 2` | `(+) 4 2` |

`a && b` | `(&&) a b` |

`8 `div` 3` | `div 8 3` |

`2 `take` [1,2,3,4,5]` | `take 2 [1,2,3,4,5]` |

`(a `someFunc` b) c` | `someFunc a b c` |

Sometimes code can be more readable if you swap functions and operators: I often write

for symmetry with `a `div` 2`

.`a / 2`

Sometimes it's necessary to have a function, even though you have an operation defined as an operator…

There are many ways to dissect lists in Haskell.

`head`

/`tail`

: the first/rest of the list (but consider a cons pattern, which might be more readable).

Expression | Result |
---|---|

`head [8,9,10,11]` | `8` |

`tail [8,9,10,11]` | `[9,10,11]` |

`head []` | error |

`tail []` | error |

`take`

/`drop`

: get/throw away the first elements from a list.

Expression | Result |
---|---|

`take 3 [10,20,30,40,50]` | `[10,20,30]` |

`take 1 "Hello"` | `"H"` (not `'H'` ) |

`take 3 [1,2]` | `[1,2]` |

`drop 3 [10,20,30,40,50]` | `[40,50]` |

`drop 3 [1,2]` | `[]` |

`takeWhile`

/`dropWhile`

: take/drop while a condition is true.

`splitAt`

: chop a list in two at a specific position.

Expression | Result |
---|---|

`takeWhile even [2,4,6,7,10,12]` | `[2,4,6]` |

`dropWhile even [2,4,6,7,10,12]` | `[7,10,12]` |

`splitAt 2 [10,20,30,40,50]` | ```
([10,20],[30,40,50])
``` |

`splitAt 4 [10,20,30,40,50]` | ```
([10,20,30,40],[50])
``` |

Processing lists so far: list comprehensions and recursion on lists. There are more built-in tools that are worth mentioning…

`map`

: apply a function to each element in a list.

Expression | Result |
---|---|

`map succ [1,42,8]` | `[2,43,9]` |

`map sqrt [4,25,2]` | `[2.0,5.0,1.414…]` |

`map hailstone (divisors 30)` | `[1,10,16,3,5,46]` |

`map (gcd 10) [3,4,5,6]` | `[1,2,5,2]` |

`filter`

: Take only elements of a list that meet some condition.

Expression | Result |
---|---|

`filter even [1..8]` | `[2,4,6,8]` |

`filter isPrime [2..10]` | `[2,3,5,7]` |

We could have defined `divisors`

with `filter`

as:

divisors n = filter (divides n) [2..(n `div` 2)] where divides a b = (a `mod` b) == 0

Both `map`

and `filter`

duplicate things we can do with list comprehensions (or recursion): use whichever is easier to read in the specific situation.

… but not `foldr`

: used to apply a function across a list.

[Compare the `reduce`

function/method in Python, Ruby, Scala, JavaScript, Apache Spark.]

An example: sum the values in a list. We could to it recursively:

mySum [] = 0 mySum (x:xs) = x + mySum xs

Important points: the operation is `(+)`

and the starting point (result for `[]`

) is `0`

. Then, an equivalent fold:

mySum' xs = foldl (+) 0 xs

mySum' xs = foldl (+) 0 xs

If we call this on `[1,2,3]`

, it expands to:

foldl (+) 0 [1,2,3] == (+) ((+) ((+) 0 1) 2) 3 == ((0 + 1) + 2) + 3

mySum' xs = foldl (+) 0 xs

The arguments to the fold:

- the operation: function that combines the accumulator and an element.
- the zero: correct result for an empty list, and where to start the accumulator.
- the list.

The `foldr`

function does the same thing, but associates the other way:

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

If there's a choice, `foldl`

*should* be faster, since it's working from the head of the list (but there's more to say about that, later).

`foldr`

and `foldl`

are surprisingly flexible. For example:

myLength xs = foldl oneMore 0 xs where oneMore n _ = n+1

When it's called:

myLength "abc" == oneMore (oneMore (oneMore 0 'a') 'b') 'c' == oneMore (oneMore 1 'b') 'c' == oneMore 2 'c' == 3

Two more:

myConcat xs = foldl (++) [] xs myReverse xs = foldl prefix [] xs where prefix xs x = x:xs

myConcat [[1,2], [3,4], [5,6]] == ([1,2] ++ [3,4]) ++ [5,6] == [1,2,3,4,5,6] myReverse [1,2,3,4] == prefix (prefix (prefix (prefix [] 1) 2) 3) 4 == prefix (prefix (prefix [1] 2) 3) 4 == prefix (prefix [2,1] 3) 4 == prefix [3,2,1] 4 == [4,3,2,1]

It's (usually?) possible to swap `foldr`

and `foldl`

if you change the operation appropriately.

myReverse' xs = foldr postfix [] xs where postfix x xs = xs ++ [x]

myReverse' [1,2,3,4] == postfix 1 (postfix 2 (postfix 3 (postfix 4 []))) == postfix 1 (postfix 2 (postfix 3 [4])) == postfix 1 (postfix 2 [4,3]) == postfix 1 [4,3,2] == [4,3,2,1]

We have already seen some simple types:

`Bool`

: boolean True or False`Char`

: one character`Int`

: fixed-precision signed integer (usually 64-bit)`Float`

/`Double`

: floating-point values

And compound types:

- Lists which contain several values of a single type, written

.`[Type]`

`String`

: list of characters. Shortcut for

.`[Char]`

All type names start with a uppercase character. Functions and arguments start with lowercase.

Types can be explicitly declared with the `::`

syntax:

val :: Int val = 6 lst :: [Int] lst = [1,2,3] lstlst :: [[Int]] lstlst = [[1,2,3], [4,5]]

…or queried with the GHCi `:t`

command:

Prelude> :t 6 6 :: Num t => t Prelude> :t "Hello" "Hello" :: [Char]

More types…

`Integer`

: arbitrary-precision integer:

Prelude> let base=2 :: Int Prelude> let power=64 :: Int Prelude> base ^ power 0 Prelude> let base=2 :: Integer Prelude> let power=64 :: Integer Prelude> base ^ power 18446744073709551616

tuples: collection of values with a fixed length, but may have different types in each position. Different type signatures/lengths are considered different types.

Prelude> (1, "Hello") :: (Int, String) (1,"Hello") Prelude> (1,2,3) :: (Int,Int,Int) (1,2,3) Prelude> [(1,'a'), (2,'b')] :: [(Int,Char)] [(1,'a'),(2,'b')] Prelude> [(1,'a'), (2,2)] error… Prelude> [(1,2,3), (4,5)] error…

Functions also have a type. It can (and should) be explicitly declared.

half_of :: Float -> Float half_of x = x/2 myPower :: Int -> Int -> Int myPower _ 0 = 1 myPower x y = x * myPower x (y-1)

The type

indicates a function that takes two arguments of type `A -> B -> C`

`A`

and `B`

, and returns a `C`

.

Some functions can work on a variety of types.

*Main> :t zip zip :: [a] -> [b] -> [(a, b)] *Main> :t half_of half_of :: Float -> Float *Main> let another_half_of x = x/2 *Main> :t another_half_of another_half_of :: Fractional a => a -> a

Here, `a`

and `b`

are type variables that can represent any type. The function `another_half_of`

has a more general type because it wasn't explicitly declared.

Functions can also be passed as arguments or returned (as we have seen). Their types are given in the type signature.

*Main> :t map map :: (a -> b) -> [a] -> [b] *Main> :t filter filter :: (a -> Bool) -> [a] -> [a]

flip_args :: (a -> b -> c) -> b -> a -> c flip_args f x y = f y x

Types are important in Haskell. Important enough that you can search by type signature in Hoogle.

Some searches to try:

- I think
`map`

might exist:`(a -> b) -> [a] -> [b]`

- … with wrong argument order:
`[a] -> (a -> b) -> [b]`

- What kind of arithmetic is there?
`Double -> Double -> Double`

- What can I do to a list?
`[Int] -> [Int]`

Everything has a type, even if you don't specify it. Haskell will do type inference to guess the types of values. It's surprisingly good at it.

myAnd False _ = False myAnd True a = a

*Main> :t myAnd myAnd :: Bool -> Bool -> Bool

The inferred types can be useful, but it's often better to give the type explicitly. There can be performance implications: these functions will perform differently:

myPower :: Int -> Int -> Int

myPower :: Integer -> Integer -> Integer

… because `Int`

operations are processor instructions; `Integer`

operations are calls to an arbitrary-precision integer library.

If you give an explicit type, you can get better error messages when what you write has different types than you intended.

Rule starting with Exercise 3: must give explicit types of functions you declare.

A type class is a set of operations.

- Like a Java or C# interface: a class that implements the right operations can declare that it
implements

that interface. - Like Go interfaces, but explicitly declared on the type.
- Like traits in Rust.
- A little like a C++ abstract class: defines a set of operations that must be implemented on a specific class.

e.g. if `(==)`

and `(/=)`

can be applied to values of a type, it is in the `Eq`

type class.

Type classes are indicated in types with

. e.g.`=>`

Prelude> let theSame x y = x == y Prelude> :t theSame theSame :: Eq a => a -> a -> Bool

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

Other important type classes:

e.g.

*Main> :t 6 6 :: Num t => t *Main> :t 6/4 6/4 :: Fractional a => a *Main> :t qsort qsort :: Ord t => [t] -> [t] *Main> :t (<) (<) :: Ord a => a -> a -> Bool

Type inference will often give a type class, not a specific type. Types with classes are more flexible: can be used on any value/type in the class.

Type classes (and type variables) provide easy and flexible polymorphism in Haskell: functions can operate on any type(s) where the operations used in their definition make sense.

Consider the type declaration for a two-argument function:

join :: String -> [String] -> String

This is actually parsed as:

join :: String -> ([String] -> String)

i.e. `join`

is actually a function that takes a `String`

and returns a function `[String] -> String`

.

So, we can write:

join :: String -> [String] -> String -- ... commajoin :: [String] -> String commajoin = join ", "

Then:

*Main> commajoin ["one", "two", "three"] "one, two, three"

When a function has values applied to some (but not all) of its arguments, it is referred to as a partial function.

A partial function can be treated like any other function. Every function application we have done could have been parenthesized left associating:

map sqrt someList == (map sqrt) someList foldl (+) 0 someList == ((foldl (+)) 0) someList

That means that all of these are the same calculation:

Prelude> div 10 2 5 Prelude> (div 10) 2 5 Prelude> let d10=(div 10) in d10 2 5

We can define functions using partial function application as well. These are equivalent:

myConcat :: [[a]] -> [a] myConcat xs = foldl (++) [] xs myConcat' :: [[a]] -> [a] myConcat' = foldl (++) []

When you need to pass a function as an argument, a partially-applied function can be used. This example did this with

:`divides n`

divisors n = filter (divides n) [2..(n `div` 2)] where divides a b = (a `mod` b) == 0

Operators can also be partially-applied, but more flexibly, since you can easily get to either argument.

Prelude> map (12/) [6,2,12] [2.0,6.0,1.0] Prelude> map (/12) [6,2,12] [0.5,0.16666666666666666,1.0]

Functions (like all examples so far) that take multiple arguments by taking single arguments multiple times are called curried functions. (After Haskell Curry.)

The other possibility (in Haskell) is to wrap multiple arguments in a tuple: an uncurried function. e.g.

myDiv :: (Int, Int) -> Int myDiv (n,d) = div n d

There are functions to curry and uncurry two-argument functions:

*Main> (uncurry div) (10,2) 5 *Main> (curry myDiv) 10 2 5

These are often useful during list manipulations, particularly with `zip`

, which puts two lists together into tuples:

*Main> :t zip zip :: [a] -> [b] -> [(a, b)] *Main> zip [1,2,3] ['a','b','c'] [(1,'a'),(2,'b'),(3,'c')]

Using `uncurry`

, we can operate on these pairs:

addPairwise :: Num a => [a] -> [a] -> [a] addPairwise xs ys = map (uncurry (+)) (zip xs ys)

addPairwise [1,2,3] [4,5,6] == map (uncurry (+)) (zip [1,2,3] [4,5,6]) == map (uncurry (+)) [(1,4), (2,5), (3,6)] == [(uncurry (+)) (1,4), (uncurry (+)) (2,5), (uncurry (+)) (3,6)] == [(+) 1 4, (+) 2 5, (+) 3 6] == [5, 7, 9]

Once you start to think of functions as values, there are many useful ways to manipulate them. We have seen:

- partial function application,
- currying/uncurrying.

But also…

Function composition with `(.)`

(like \(f\circ g\)

in a math class). Lets us combine two functions, so:

(f.g) x == f (g x)

Some functions we could have defined this way:

hailLen :: Int -> Int hailLen = length . hailSeq reverseJoin :: String -> [String] -> String reverseJoin s = (join s) . reverse weekday :: Day -> Int weekday = snd . mondayStartWeek

Reverse function arguments of a (two-argument curried) function with `flip`

. Useful to partially-apply on the second argument.

joinPrimes :: String -> String joinPrimes = (flip join) ["2", "3", "5", "7", "11"] myReverse'' :: [a] -> [a] myReverse'' xs = foldl (flip (:)) [] xs

*Main> joinPrimes "," "2,3,5,7,11" *Main> joinPrimes "+" "2+3+5+7+11" *Main> myReverse'' "testing" "gnitset"

Haskell has first-class functions: functions are values just like integers, lists, etc. They can be passed as arguments, assigned names, etc.

When we define things in our code:

val :: Int val = 6

half_of :: Float -> Float half_of x = x/2

… `val`

is value of type `Int`

, and `half_of`

is a value of type `Float -> Float`

.

Functions can also be created with lambda expressions. The Greek letter λ is spelled

in Haskell.`\`

This defines an equivalent function:

half_of' :: Float -> Float half_of' = \x -> x/2

The lambda expression `\x -> x+x`

could be read a value [function] that takes an argument called

.`x`

and returns `x+x`

Like partial application, lambdas can be useful to define functions on their own, but are more likely to be used to create readable larger expressions. For example,

addToEach :: Num a => a -> [a] -> [a] addToEach n lst = map (\x -> x+n) lst

… is arguably more readable than…

addToEach' :: Num a => a -> [a] -> [a] addToEach' n lst = map addN lst where addN x = x+n

Lambda could be more clear than partial application. e.g. which is more readable?

commajoin0, commajoin1, commajoin2 :: [String] -> String commajoin0 = \xs -> join ", " xs commajoin1 = join ", " commajoin2 xs = join ", " xs