# Lists, Ranges and Comprehensions — Haskell

Source: https://www.geekswithgeeks.com/en/haskell/c-lists

> Build and transform lists with ranges, comprehensions and list functions.

## The workhorse data structure

A **list** `[a]` holds elements of one type and is a singly linked list built from **`[]`** (empty) and **`:`** (cons): `[1, 2, 3]` is `1 : 2 : 3 : []`. Prepending with `:` is O(1); appending with `++` and indexing with `!!` are O(n). **Ranges** generate lists: `[1 .. 10]`, `[2, 4 .. 20]`, `['a' .. 'z']`, and thanks to laziness, infinite ranges such as `[1 ..]`. **List comprehensions** combine generators, filters and local bindings: `[x * x | x <- [1 .. 10], even x]`. The Prelude and `Data.List` provide many functions: `map`, `filter`, `foldr`, `sum`, `product`, `length`, `reverse`, `take`, `drop`, `takeWhile`, `zip`, `zipWith`, `concat`, `concatMap`, `elem`, `words`, `unwords`, `lines`, `replicate` and, from `Data.List`, `sort`, `sortOn`, `group`, `nub`, `partition` and `foldl'`. Strings are lists of `Char`, so these functions work on them too. Beware of **partial functions** like `head` and `tail`, which crash on empty lists; prefer pattern matching or safe alternatives such as `Data.List.uncons`.

## A list as cons cells

Each cell holds a value and a pointer to the rest; [] ends the list.

![A chain of small two-part boxes, each with a value on the left and an arrow on the right to the next box, ending in an empty box marker.](assets/figures/haskell/section-2-map.svg) — Figure 2.1 — 1 : 2 : 3 : [].

## Working with lists

Ranges, comprehensions and Data.List.

```haskell
import Data.List (sortOn, group, sort, partition)
import Data.Ord (Down (..))

evensSquared :: [Int]
evensSquared = [x * x | x <- [1 .. 10], even x]           -- [4,16,36,64,100]

pythagorean :: Int -> [(Int, Int, Int)]
pythagorean n = [(a, b, c) | c <- [1 .. n], b <- [1 .. c], a <- [1 .. b], a * a + b * b == c * c]

wordFrequencies :: String -> [(String, Int)]
wordFrequencies text =
  sortOn (Down . snd) [(head ws, length ws) | ws <- group (sort (words text))]

main :: IO ()
main = do
  print evensSquared
  print (pythagorean 15)                   -- [(3,4,5),(6,8,10),(5,12,13),(9,12,15)]
  print (zip [1 :: Int ..] "abc")          -- [(1,'a'),(2,'b'),(3,'c')]
  print (takeWhile (< 40) (map (^ 2) [1 :: Int ..]))   -- [1,4,9,16,25,36]
  print (partition even [1 .. 10 :: Int])  -- ([2,4,6,8,10],[1,3,5,7,9])
  print (wordFrequencies "to be or not to be")
  -- [("be",2),("to",2),("not",1),("or",1)]
```

## head is safe only when you know the list is non-empty

In `wordFrequencies`, `group` never produces empty groups, so `head ws` is safe. Elsewhere, match on `(x : _)` or use `Data.List.NonEmpty` so the type guarantees non-emptiness.

**Quiz:** What is the cost of prepending an element to a Haskell list with (:)?

- [ ] O(n)
- [ ] O(log n)
- [x] O(1)
- [ ] O(n squared)

*Answer:* O(1). Cons creates one new cell pointing to the existing list.