Week 10: Notes

arrays

As we discussed in the lecture, Haskell has immutable arrays that allow you to access elements in O(1) using the ! operator. You can build an array from a list or an association list. Our library quick reference documents the array API.

arrays and recursion

Array elements are evaluated lazily, and may even refer to other elements of the same array:

> a = listArray (1, 3) [10, 20, a ! 1 + a ! 2]
> a ! 1
10
> a ! 3
30

And so we can build an entire array using a recursive calculation. This function builds an array of the first N Fibonacci numbers in linear time:

fibs :: Int -> [Int]
fibs n = 
    let arr = listArray (1, n) (1 : 1 : [arr ! (i - 2) + arr ! (i - 1) | i <- [3 .. n]])
    in elems arr

counting sort

This function sorts a list of integers in a fixed range in linear time using an array.

sort :: Int -> Int -> [Int] -> [Int]
sort lo hi xs =
    let arr = accumArray (+) 0 (lo, hi) [(x, 1) | x <- xs]
    in concat [replicate x i | (i, x) <- assocs arr]