We have two ways to express calculations:
4 + 2, a && bdiv 8 3, take 2 [1,2,3,4,5], someFunc a b cThey 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 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 FalseChar: one characterInt: fixed-precision signed integer (usually 64-bit)Float/Double: floating-point valuesAnd compound types:
[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 -> CA 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:
map might exist: (a -> b) -> [a] -> [b][a] -> (a -> b) -> [b]Double -> Double -> Double[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.
implementsthat interface.
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:
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/2 could be read a value [function] that takes an argument called
.x and returns x/2
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