Чтобы проверить, как списки, кодированные церковью, выполняются в отношении списков пользовательских прав и собственных списков, я подготовил 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 с коэффициентом 2250x. Я скомпилировал все программы с помощью GHC -O2. Я попытался заменить sum на foldl', тот же результат. Я попытался добавить пользовательские входы, чтобы убедиться, что версия церковного списка не оптимизирована для константы. arkeet указал на #haskell, что, проверив Core, родная версия имеет промежуточные списки, но почему? Выделение выделения с помощью дополнительного reverse, все 3 выполняют примерно то же самое.
