Skip to content

Instantly share code, notes, and snippets.

@553224019

553224019/Hamming.hs

Created April 2, 2019 06:00
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save 553224019/fbc59196bd654ac278af39a595c5bb9a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save 553224019/fbc59196bd654ac278af39a595c5bb9a to your computer and use it in GitHub Desktop.
Download ZIP
Comparison between two solutions to hamming numbers in Haskell
Raw
Hamming.hs
module Hamming (ham1, ham2) where
ham1 :: [Integer]
ham1 = 1 :
map (* 2) ham1 `merge`
map (* 3) ham1 `merge`
map (* 5) ham1
merge :: Ord a => [a] -> [a] -> [a]
merge [] l = l
merge l [] = l
merge (x : xs) (y : ys) | x < y = x : merge xs (y : ys)
| x == y = x : merge xs ys
| otherwise = y : merge (x : xs) ys
ham2 :: Integer -> [Integer] -> ([Integer], [Integer], [Integer]) -> [Integer]
ham2 1 xs _ = xs
ham2 n xs (q2, q3, q5) = ham2 (n - 1) (xs ++ [x]) update
where
x = minimum $ map head [q2, q3, q5]
update | x == head q2 = ((tail q2) ++ [x * 2], q3 ++ [x * 3], q5 ++ [x * 5])
| x == head q3 = (q2, (tail q3) ++ [x * 3], q5 ++ [x * 5])
| otherwise = (q2, q3, (tail q5) ++ [x * 5])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment