[Haskell-cafe] Errata for "Pearls of Functional Algorithm Design" by Richard Bird, 2010, page 25 #Haskell

[caseyh at istar.ca]

-- Errata for "Pearls of Functional Algorithm Design" by Richard Bird,
-- 2010, page 25 #Haskell

-- I don't like this solution it suffers from "indexitis" which
-- Bird talks about in the chapter on Sudoku.
-- I can see why lists are liked, they avoid "indexitis" at
-- the cost of chopping and concatenating them.

-- One of the advantages of functional programming is supposed to be  
less bookkeeping.

smallest :: (Ord a) => Int -> (Array Int a, Array Int a) -> a
smallest k (xa,ya) =
~~~~search k (0,m+1) (0,n+1)
~~~~~~~~where
~~~~~~~~(0,m) = bounds xa
~~~~~~~~(0,n) = bounds ya

~~~~~~~~search k (lx,rx) (ly,ry)
~~~~~~~~~~~~| lx == rx = ya ! (k+ly)
~~~~~~~~~~~~| ly == ry = xa ! (k+lx)
~~~~~~~~~~~~| otherwise = case (xa ! mx < ya ! my, k <= mx-lx+my-ly) of
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(True, True) -> search k (lx,rx) (ly,my)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(True, False) -> search (k-(mx-lx)-1)  
(mx+1,rx) (ly,ry)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(False, True) -> search k (lx,mx) (ly,ry)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(False, False)-> search (k-(my-ly)-1)  
(lx,rx) (my+1,ry)
~~~~~~~~~~~~~~~~~~~~~~~~~~where
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~mx = (lx+rx) `div` 2
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~my = (ly+ry) `div` 2