Я думал, что Cont
monad просто эквивалентен преобразованию CPS, так что если у меня есть
монадную сумму, если я запущу в Identity
monad, то это не удастся из-за переполнения стека, а также, если
Я запустил его в Cont
Monad, все будет в порядке из-за рекурсии хвоста.
Итак, я написал простую программу, чтобы проверить свою идею. Но, к моему удивлению, результат неразумный из-за моих ограниченных знаний.
Все программы скомпилированы с использованием ghc --make Test.hs -o test && ./test
sum0 n = if n==0 then 0 else n + sum0 (n-1)
sum1 n = if n==0 then return 0 else sum1 (n-1) >>= \ v -> seq v (return (n+v))
sum2 n k = if n == 0 then k 0 else sum2 n (\v -> k (n + v))
sum3 n k = if n == 0 then k 0 else sum3 n (\ !v -> k (n + v))
sum4 n k = if n == 0 then k 0 else sum4 n (\ v -> seq v ( k (n + v)))
sum5 n = if n==0 then return 0 else sum5 (n-1) >>= \ v -> (return (n+v))
main = print (sum0 3000000)
Stack overflow. Это разумно.
main = print (flip runCont id (sum1 3000000))
Использует 180М памяти, что разумно, но мне непонятно, зачем здесь нужна seq
, так как ее продолжение не применяется до тех пор, пока n
не перейдет на 0.
main = print (flip runCont id (sum5 3000000))
Переполнение стека. Почему?
main = print (flip runCont (const 0) (sum1 3000000))
Использует 130М памяти. Это разумно.
main = print (flip runCont (const 0) (sum5 3000000))
Использует 118М памяти. Это разумно.
main = print (sum2 3000000 (const 0))
Использует много памяти (более 1Гб). Я думал, что sum2
эквивалентно sum5
(когда sum5
находится в Cont
monad). Почему?
main = print (sum3 3000000 (const 0))
Использует много памяти. Я думал, что sum3
эквивалентно sum1
(Cont
monad). Почему?
main = print (runIdentity (sum1 3000000))
Stack overflow, именно то, что я хочу.
main = print (sum3 3000000 id)
Использует много памяти. Эквивалент sum1
, почему?
main = print (sum4 3000000 id)
Использует много памяти. Эквивалент sum1, почему?
main = print (sum [1...3000000])
Переполнение стека. Источник sum = фолд (+) 0
, так что это разумно.
main = print (foldl' (+) 0 [1 ... 3000000])
Использует 1,5М.