WhnfConcatPerformance.hs

-- from https://twitter.com/haskell_cat/status/1533795075154755584
--
-- a micro-benchmark confirming that forcing the head of
--   ((xs_0 ++ xs_1) ++ ...) ++ xs_n
-- only takes linear time even though forcing the whole thing would
-- take quadratic time. It sure looks quadratic between n=1000 and
-- n=16000 though!

{-# LANGUAGE BangPatterns #-}
module Main where

import Prelude hiding ((++))
import Criterion.Main

(++) :: [()] -> [()] -> [()]
[] ++ ys
  = ys
(x:xs) ++ ys
  = x : (xs ++ ys)

measureConcat
  :: Int -> [()]
measureConcat n = go n
  where
    go :: Int -> [()]
    go 1
      = [()]
    go !i
      = go (i-1) ++ [()]

inputs
  :: [Int]
inputs
  = [1000,2000..60000]

main :: IO ()
main = defaultMain
  [ bgroup "concat"
      [ bench (show n)
      $ whnf measureConcat n
      | n <- inputs
      ]
  ]