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

Question

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

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

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, но я до сих пор не могу этого понять:(

6

haskell recursion functional-programming lazy-evaluation tailrecursion-modulo-cons

Источник

user12988183 01 мар '20 в 14:57

1 ответ

Другие вопросы по тегам haskell recursion functional-programming lazy-evaluation tailrecursion-modulo-cons

user849891 01 мар '20 в 15:10 2020-03-01 15:10 · Answer 1 · 2020-03-01 15:10

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

То, что вы показываете, - это еще не вся история. 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 который, таким образом, не требует больше элементов из входного списка.

Примечание: TRMC очень внимательно изучает терминологию языков. В Haskell это называется защищенной рекурсией. Рекурсивный вызов должен быть за ленивым конструктором.

Я не верю, что Haskell (то есть GHC) имеет TRMC-оптимизацию в случае строгого конструктора. Это могло бы быть, если тип результата - моноид, как списки действительно:

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

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

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