hemming.hs

import Criterion.Main

merge2 :: Ord a => [a] -> [a] -> [a]
merge2 (x:xs) (y:ys) = case compare x y of
    EQ -> x : merge2 xs ys
    LT -> x : merge2 xs (y:ys)
    GT -> y : merge2 (x:xs) ys

hemming :: [Integer]
hemming = 1 : (map (*2) hemming `merge2` map (*3) hemming `merge2` map (*5) hemming)

join :: Ord a => [[a]] -> [a]
join ((x:xs):t) = x : merge2 xs (join t)

hemming2 :: [Integer]
hemming2 = join [join [[z | z <- iterate (*5) y] | y <- iterate (*3) x] | x <- iterate (*2) 1]

main = defaultMain
    [ bench "hemming" $ whnf (hemming!!) 100000
    , bench "hemming2" $ whnf (hemming2!!) 100000
    ]