Динамическое программирование и ленивые вычисления

[mixrin]

Кратко, просто и по делу

[CheatEx]

«Т.е. нам нужно как-то указать, что мы имеем в виду одни и те же выражения» — тут встаёт вопрос… А на кой чёрт в Хаскеле сделан весь этот геморрой с IO, если реально референциальная прозрачность не используется?

[atamur]

Она используется, вопрос в том, как понять вычислялось ли такое выражение раньше или нет. Вместо того, чтобы искать среди всех выражений программы (слишком долго) используется ссылка на выражение.

[CheatEx]

Не вижу при таком подходе отличий от богомерзкой джавы. Что там что там надо думать о том, что и когда вычисляется. Тока в джаве когда хочется чёнить в лог сказать можно взять и сказать.

[Gokjer]

В Хаскеле есть инструменты для дебага. Например — Debug.trace, если мне не изменяет память, печатает из любого места программы.

[atamur]

Разница заключается в том, что на java такого не напишешь:

primes = 2 : filter prime [3,5..]
prime p = not (any (\x -> p`mod`x == 0) (takeWhile (\x -> x^2 <= p) primes))
main = print (take 10 primes)

А думать вообще стоит всегда ;)

[CheatEx]

А фибоначчи то как убого выглядит! Не джаве не место в промышленности…

[atamur]

А как вам тогда ленивый ввод-вывод? ;)

main =
  do text <- getContents
     putStr (map toUpper text)

и это для данных любого размера!

[kingpin]

Так короче ;-)

main = getLine >>= putStrLn . map toUpper

[tranquil]

> Не джаве не место в промышленности…

Разработчики на php, с++ смотрят как-то недовольно, свирепо и в то же время грустно и с недоумением.

[jakobz]

Я так понимаю это работает как-то за счет Constant Applicative Forms, грубо говоря за счет того, что константные выражения вычисляются только один раз. Верно?

Кто-нибудь может дать ссылки где поподробнее про это расписано?

[atamur]

Нет, это связано как раз с ленивыми вычислениями, а точнее с Sharing.

[idemura]

А всегда ли такой метод пройдет? Определить массив и вместо вызова функции обращаться к ячейке массива? Есть ограничения?

[atamur]

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