hail2.hs

-- Collatz sequence.  See rosettacode.org/wiki/Hailstone_sequence#Haskell

import Data.List (maximumBy)
import Data.Ord (comparing)

main :: IO ()
main = putStrLn $ "Collatz sequence for 27: "
          ++ (show.hailstone $ 27)
          ++ "\n"
          ++ "The number "
          ++ (show longestChain)
          ++" has the longest hailstone sequence"
          ++" for any number less then 100000. "
          ++"The sequence has length " 
          ++ (show.length.hailstone $ longestChain)
 
hailstone :: Integer -> [Integer]
hailstone = takeWhile (/=1) . (iterate collatz)
   where collatz n = if even n then n `div` 2 else 3*n+1
 
longestChain :: Integer
longestChain = maximumOn (length.hailstone) [1..100000]

{-
   -- The more obvious way of is not much slower.

longestChain' = fst $ maximumBy (comparing snd) $ map pairUp [1..100000]
   where pairUp i = (i, (length.hailstone) i)
 -}

{-
   The "Schwartzian Transform" https://en.wikipedia.org/wiki/Schwartzian_transform
   avoid recomputing the keys of comparison.  Haskell has a 'sortOn' to go with
   its 'sortBy', but as of yet there is no 'maximumOn'.
-}

{-
sortBy :: (a -> a -> Ordering) -> [a] -> [a]
maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a

sortOn :: Ord b => (a -> b) -> [a] -> [a]
sortOn f =
  map snd . sortBy (comparing fst) . map (\x -> let y = f x in y `seq` (y, x))
 -}

-- New feature request #15566: https://ghc.haskell.org/trac/ghc/ticket/15566
maximumOn :: Ord b => (a -> b) -> [a] -> a
maximumOn f =
  snd . maximumBy (comparing fst) . map (\x -> let y = f x in y `seq` (y, x))

--  ------------For GNU Emacs ------------
--  Local Variables:
--  compile-command: "ghc -Wall -O2 hail2.hs"
--  End: