Benchmarking CollatzConjecture

bench.hs

module Main where

import CollatzConjecture
import Criterion
import Criterion.Main

main :: IO ()
main = defaultMain
  [ bgroup "collatz" [ bench "recursive"           $ nf collatz1 n
                     , bench "recursive extra arg" $ nf collatz2 n
                     , bench "recursive strict"    $ nf collatz3 n
                     , bench "iterate takeWhile"   $ nf collatz4 n
                     , bench "iterate elemIndex"   $ nf collatz5 n
                     ]
  ] where n = 1000000

CollatzConjecture.hs

{-# LANGUAGE BangPatterns #-}
module CollatzConjecture ( collatz
                         , collatz1
                         , collatz2
                         , collatz3
                         , collatz4
                         , collatz5
                         ) where

import Data.List (genericLength, elemIndex)

collatz :: Integer -> Maybe Integer
collatz = collatz1

next :: Integer -> Integer
next n
  | even n = n `quot` 2
  | otherwise = 3 * n + 1

-- Recursive 1

collatz1 :: Integer -> Maybe Integer
collatz1 n
  | n < 1 = Nothing
  | otherwise = Just (go n)
  where
    go :: Integer -> Integer
    go 1 = 0
    go m = 1 + go (next m)

-- Recursive 2, extra argument

collatz2 :: Integer -> Maybe Integer
collatz2 n
  | n < 1 = Nothing
  | otherwise = Just (go n 0)
  where
    go :: Integer -> Integer -> Integer
    go 1 res = res
    go m res = go (next m) res

-- Recursive 3, strict

collatz3 :: Integer -> Maybe Integer
collatz3 n
  | n < 1 = Nothing
  | otherwise = Just (go n 0)
  where
    go :: Integer -> Integer -> Integer
    go 1  !res = res
    go !m !res = go (next m) res

-- iterate, takeWhile

collatz4 :: Integer -> Maybe Integer
collatz4 n
  | n < 1 = Nothing
  | otherwise = Just . genericLength . takeWhile (/= 1) . iterate next $ n

-- iterate, elemIndex

collatz5 :: Integer -> Maybe Integer
collatz5 n
  | n < 1 = Nothing
  | otherwise = fromIntegral <$> elemIndex 1 (iterate next n)

package.yaml

name: collatz-conjecture
version: 1.2.0.2

dependencies:
  - base

library:
  exposed-modules: CollatzConjecture
  source-dirs: src

tests:
  test:
    main: Tests.hs
    source-dirs: test
    dependencies:
      - collatz-conjecture
      - hspec

benchmarks:
  bench:
    main: bench.hs
    source-dirs: bench
    dependencies:
      - collatz-conjecture
      - criterion
    ghc-options: -O2