Странное пространственное поведение программы Хаскелла

Я думал, что 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М.

7
задан Matthieu M. 24 August 2011 в 06:41
поделиться