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"

Constructing lists.

> []                           -- empty list
> 1 : []                       -- "cons"
> 1 : 2 : []
> 1 : 2 : [] == [1,2]          -- 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

-- length : [Int] -> Int
-- length : [Char] -> Int
-- length : [[Char]] -> Int

length : [a] -> Int
length []     = 0
length (_:xs) = 1 + length xs

-- doubleList : [Int] -> [Int]
-- doubleList : [Integer] -> [Integer]
-- doubleList : [Double] -> [Double]

doubleList : Num n => [n] -> [n]
doubleList []     = []
doubleList (x:xs) = x*2 : doubleList xs

squareList : Num n => [n] -> [n]
squareList []     = []
squareList (x:xs) = x^2 : squareList xs

Yuck, some of these definitions have a lot of repeated code.

Map

-- map : Num a => (a -> a) -> [a] -> [a]
-- map : (a -> a) -> [a] -> [a]

map : (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

doubleList xs = map ((*) 2) xs

squareList xs = map square xs
  where square x = x * x

Filter

filter : (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

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)

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

This type can be instantiated by substituting any type for the type variable a. When we call the function, Haskell implicitly infers the appropriate type instantiation. For practice, you can think of explicitly instantiatiating the type parameter (although Haskell syntax does not allow it).

> id True      -- id<Bool> True
> id "hello"   -- id<String> "hello"

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

Recent feature allows forall to be explicitly written:

> :set -XExplicitForAll

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

For the functions we will write and call in this class, we will never need to write foralls explicitly. Just remember that the foralls are there, but Haskell inserts and instantiates that implicitly. There are certain more complicated situations in which explicit foralls are required, but we won't cover them in this class.