Haskell Lists

Haskell, in common with many other functional languages, provide list types as a fundamental data structuring mechanism.

Definition

In Haskell, a list type for any given base type may be easily constructed by naming the base type.

<list-type> ::="[" <type> "]"

• [Int] : lists of Ints.
• [Polygon] : lists of Polygons.
• [Char] : Haskell's String data type is a lists of Chars.
• [(Int, Float)] : lists of Int \(\times\) Float tuples.

The Haskell list data type is said to be polymorphic.

Construction

List values can be easily constructed by explicit enumeration of values. For example, a list of 4 [Char] \(\times\) Int 2-tuples:

[("black", 0), ("brown" 1), ("red", 2), ("orange", 3)]

Construction may also use the : operator to "cons" an element to the front of a given list, or the ++ operator to append to lists together.

("black", 0):[("brown", 1), ("red", 2), ("orange", 3)]
("black", 0):("brown", 1):[("red", 2), ("orange", 3)]
("black", 0):("brown", 1):("red", 2):[("orange", 3)]
("black", 0):("brown", 1):("red", 2):("orange", 3):[]
[("black", 0), ("brown", 1)] ++ [("red", 2), ("orange", 3)]

These examples all construct the same list value.

Access

Haskell list elements can be accessed by pattern-matching or by explicit recognition and access functions: null, head, tail.

• Pattern matching

totalof3[x, y, z]  = x + y + z

total [] = 0
total (a:as) = a + total as

• Access functions

total xs 
  | null xs = 0
  | otherwise = head xs + total(tail xs)

• null is a boolean function returning true if its argument is an empty list, false otherwise.
• head returns the first element of a nonempty list
• tail returns the sublist remaining after removing the first element of a list.

Type Variables for Polymorphic List Processing Functions

Consider the function to return the second element of a list.

second (a0: a1: moreas) = a1

Note that the logic of this function does not depend on the type of the list. So if we ask Haskell it's type, we see that Haskell displays a type variable t as the base type of the list.

*Main> :type second
second :: [t] -> t

The type variable allows us to use this function for any type of list.

• For a list of integers [Int], t = Int.
• For a list of pairs [(Char, Int)], t = (Char, Int)].

Functionals for List Processing

Functionals take a function as an argument and apply that function in interesting ways. For example, we can consider applying a function to elements of a list.

The map functional

The functional map applies a function to all elements of a list, returning a list of the results. In Haskell, map is a strongly-typed functional.

map :: (a ->b) -> [a] -> [b]

The function being mapped can be from any type a to any other type b.

Consider some examples applied to lists of strings, that is, [String] = [[Char]].

Prelude> map head ["The", "quick", "brown", "fox"]
"Tqbf"
Prelude> map tail ["The", "quick", "brown", "fox"]
["he","uick","rown","ox"]
Prelude> map length ["The", "quick", "brown", "fox"]
[3,5,5,3]
Prelude> map null ["The", "quick", "brown", "fox"]
[False,False,False,False]

But note that the functions head, tail, length, null are themselves polymorphic, working on lists of any type.

Prelude> :type head
head :: [a] -> a
Prelude> :type tail
tail :: [a] -> [a]
Prelude> :type length
length :: [a] -> Int
Prelude> :type null
null :: [a] -> Bool

So let's map these functions down lists of integers.

Prelude> map head [[1,2,3], [4,5], [6], [7,8]]
[1,4,6,7]
Prelude> map tail [[1,2,3], [4,5], [6], [7,8]]
[[2,3],[5],[],[8]]
Prelude> map length [[1,2,3], [4,5], [6], [7,8]]
[3,2,1,2]
Prelude> map null [[1,2,3], [4,5], [6], [7,8]]
[False,False,False,False]

Using map with Operator Sections

Haskell's operator section syntax converts binary operators into unary functions, by enclosing the operator and a single argument in parentheses.

Prelude> map (1+) [1,2,3,4,5]
[2,3,4,5,6]

Prelude> map (*2) [1,2,3,4,5]
[2,4,6,8,10]

Prelude> map(:[]) [1,2,3,4,5]
[[1],[2],[3],[4],[5]]

Prelude> map(:[0]) [1,2,3,4,5]
[[1,0],[2,0],[3,0],[4,0],[5,0]]

Prelude> map ('!':) ["The", "quick", "brown", "fox"]
["!The","!quick","!brown","!fox"]

Prelude> map (++"_word") ["The", "quick", "brown", "fox"]
["The_word","quick_word","brown_word","fox_word"]

Prelude> map (3>)[1,2,3,4,5]
[True,True,False,False,False]

Predicate Functionals

Predicate functionals take a boolean function and apply that in interesting ways.

Prelude> :type filter
filter :: (a -> Bool) -> [a] -> [a]
Prelude> :type span
span :: (a -> Bool) -> [a] -> ([a], [a])
Prelude> :type break
break :: (a -> Bool) -> [a] -> ([a], [a])

Let us apply these to some of the simple functions from the Data.Char library.

Prelude> import Data.Char
Prelude Data.Char> filter isLetter "ab12 cd245"
"abcd"
Prelude Data.Char> span isLetter "ab12 cd245"
("ab","12 cd245")
Prelude Data.Char> break isLetter "ab12 cd245"
("","ab12 cd245")
Prelude Data.Char> filter isDigit "ab12 cd245"
"12245"
Prelude Data.Char> span isDigit "ab12 cd245"
("","ab12 cd245")
Prelude Data.Char> break isDigit "ab12 cd245"
("ab","12 cd245")

Functionals with Lambda Expressions

Sometimes the function you need to map or filter is not immediately available. But simple functions can often be defined inline using Haskell lambda expressions.

Prelude Data.Char> map (\x->length x > 2) ["The", "quick", "brown", "fox"]
[True,True,True,True]
Prelude Data.Char> map (\x->length x > 4) ["The", "quick", "brown", "fox"]
[False,True,True,False]
Prelude Data.Char> filter (\x->length x > 4) ["The", "quick", "brown", "fox"]
["quick","brown"]
Prelude Data.Char> break (\x->length x > 4) ["The", "quick", "brown", "fox"]
(["The"],["quick","brown","fox"])

We can even map down a list of functions! Here we take a list of functions and apply each of them to the numeric value 3:

Prelude Data.Char> map (\f->f 3)[(+1), (*2), (+7), \x -> x * x]
[4,6,10,9]

Because functions can be stored in lists and used in all the ways any other values can be used in Haskell, functions are said to be first-class citizens.

Zipping

Haskell not only allows unary functions applied to lists, but binary functions applied to pairs of lists.

Prelude> :type zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
Prelude> zipWith (+) [1,2,3] [9,8,7]
[10,10,10]

Or even ternary functions:

Prelude> :type zipWith3
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]