fix

[voidex]

Ковырялся тут с fix, написал такую штуку:
fib self 0 = 1
fib self 1 = 1
fib self n = self (n - 2) + self (n - 1)

fixMemo f = let x = f (map x [0..] !!) in x
fixMemo fib 10000 отрабатывает почти мгновенно, в отличие от.

Других открытий, правда, не сделал, а они есть?

Comments

[beroal]

Это напомнило мне следующий пост: From Löb's Theorem to Spreadsheet Evaluation. В fixMemo ты для кэширования используешь список, преобразуя Int -> num в [num] и обратно. Оба типа являются функтором от num. Поэтому fixMemo можно определить через loeb:

fibMemoLoeb = loeb (map (\n memo -> fib (memo !!) n) [0..])
А это обычная функция Фибоначчи, без кэширования:

fibLoeb :: (Num a, Num b) => a -> b
fibLoeb = loeb (\n self -> fib self n)
где

loeb x = let y = fmap (\a -> a y) x in y

[deni_ok]

О, какая хорошая функция

loeb :: (Functor f) => f (f b -> b) -> f b

[beroal]

Хороша для медитаций? ;)

[deni_ok]

Именно!