Do you have a question for the group or something you want to discuss? On Mon, Apr 25, 2011 at 8:50 PM, wrote:

-- 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

~~~~where ~~~~~~p = (length zs) `div` 2 ~~~~~~q = (length ws) `div` 2 ~~~~~~o = (length ts) `div` 2

~~~~~~(xs, a : ys) = splitAt p zs ~~~~~~(us, b : vs) = splitAt q ws ~~~~~~(rs, c : ss) = splitAt o ts

~~~~~~smallest3h'' k ((zs,p,ys),(ws,q),(ts,o,rs)) = ~~~~~~~~case (k<=p+q+o) of ~~~~~~~~~~(True) -> 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

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe