Почему сумма медленнее, чем foldl 'в haskell?

Question

Каким образом значение по умолчанию sum в ghc составляет ~ 10 раз медленнее, чем его foldl' (stricter equivalent из foldl) эквивалентно? И если это так, почему это не реализовано с использованием foldl'?

import Data.List 
> foldl' (+) 0 [1..10^7] 
50000005000000 
(0.39 secs, 963,528,816 bytes) 

> sum [1..10^7] 
50000005000000 
(4.13 secs, 1,695,569,176 bytes) 

Для полноты здесь также статистика foldl и foldr.

> foldl (+) 0 [1..10^7] 
50000005000000 
(4.02 secs, 1,695,828,752 bytes) 

> foldr (+) 0 [1..10^7] 
50000005000000 
(3.78 secs, 1,698,386,648 bytes) 

Похоже sum реализуется с использованием foldl с момента их выполнения аналогична. Протестировано на ghc 7.10.2.

Answer 1

sum функция реализуется с помощью foldl в GHC:

-- | The 'sum' function computes the sum of a finite list of numbers. 
sum      :: (Num a) => [a] -> a 
{-# INLINE sum #-} 
sum      = foldl (+) 0 

как можно видеть in the source.

Должно быть так, потому что это спецификация in the Haskell report.

Обоснование было вероятным, что для определенных ленивых типов элементов списка, foldl - это правильная вещь. (Я лично считаю, что foldl почти всегда ошибочен и должен использоваться только foldl'.)

С достаточной оптимизацией GHC построит это определение, специализируясь на этом типе элемента, заметим, что цикл является строгим, и сила оценка аккумулятора на каждой итерации; фактически превращая это в foldl', как заметил @ AndrásKovács.

Поскольку GHC-7.10, sum itself - это метод класса Foldable, а определение по умолчанию осуществляется через foldMap. Однако instance Foldable [] переопределяет это с помощью вышеуказанного определения sum.

Answer 2

В дополнение к ответу @Joachim Breitner я нашел это blog post, очень интересное чтение (взято из обсуждения reddit, благодаря @ZhekaKozlov для ссылки).

Когда Haskell 1.0 был опубликован в этот день 24 года назад, функции seq вообще не было, поэтому не было выбора, кроме как определить foldl в «классическом» способе.

В конце концов, через шесть лет после большого обсуждения мы получили функцию seq в Haskell 1.3. Хотя на самом деле в Haskell 1.3 seq был частью класса Eval, поэтому вы не могли использовать его нигде, например, в foldl. В Haskell 1.3 вы должны были бы определить foldl»с типом:

foldl' :: Eval b => (b -> a -> b) -> b -> [a] -> b 

Haskell 1.4 и Haskell 98 избавившись от ограничения класса Eval для SEQ но foldl не был изменен. Объятия и GHC и другие реализации добавили нестандартный склад.

Я подозреваю, что люди тогда считали это проблемой совместимости и инерции. Достаточно просто добавить нестандартную складку, но вы не можете так легко изменить стандарт.

Я подозреваю, что если бы у нас был seq с самого начала, мы бы определили его с использованием.

Миранда, один из предшественников языка Хаскелла, уже имел 5 лет до Haskell 1.0.

Кстати, я успел побриться 20 мс больше, используя

foldl1' (+) [1..10^7] 

Так что, я думаю, foldl1' должен быть по умолчанию для sum и product (со специальной обработкой пустых списков).