Чтобы протестировать, как церковно-закодированные списки работают против пользовательских списков и родных списков, я подготовил 3 теста:

Пользовательские списки

data List a = Cons a (List a) | Nil deriving Show
lenumTil n        = go n Nil where
    go 0 result   = result
    go n result   = go (n-1) (Cons (n-1) result)
lsum Nil          = 0
lsum (Cons h t)   = h + (lsum t)

main = print (lsum (lenumTil (100000000 :: Int)))

Родные списки

main = print $ sum ([0..100000000-1] :: [Int])

Церковные списки

fsum   = (\ a -> (a (+) 0))
fenumTil n cons nil = go n nil where
    go 0 result    = result
    go n result    = go (n-1) (cons (n-1) result)
main = print $ (fsum (fenumTil (100000000 :: Int)) :: Int)

Результаты теста неожиданные:

Пользовательские списки

-- 4999999950000000
-- real 0m22.520s
-- user 0m59.815s
-- sys  0m20.327s

Родные списки

-- 4999999950000000
-- real 0m0.999s
-- user 0m1.357s
-- sys  0m0.252s

Церковные списки

-- 4999999950000000
-- real 0m0.010s
-- user 0m0.002s
-- sys  0m0.003s

Можно ожидать, что с огромным количеством специфических оптимизаций, ориентированных на собственные списки, они будут работать лучше всего. Тем не менее церковные списки превосходят их в 100 раз, а пользовательские ADT превосходят в 2250 раз. Я собрал все программы сGHC -O2, Я пытался заменитьsum отfoldl', тот же результат. Я попытался добавить пользовательские данные, чтобы убедиться, что версия церковного списка не была оптимизирована до постоянной.arkeet на #haskell указал, что при проверке Core у нативной версии есть промежуточные списки, но почему? Принудительное выделение с дополнительнымreverseВсе 3 выполняют примерно одинаково.