Почему можно оптимизировать Tail Recursion Modulo Cons? - PullRequest
Новая
       33

Почему можно оптимизировать Tail Recursion Modulo Cons?

4 голосов
/ 01 марта 2020

Например, это не хвостовой вызов: 

map _ [] = []
map f (x : xs) = f x : map f xs

рекурсивный каллис, защищенный конструктором данных (:), поэтому он не будет создавать огромный стек, как эквивалент в некоторых других язык может сделать. Это работает так: 

map (+1) (1 : 2 : 3 : [])
2 : map (+1) (2 : 3 : [])
2 : 3 : map (+1) (3 : [])
2 : 3 : 4 : map (+1) []
2 : 3 : 4 : []

Почему бы и нет 

map (+1) (1 : 2 : 3 : [])
2 : map (+1) (2 : 3 : [])
2 : (3 : map (+1) (3 : []))
2 : (3 : (4 : map (+1) []))
2 : (3 : (4 : []))
2 : (3 : [4])
2 : [3, 4]
[2, 3, 4]

Это связано с WHNF, но я до сих пор не могу понять это хорошо: (

1 Ответ

8 голосов
/ 01 марта 2020

Потому что : ленив. Сам по себе он не вызывает оценку своего второго аргумента.

То, что вы показываете, не вся история. map также не выполняет то, что вы показываете, только если этого требует другой потребитель, чей результат в конечном итоге требует main (или REPL GHCi). Так, например, 

GHCi> take 2 (map (1+) [1..4]
   {- implied `putStrLn . show` causes this -}
   = take 2 (2 : map (1+) (enumFromTo 2 4))
   = 2 : take 1 (map (1+) (enumFromTo 2 4))
   = 2 : take 1 (3 : map (1+) (enumFromTo 3 4))
   = 2 : 3 : take 0 (map (1+) (enumFromTo 3 4))
   = 2 : 3 : []

Остальная часть списка ввода даже не вычисляется, потому что take не требует его от map, что, таким образом, не требует больше элементов из списка ввода.

Дополнительное примечание: TRM C - это терминология языков, стремящихся к оценке. В Haskell это называется защищенной рекурсией. Рекурсивный вызов должен быть за ленивым конструктором.

Я не верю, что Haskell (т.е. GH C) имеет TRM C -оптимизацию в строгом случае конструктора. В случае, если тип результата является моноидом, он может выглядеть следующим образом: 

[a] ++ ([b] ++ ([c] ++ ....))
=
([a] ++ [b]) ++ ([c] ++ ....)

Так что в нетерпеливом языке с TRMCO вместо первой оценки обоих аргументов наверху : действительно открывает O (n) стек вычислений, как подразумевает ваш второй фрагмент, сначала создаст верхний :, а затем заполнит его правый слот, работая итеративно в пространстве постоянного стека (как показывают фрагменты кода в Википедии).

Но в Haskell все это не применимо, когда конструктор ленив и оценка аргументов в любом случае не запускается сама по себе.

...