Haskell Lazy Оценка и повторное использование

Я знаю, что если бы я вычислил список квадратов в Haskell, я мог бы сделать это:

squares = [ x ** 2 | x <- [1 ..] ]

Тогда, когда я вызываю квадраты следующим образом:

print $ take 4 squares

И он распечатает [1.0, 4.0, 9.0, 16.0]. Это оценивается как [1 ** 2, 2 ** 2, 3 ** 2, 4 ** 2]. Теперь, поскольку Haskell является функциональным, и каждый результат будет один и тот же, если бы я снова должен был называть квадраты где-то в другом месте, будет ли он переоценивать ответы, которые он уже вычислил? Если бы я повторно использовал квадраты после того, как я уже вызвал предыдущую строку, перерасчет первых 4 значений?

print $ take 5 squares

Будет ли он оцениваться [1.0, 4.0, 9.0, 16.0, 5 ** 2]?

Ответ 1

В этом случае он не будет пересчитан, потому что список фактически создается, и список квадратов продолжает существовать после вызова. Однако функции Haskell вообще не запоминаются. Это работает только в таком случае, когда вы явно не вызываете функцию, просто исследуя конечный список (in).

Ответ 2

Это значение squares потенциально полиморфно:

Prelude> :t [ x ** 2 | x <- [1 ..] ]
[ x ** 2 | x <- [1 ..] ] :: (Floating t, Enum t) => [t]

AFAIK, независимо от того, будет ли он пересчитываться (в GHC), зависит от того, задан ли значение верхнего уровня squares полиморфным типом. Я считаю, что GHC не делает никакой memoization полиморфных значений, включающих классы типов (функции от типов к значениям), так же как он не выполняет никаких заметок обычных функций (функции от значений до значений).

Это означает, что если вы определяете squares на

squares :: [Double]
squares = [ x ** 2 | x <- [1 ..] ]

то squares будет вычисляться только один раз, а если вы определяете его

squares :: (Floating t, Enum t) => [t]
squares = [ x ** 2 | x <- [1 ..] ]

то он, вероятно, будет вычисляться каждый раз, когда он будет использоваться, даже если он многократно используется для одного и того же типа. (Я не тестировал это, и, возможно, GHC, если он видит несколько видов использования squares :: [Double], может специализировать значение squares для этого типа и делиться полученным значением.) Конечно, если используется squares на нескольких разных типах, таких как squares :: [Double] и squares :: [Float], он будет пересчитан.

Если вы не укажете подпись типа squares, то к ней применится ограничение

Ответ 3

Чтобы прояснить уже заданный ответ, это функция Haskell:

thisManySquares n = map (^2) [1..n]

Итак, если вы заменили вызовы "thisManySquares 4" для вашего take 4 squares, то да, он будет вызывать функцию повторно.

Ответ 4

Почему бы не использовать ghci для тестирования (если ghc является вашим компилятором):

Prelude> let squares = [ x ** 2 | x <- [1 ..] ] :: [Float]
Prelude> :print squares
squares = (_t6::[Float])

Итак, все ghci знают, что у вас есть список.

Prelude> print $ take 4 squares
[1.0,4.0,9.0,16.0]
Prelude> :print squares
squares = 1.0 : 4.0 : 9.0 : 16.0 : (_t7::[Float])

Знайте, что он знает, что ваш список начинается с материала, потому что ему нужно было его распечатать.

Prelude> let z = take 5 squares
Prelude> :print z
z = (_t8::[Float])

взять 5 сам по себе не оценивает ничего

Prelude> length z --Evaluate the skeleton
5
Prelude> :print z
z = [1.0,4.0,9.0,16.0,(_t9::Float)]

Взятие длины приводит к тому, что take запускает свой курс, и мы видим, что вы были правы. Вы можете проверить, что происходит, когда оно также полиморфно, просто опуская определение типа на квадратах. Еще один хороший трюк, если вы не хотите использовать ghci, - это использовать undefined в вашем коде (ваша программа срабатывает точно, когда пытается оценить _|_, тип undefined - это тип.)