Навеяно темой Решение Problem K на Эрланг: дизайн

Автор: Gaperton
Дата: 06.11.07

В хаскелле вычисления ленивые, поэтому мемоизация делается сравнительно просто.
Например,

f 0 = .....
f n = .....(f k)....(f l)....(f m)..... -- где k,l,m < n

-- превращаем в бесконечный список заготовок
memo = [ f' n | n <- [0..] ]
f n = memo !! n
-- можно и другие структуры, с более эффективным доступом
-- например, кучу - т.е. список массивов экспоненциально возрастающей длины

f' 0 = .....
f' n = .....(f k)....(f l)....(f m).....

Если f n для какого-то n зацикливается, то, естественно, мы получим зависание — что в исходной формуле, что с мемоизацией.

Допустим, мы хотим как-то диагностировать зацикливание — чтобы получать не _|_, а какой-то определённый результат, например, банальное None.

Если бы memo было изменяемым — то нет ничего проще. Каждая ячейка принимает одно из трёх значений: ( ещё-не-вычисляли, начали-вычислять, результат ).
Обращение к ячейке со значением начали-вычислять — это и есть признак цикла.

Но в суровой реальности у нас выбор лишь между ещё-не-вычисляли и результатом.
Что делать?

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

f 0 _ = return .....
f n ns =
    do
        let False = n `elem` ns -- в случае нестыковки стремительно выйдем
        let ns' = n:ns
        fk <- f k ns'
        fl <- f l ns'
        fm <- f m ns'
        return .....fk.....fl.....fm.....

А можно ли сделать то же самое, не занимаясь трассировкой вручную?