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

KC kc1956 at gmail.com
Tue Apr 19 01:30:36 CEST 2011


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

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



-- 
--
Regards,
KC



More information about the Haskell mailing list