An explanation for the benchmark results in https://github.com/vmchale/ats-benchmarks

Derangement.hs

-- This gist provides an explanation for why Haskell is significantly
-- faster than ATS and Rust in [vmchale’s great
-- benchmarks](https://github.com/vmchale/ats-benchmarks). What’s
-- happening is that the `derangements` list gets memoized so the
-- benchmark only checks the performance of (!!). `derangements'`
-- prevents GHC from memoizing the list and results in a significant
-- loss of performance. Criterion does try to prevent memoization but
-- it only prevents memoization of the function application (that’s
-- why the function and the argument need to be passed separately to
-- `nf`). It cannot prevent the memoization of the `derangements`
-- list.

-- This is necessary to prevent GHC from floating out the list in derangements'
{-# OPTIONS_GHC -fno-full-laziness #-}
module Main where

import Criterion.Main

derangement :: Int -> Integer
derangement = (derangements !!)

derangements :: [Integer]
derangements = fmap snd g
    where g = (0, 1) : (1, 0) : zipWith (\(_, n) (i, m) -> (i + 1, i * (n + m))) g (tail g)

derangement' :: Int -> Integer
derangement' = \i ->
  let derangements = derangements' ()
  in derangements !! i

derangements' :: () -> [Integer]
derangements' () = fmap snd g
    where g = (0, 1) : (1, 0) : zipWith (\(_, n) (i, m) -> (i + 1, i * (n + m))) g (tail g)

ints :: [Integer]
ints = [0..64]

index :: Int -> Integer
index = (!!) ints

main :: IO ()
main =
  defaultMain
    [ bgroup
        "derangement"
        [ bench "derangement (64)" $ nf derangement 64
        , bench "derangement' (64)" $ nf derangement' 64
        , bench "[0..64] !! 64" $ nf index 64
        , bench "id (96800425246141091510518408809597121)" $
          nf id (96800425246141091510518408809597121 :: Integer)
        ]
    ]