Lists

List literals.

> [1, 2, 3]

Concatenating lists.

> [1, 2, 3] ++ [4, 5]
> [1, 2, 3] ++ []

> :t (++)
(++) :: [a] -> [a] -> [a]

Read this type signature as

“for all types 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 foralls, 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']

Structural Recursion

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

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

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

Fold

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).

List Fold-Right

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

List Fold-Left

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.

Exercise

If you’re missing the chill of your frigid languages, implement map, filter, foldr using loops and mutable variables.

Syntax

Functions defined with multiple equations, as above, can be desugared into a more primitive form.

Foldable

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

Data.List

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.

Infinite Lists

> [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

Parametric Polymorphism (a.k.a. Generics)

> id x = x

> :t id
a -> a

> :t id :: {- forall a. -} a -> a

> :t id :: forall a. a -> a

Type Instantiation

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])

Type Variables

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

Language Extensions

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 foralls 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.