Мемоизация в монаде Писателя

Question

ПРИМЕЧАНИЕ. Я просто пытаюсь понять, что происходит в этом фрагменте кода, показанном ниже. Я знаю, что это не лучший способ решить проблему.

Я пытаюсь использовать ленивый Writer монада с запомненной функцией Фибоначчи для подсчета количества вызовов этой функции. Функция возвращает правильное значение быстро, но Writer среда никогда не возвращается и не использует процессор или память.

import Control.Monad.Writer.Lazy as W

fib :: Int -> Writer (Sum Int) Int
fib = let fibs = mapM fib' [0..]
          fib' 0 = return 0
          fib' 1 = return 1
          fib' n = liftM2 (+) (fib $ n-1) (fib $ n-2)
      in \n -> tell (Sum 1) >> fibs >>= return . (!!n)

Prelude W> runWriter $ fib 51
(20365011074,Sum {getSum = Interrupted.

Может кто-нибудь объяснить, что происходит? Почему среда не возвращает значение?

РЕДАКТИРОВАТЬ

Бесконечный список [0..] здесь не проблема Я пытался заменить его ограниченным списком, таким как [0..10] или же [0..n] но проблема все еще сохраняется.Если бы проблема заключалась в бесконечном списке, это было бы очень трудоемким вычислением, и именно поэтому я упомянул выше, что он не потребляет никакого процессора или памяти, что меня смущает.

Я полагаю, что из-за лени, где-то возникает тупик при оценке узлов fib функция.

Answer 1

Проблема в mapM fib' [0..], Это эффективное вычисление, которое вычисляет бесконечный список в монаде, и для этого также необходимо объединить бесконечное количество эффектов, в данном случае tell (Sum 1), Благодаря WriterЭто лень, вы можете получить доступ к результату, но счет внутри моноидальной части никогда не заканчивается.

Обновление: даже если вы сделаете список конечным, он все равно не будет работать. Проблема в том, что mapM fib' [0..10] представляет "список чисел Фибоначчи и общее количество вызовов, необходимых для их вычисления". Так в вашем выражении tell (Sum1) >> fibs >>= ... Вы всегда добавляете общее количество всех вызовов на счетчик, что явно не нужно.

Более того, он создает бесконечный цикл: любой вызов fib Запускает fib', который вычисляет количество вызовов для всех своих элементов, следовательно, вызывая (среди других вызовов) fib' 2, который вызывает fib снова. Бесконечная рекурсия останавливается, только если вы ограничите список [0..1], Опять проблема в том что mapM сочетает в себе все эффекты данных монадических вычислений.

Вместо этого вам нужно что-то вроде этого:

import Control.Monad.Writer.Lazy as W

fib :: Int -> Writer (Sum Int) Int
fib = let fibs = map fib' [0..] -- <<<<
          fib' 0 = return 0
          fib' 1 = return 1
          fib' n = liftM2 (+) (fib $ n-1) (fib $ n-2)
      in \n -> tell (Sum 1) >> fibs !! n -- <<<<

Вот fibs :: [Writer (Sum Int) Int]поэтому для каждого элемента он содержит как результат, так и количество вызовов, необходимых для его вычисления.