Lists and List Processing

Lists are the fundamental data structure in functional programming. In Haskell, almost all data processing involves manipulating lists using recursion, pattern matching, and higher-order functions like map, filter, and fold.

---

Lists in Haskell

A list in Haskell is a sequence of elements of the same type, enclosed in square brackets:

numbers = [1, 2, 3, 4, 5]          -- List of integers
names = ["Alice", "Bob", "Carol"]   -- List of strings
empty = []                          -- Empty list
single = [42]                       -- List with one element

List Types

Every list has a type written as [a], where a is the type of the elements:

[1, 2, 3]           :: [Int]
["hello", "world"]  :: [String]
[True, False, True]  :: [Bool]

All elements must be the same type — you cannot mix integers and strings.

Strings are Lists of Characters

In Haskell, a String is simply a list of Char:

"hello" == ['h', 'e', 'l', 'l', 'o']    -- True

---

Head, Tail, and Cons

Head and Tail

• head returns the first element of a list.
• tail returns everything except the first element.

head [1, 2, 3, 4, 5]    -- 1
tail [1, 2, 3, 4, 5]    -- [2, 3, 4, 5]

head "hello"             -- 'h'
tail "hello"             -- "ello"

Warning: Calling head or tail on an empty list causes a runtime error.

Cons Operator (:)

The cons operator (:) prepends an element to the front of a list:

1 : [2, 3, 4]        -- [1, 2, 3, 4]
'h' : "ello"         -- "hello"
0 : []               -- [0]

The list [1, 2, 3] is syntactic sugar for 1 : 2 : 3 : [].

Other Useful Functions

last [1, 2, 3, 4, 5]     -- 5 (last element)
init [1, 2, 3, 4, 5]     -- [1, 2, 3, 4] (all except last)
length [1, 2, 3, 4, 5]   -- 5
null []                   -- True (is the list empty?)
null [1, 2]               -- False
reverse [1, 2, 3]         -- [3, 2, 1]
take 3 [1, 2, 3, 4, 5]   -- [1, 2, 3]
drop 3 [1, 2, 3, 4, 5]   -- [4, 5]
elem 3 [1, 2, 3, 4, 5]   -- True (is 3 in the list?)
sum [1, 2, 3, 4, 5]       -- 15
product [1, 2, 3, 4, 5]   -- 120

---

List Concatenation

The ++ operator joins two lists:

[1, 2, 3] ++ [4, 5]         -- [1, 2, 3, 4, 5]
"Hello" ++ " " ++ "World"   -- "Hello World"

Note: (:) prepends a single element (O(1)), while (++) concatenates two lists (O(n) where n is the length of the first list).

---

List Ranges

Haskell supports list ranges for generating sequences:

[1..10]          -- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[2, 4..20]       -- [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
['a'..'z']       -- "abcdefghijklmnopqrstuvwxyz"
[10, 9..1]       -- [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

---

List Comprehensions

A list comprehension is a concise way to create lists based on existing lists, with optional filtering.

Syntax

[expression | generator, guard]

Examples