atamur Oct 21 2011 at 19:06

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

4 min

5.2K

Haskell*

+26

Comments 14

mixrin Oct 21 2011 at 20:29

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

CheatEx Oct 21 2011 at 22:06

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

atamur Oct 21 2011 at 23:04

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

CheatEx Oct 22 2011 at 00:22

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

Gokjer Oct 22 2011 at 18:15

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

atamur Oct 22 2011 at 22:30

Разница заключается в том, что на 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 Oct 23 2011 at 00:35

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

atamur Oct 23 2011 at 01:06

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

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

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

kingpin Oct 23 2011 at 14:07

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

main = getLine >>= putStrLn . map toUpper

tranquil Oct 24 2011 at 07:27

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

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

jakobz Oct 24 2011 at 12:53

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

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

atamur Oct 24 2011 at 14:36

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

idemura Oct 27 2011 at 18:53

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

atamur Oct 27 2011 at 19:16

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