-- Extension for "Pearls of Functional Algorithm Design" by Richard Bird,
-- 2010, page 25 #Haskell
-- This version assumes 3 disjoint ordered sets represented as lists.
-- So either: x<y XOR x>y
-- Since it uses lists it is no faster than the divide and conquer approach.
-- I might try to convert this version to sorted arrays for
-- O(log|X|+log|Y|+log|Z|) performance
-- If I can figure out how to do it without suffering from "indexitis".
smallest3'' :: Ord a => Int -> ([a], [a], [a]) -> a
smallest3'' k ([],[],ts) = ts !! k
smallest3'' k (zs,[],[]) = zs !! k
smallest3'' k ([],ws,[]) = ws !! k
smallest3'' k ([],ws,ts) = smallest'' k (ws,ts)
smallest3'' k (zs,[],ts) = smallest'' k (zs,ts)
smallest3'' k (zs,ws,[]) = smallest'' k (zs,ws)
smallest3'' k (zs,ws,ts) =
~~~~case (a smallest3h'' k
((zs,p,ys),(ws,q),(ts,o,rs)) -- a smallest3h'' k
((zs,p,ys),(ts,o),(ws,q,us)) -- a smallest3h'' k
((ws,q,vs),(zs,p),(ts,o,rs)) -- b smallest3h'' k
((ws,q,vs),(ts,o),(zs,p,xs)) -- b smallest3h'' k
((ts,o,ss),(zs,p),(ws,q,us)) -- c smallest3h'' k
((ts,o,ss),(ws,q),(zs,p,xs)) -- c smallest3'' k (zs,ws,rs)
~~~~~~~~~~(False) -> smallest3'' (k-p-1) (ys,ws,ts)
smallest'' :: Ord a => Int -> ([a], [a]) -> a
smallest'' k ([],ws) = ws !! k
smallest'' k (zs,[]) = zs !! k
smallest'' k (zs,ws) =
~~~~case (a smallest'' k (zs,us)
~~~~~~(True, False) -> smallest''(k-p-1) (ys,ws)
~~~~~~(False, True) -> smallest'' k (xs,ws)
~~~~~~(False, False)-> smallest''(k-q-1) (zs,vs)
~~~~where
~~~~~~p = (length zs) `div` 2
~~~~~~q = (length ws) `div` 2
~~~~~~(xs, a : ys) = splitAt p zs
~~~~~~(us, b : vs) = splitAt q ws
