Из соображений эффективности GHC преобразует список, используемый только один раз, в генератор? - PullRequest
Новая
       16

Из соображений эффективности GHC преобразует список, используемый только один раз, в генератор?

5 голосов
/ 26 ноября 2011

Если это так, является ли это частью стандартной или специфической для GHC оптимизации, от которой мы можем зависеть? Или просто оптимизация, от которой мы не можем зависеть.

P.S .: Когда я попробовал тестовый образец, он, казалось, указывал на то, что он имел место / 

Prelude> let isOdd x = x `mod` 2 == 1
Prelude> let isEven x = x `mod` 2 == 0
Prelude> ((filter isOdd).(filter isEven)) [1..]

жует процессор, но не потребляет много памяти.

Ответы [ 2 ]

7 голосов
/ 26 ноября 2011

Зависит от того, что вы подразумеваете под генератором. Список генерируется лениво, и поскольку ничто иное не ссылается на него, использованные части собираются почти сразу же. Поскольку результат вышеуказанного вычисления не растет, все вычисления выполняются в постоянном пространстве. Это не предусмотрено стандартом, но так как в этом примере сложнее реализовать нестрогую семантику с различным поведением пространства (и множеством неопределенно похожих), на практике вы можете положиться на это.

Но обычно список по-прежнему генерируется как список, поэтому создается много мусора. При благоприятных обстоятельствах ghc исключает список [1 .. ] и создает неразмещающий цикл: 

result :: [Int]
result = filter odd . filter even $ [1 .. ]

(используя функции Prelude из-за лени), скомпилированный с -O2 генерирует ядро ​​

List.result_go =
  \ (x_ayH :: GHC.Prim.Int#) ->
    case GHC.Prim.remInt# x_ayH 2 of _ {
      __DEFAULT ->
        case x_ayH of wild_Xa {
          __DEFAULT -> List.result_go (GHC.Prim.+# wild_Xa 1);
          9223372036854775807 -> GHC.Types.[] @ GHC.Types.Int
        };
      0 ->
        case x_ayH of wild_Xa {
          __DEFAULT -> List.result_go (GHC.Prim.+# wild_Xa 1);
          9223372036854775807 -> GHC.Types.[] @ GHC.Types.Int
        }
    }

Простой цикл, работающий от 1 до maxBound :: Int, ничего не производящий в пути и [] в конце. Это почти достаточно умно, чтобы просто вернуть []. Обратите внимание, что есть только одно деление на 2, GHC знает, что если Int является четным, оно не может быть нечетным, поэтому проверка исключена, и ни в одной ветви не создается непустой список (т. Е. Недоступный). ветви были устранены компилятором).

2 голосов
/ 26 ноября 2011

Строго говоря, Haskell не определяет какую-либо конкретную модель оценки, поэтому реализации могут свободно реализовывать семантику языка так, как они хотят. Однако в любой разумной реализации, включая GHC, вы можете рассчитывать на этот запуск в постоянном пространстве.

В GHC вычисления, подобные этим, приводят к односвязному списку, заканчивающемуся разделом, представляющим остаток списка, который еще не был оценен. При оценке этого списка большая часть списка будет создаваться по требованию, но поскольку начало списка не упоминается нигде, более ранние части сразу же пригодны для сборки мусора, поэтому вы получаете постоянное пространство.

С включенной оптимизацией GHC, скорее всего, выполнит здесь вырубку леса, оптимизируя необходимость в наличии списка вообще, и в результате получится простой цикл без выделения.

...