I m reading a book Pearls of Functional Algorithm Design . Tried implementing the divide and conquer solution for smallest free number problem.
minfree xs = minfrom 0 (length xs) xs minfrom a 0 _ = a minfrom a n xs = if m == b - a then minfrom b (n-m) vs else minfrom a (m) us where b = a + 1 + (n `div` 2) (us,vs) = partition (<b) xs m = length us
But this one works no faster than the solution that one might call "naive" solution. Which is
import Data.List ((\)) minfree = head . (\) [0..]
I don t know why this is like this, what s wrong with the divide and conquer algorithm and how to improve it.
Tried using BangPatterns, implementing the version of partition that also returns first list s length in the tuple, so it eliminates additional traversal for m =length us. None of them made improvement.
First one takes more than 5 seconds, whereas second one does it almost instantly in ghci on input [0..9999999].