Lists

> [1, 2, 3]

Concatenating lists.

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

"For every type a. (++) has type [a] -> [a] -> [a]." If there were an AllTypes type class that contained all types, this type might be written AllTypes a => [a] -> [a] -> [a].

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

> [1, True]

> ['a', 'b', 'c']              -- strings are lists
> ['a', 'b', 'c'] == "abc"

> type String = [Char]
> :t "abc"
> :t "abc" :: String

Constructing lists.

> []                           -- empty list
> 1 : []                       -- "cons"
> 1 : (2 : [])
> 1 : (2 : (3 : []))
> 1 : 2 : 3 : []
> 1 : 2 : 3 : [] == [1,2,3]    -- syntactic sugar

> 1 : True : []                -- heterogeneous elements

> [1] : []                     -- list of lists

> [1] : [2]                    -- error

"For every type a. (:) has type a -> [a] -> [a]."

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

> 1 : [2, 3]
> [1] : [2, 3]

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       -- if-then-else expression
         else filter p xs

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

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

Notice the following cosmetic difference, that the order of arguments to f differs between foldr and foldl:

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.

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)

> 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       -- "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#, polymorphic (i.e. generic) functions like id would be rewritten with explicit type arguments:

> id {- <a> -} x = x

And calls to polymorphic functions would require explicit type arguments:

> id {- <Bool> -} True
True

> id {- <(Bool, [Char])> -} (True, "Hello")
(True,"Hello")

In the code snippets above, the type arguments are "hidden" inside comments because Haskell syntax does not allow them to be written (not by default, at least). Instead, Haskell automatically infers polymorphic function types when possible, and automatically infers the appropriate type instantations at each call to such functions. For practice, you may want to think about explicitly instantiatiating type arguments, as above.

Choice of bound variables is irrelevant (just like for expressions).

--               a -> a  ===             b -> b
--     forall a. a -> a  ===   forall b. b -> b

> :t id
> :t id :: a -> a
> :t 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

> head (x:_) = x