List literals.
> [1, 2, 3]
Concatenating lists.
> [1, 2, 3] ++ [4, 5]
> [1, 2, 3] ++ []
> :t (++)
(++) :: [a] -> [a] -> [a]
Read this type signature as
a
. (++)
has type
[a] -> [a] -> [a]
” or(++)
has type [a] -> [a] -> [a]
,
for all types a
”I often like to be explicit about the implicit “for all” by burying it in comments:
> :t (++) :: {- forall a. -} [a] -> [a] -> [a]
Even better, recent versions of Haskell, by default, allow us to be explicit:
> :t (++) :: forall a. [a] -> [a] -> [a]
(++) :: forall a. [a] -> [a] -> [a] :: forall a. [a] -> [a] -> [a]
Also handy to know is that GHC offers a verbosity
option for explicitly printing forall
s, even if the
relevant type declarations are not explicit:
> :set -fprint-explicit-foralls
> :t (++)
(++) :: forall a. [a] -> [a] -> [a]
Type errors.
> [1, True]
> [1, [2]]
Strings are lists of characters.
> ['a', 'b', 'c']
> ['a', 'b', 'c'] == "abc"
> :t "abc"
> :t "abc" :: [Char]
> type String = [Char] -- Defined in ‘GHC.Base’
Constructing lists.
> [] -- empty list
> 1 : [] -- "cons"
> 1 : (2 : [])
> 1 : (2 : (3 : []))
> 1 : 2 : 3 : []
> 1 : 2 : 3 : [] == [1,2,3] -- syntactic sugar
Type errors.
> 1 : True : []
> [1] : [2]
> [1] : [2, 3]
List of lists.
> [1] : []
“(:)
has type a -> [a] -> [a]
for all
types a
.”
> :t (:)
(:) :: a -> [a] -> [a]
Destructing lists.
import Prelude hiding (head, tail, repeat, take, length)
head :: {- forall a. -} [a] -> a
head (x:xs) = x
tail :: {- forall a. -} [a] -> [a]
tail (x:xs) = xs
> head []
> tail []
We’ll see better ways to deal with errors later.
List ranges.
> [1..10]
> [1..1]
> [10..1]
> ['a'..'z']
> [1.1 .. 3.0]
Zipping two lists.
> zip [1..26] ['A'..'Z']
A list is either (i) an empty list or (ii) a non-empty list built by the cons constructor, comprising one “head” element and one “tail” list.
To define a function that works for any list, define equations for each of these (two) cases.
-- length :: [Int] -> Int
-- length :: [Char] -> Int
-- length :: [[Char]] -> Int
length :: {- forall a. -} [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs
More examples:
-- doubleList :: [Int] -> [Int]
-- doubleList :: [Integer] -> [Integer]
-- doubleList : [Double] -> [Double]
doubleList :: {- forall n. -} Num n => [n] -> [n]
doubleList [] = []
doubleList (x:xs) = x*2 : doubleList xs
squareList :: {- forall n. -} Num n => [n] -> [n]
squareList [] = []
squareList (x:xs) = x^2 : squareList xs
allCaps :: [Char] -> [Char]
allCaps [] = []
allCaps (c:cs) = Data.Char.toUpper c : allCaps cs
Yuck, some of these definitions have a lot of repeated code. Don’t Repeat Yourself!
map
is a function that takes a function as an argument.
It’s a “higher-order” function.
-- map :: {- forall a. -} Num a => (a -> a) -> [a] -> [a]
-- map :: {- forall a. -} (a -> a) -> [a] -> [a]
map :: {- forall a b. -} (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
For example:
doubleList xs = map double xs
where double x = 2 * x
Or, with partial application:
doubleList xs = map ((*) 2) xs
Another example:
squareList xs = map square xs
where square x = x * x
filter :: {- forall a. -} (a -> Bool) -> [a] -> [a]
filter p [] = []
filter p (x:xs) = if p x then
x : filter p xs
else
filter p xs
With guards:
filter p [] = []
filter p (x:xs) | p x = x : filter p xs
| otherwise = filter p xs
> otherwise
True
The higher-order functions map
and filter
eliminate boilerplate code when writing recursive list functions. Now
we’ll see an even more general function called fold
(a.k.a.
reduce, as in MapReduce).
This function generalizes the structural recursion pattern.
length [] = 0
length (x:xs) = 1 + length xs
sum [] = 0
sum (x:xs) = x + sum xs
prod [] = 1
prod (x:xs) = x * prod xs
concat [] = []
concat (x:xs) = x ++ concat xs
Don’t Repeat Yourself!
foldr :: {- forall a b. -} (a -> b -> b) -> b -> [a] -> b
foldr f acc [] = acc
foldr f acc (x:xs) = f x (foldr f acc xs)
-- let result = foldr f acc xs in
-- f x result
Notice the use of the variable acc
. Writing helper
functions with “accumulators” is a common trick in functional
programming. Each recursive call updates the accumulator, and the base
case returns the initial accumulator.
For a call of the form (foldr f init [x1, x2, x3])
, the
function f
is applied to the rightmost element in the list
first.
-- x1 : (x2 : (x3 : []))
-- x1 `f` (x2 `f` (x3 `f` init)) -- rightmost first
Note:
e_1
`f` e_2
=
f e_1 e_2
Now, via foldr
:
sum xs = foldr (+) 0 xs
prod xs = foldr (*) 1 xs
concat xs = foldr (++) [] xs
And another:
len xs = foldright addOne 0 xs
where addOne _ acc = 1 + acc
And another:
max [] = error "empty list!"
max (x:xs) = foldright foo x xs
where foo a acc | a > acc = a
| otherwise = acc
There’s also a version of fold
that applies the function
from left-to-right:
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs
-- let acc' = f acc x in
-- foldl f acc' xs
There is a cosmetic difference: the order of arguments to
f
differs between foldr
and
foldl
:
for foldr
, the function f
takes a list
element (of type a
) first and the accumulating value (of
type b
) second (i.e. f :: a -> b -> b
);
whereas
for foldl
this order is swapped
(i.e. f :: b -> a -> b
).
Unlike foldr
, for a call of the form
(foldl f init [x1, x2, x3])
, the function f
is
applied to the leftmost element first:
-- x1 : (x2 : (x3 : []))
-- ((init `f` x1) `f` x2) `f` x3 -- leftmost first
Like with foldr
, each recursive call updates the
accumulator. This time, the base case returns the accumulator as the
final result.
Functions defined with multiple equations, as above, can be desugared into a more primitive form.
In the library, the types for some of the functions above are more general:
> :t length
> :t foldr
> :t foldl
For now, when you see Foldable
, think of the list
type:
> :t +d length
> :t +d foldr
> :t +d foldl
The Data.List
library has tons of useful list-manipulating functions. Start taking a
look through; many will become close friends.
It may be useful to look through the documentation every now and again and, for practice, try to implement some of the functions based on their types and descriptions.
> [1..]
> take 10 [1..]
> take 10 (repeat 1)
> zip [1..] ['A'..'Z']
Let’s implement the repeat
library function for
ourselves.
repeat n = n : repeat n
> let zeroes = repeat 0
> zeroes
> [Ctrl+C] -- infinite list "forced" to eval
> head zeroes -- laziness
> head (tail zeroes)
> head (tail (tail zeroes))
Let’s implement the take
library function for
ourselves.
take _ [] = []
take n _ | n <= 0 = []
take n (x:xs) = x : take (n-1) xs
> id x = x
> :t id
a -> a
> :t id :: {- forall a. -} a -> a
> :t id :: forall a. a -> a
This type can be instantiated by substituting any type for
the type variable a
.
> id True -- :: Bool
True
> id (True, "Hello") -- :: (Bool, [Char])
(True,"Hello")
In languages like Java or C#, calls to polymorphic
(i.e. generic) functions like id
might be
rewritten with explicit type arguments. In the code snippets below, the
type arguments are “hidden” inside comments because Haskell
automatically infers them:
> id {- Bool -} True
True
> id {- (Bool, [Char]) -} (True, "Hello")
(True,"Hello")
But Haskell does allow explicitly writing type arguments by prefacing
them with the @
character. For practice, you may want to
think about explicitly instantiatiating type arguments:
> id @Bool True
True
> id @(Bool, [Char]) (True, "Hello")
(True,"Hello")
> :t id @Bool
> :t id @(Bool, [Char])
Choice of bound variables is irrelevant (just like for expressions).
> :t id
> :t id :: {- forall a. -} a -> a
> :t id :: {- forall b. -} b -> b
The following definitions are equivalent:
id :: {- forall a. -} a -> a
id a = a
id :: {- forall b. -} b -> b
id b = b
Without annotations, Haskell might choose undesirable variables.
> let fst x y = x
> :t fst
fst :: p1 -> p2 -> p1
> let fst' = fst :: a -> b -> a
> :t fst'
fst' :: a -> b -> a
> snd x y = y
> :t snd
snd :: p1 -> p2 -> p2
> :t snd :: a -> b -> b
snd :: a -> b -> b :: a -> b -> b
> :t snd :: x -> y -> y
snd :: x -> y -> y :: x -> y -> y
Haskell automatically infers polymorphic function types, and type
instantiations at corresponding function calls, when possible — which is
always for our purposes. But as we’ve seen, we can write explicit
forall
s in types and explicit type arguments if we choose
to. These are both allowed in recent versions of Haskell, namely GHC2021
by default but historically required language
extensions, namely ExplicitForAll
and TypeApplications
,
to enable this syntax.