```
1 {-
2
3 Pearl 1: Smallest Free Number
4
5 Problem:
6 Assume X is a list of distinct Natural numbers (non-negative integers), in no particular order.
7 Find the smallest number not in the list.
8
9 We will show two algorithms that do it in LINEAR time.
10 On first sight, it is not clear such exist. After all, sorting a list is no linear time.
11 But there's a trick.
12
13 The key trick: not every number in the range [0..length xs] can be in xs!
14 Thus, the smallest number NOT in xs is then the smallest number not in
15 filter (<=n) xs, where n=length xs.
16
17 The two programs:
18 Array based: builds a checklist of the numbers present in filter (<=n) xs.
19
20 Divide and conquer:
21 express minfree(xs++ys) in terms of minfree xs  and minfree ys.
22
23 -}
24 module P1 where
25
26 import Data.Array     (Array, elems, accumArray)
27 import Data.List     (partition)
28 testX = [8,23,9,0,12,11,1,10,13,7,41,21,5,17,3,19,2,6] :: [Int]
29
30 type Nat = Int     -- Just for ease of reading things here. Not correct!!
31
32 -- Brute force approach
33 -- Requires O(N^2) steps
34 -- (see implemntation of (\\) )
35 minfree :: [Nat] -> Nat
36 minfree xs = head ([0..] \\ xs)
37
38 -- where  us (\\) vs    denotes the list of those elements in us remaining after removing
39 -- any elements in vs.
40 (\\)    :: Eq a => [a] -> [a] -> [a]
41 us \\ vs = filter ( `notElem` vs) us
42
43 -- Array based method: Build the checklist as an array
44 -- We will use the 'tricky' function accumArray, which will enable us to do it in linear time.
45 -- accumArray: Constructs an immutable array from a list of associations.
46 -- Unlike array, the same index is allowed to occur multiple times in the list of associations;
47 -- an accumulating function is used to combine the values of elements with the same index.
48
49 checkList         :: [Nat] -> Array Nat Bool
50 checkList xs     =  accumArray         --
51                     (||)             -- accumlating function. not realy used, as no duplicates!
52                     False            -- inital entry for each index
53                     (0,n)            -- (lower/upper) indices of new array
54                     (zip (filter (<= n) xs) (repeat True) )    -- index-value pairs
55                     where
56                         n = length xs
57 -- Just for fun: Another use of accumArray: Sorting array in LINEAR time, if we know all
58 -- values lie between (0,n)
59 -- in our case, we can then look for the first '0' in the resulting array
60
61 countList        ::  [Nat] -> Array Nat Nat
62 countList xs    =   accumArray (+) 0 (0,n) ( zip xs (repeat 1))
63                     where
64                         n = length xs
65
66 -- Once we have the array, finding the minimum is simple:
67 -- (elems converts array into a list)
68 search :: Array Nat Bool -> Nat
69 search = length.takeWhile id.elems
70
71 -- Divide and conquer
72 minFree xs            =    minFrom 0 (length xs,xs)
73 minFrom a (n,xs)    |    n==0        = a
74                     |    m==b-a        = minFrom b (n-m,vs)    -- if us has exactly the number of spots,
75                                                             -- and since there's no repetiion, it means
76                                                             -- the gap have to be in the OTHER series:
77                                                             -- so we continue the search with vs
78                     |    otherwise    = minFrom a (m,us)        -- if us had the gap ==> keep searching there!
79                         where
80                             (us,vs) = partition (<b) xs        -- partitioning to 'two halves'
81                             b         = a + 1 + n `div` 2     -- b is the middle of [a..n]
82                             m         = length us
83
84 -- Main
85
86 main = do
87     putStr "Brute force       : "
88     print \$ minfree testX
89     putStr "Array method      : "
90     print \$ search \$ checkList testX
91     putStr "Divide and Conquer: "
92     print \$ minFree testX
```    