Странное пространственное поведение программы на Haskell

Question

Я думал, что монада Cont просто эквивалентна преобразованию CPS, поэтому, если у меня есть монадическая сумма, если я запускаю монаду Identity, она потерпит неудачу из-за переполнения стека, и если я запусту ее вCont Монада, все будет хорошо благодаря хвостовой рекурсии.

Итак, я написал простую программу для проверки моей идеи.Но, к моему удивлению, результат неоправдан из-за моих ограниченных знаний.

Все программы скомпилированы с использованием 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)
  Переполнение стека.Это разумно.

• main = print (flip runCont id (sum1 3000000))
  Используется память 180M, что разумно, но я не понимаю, зачем здесь нужен 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))
  Использует 118M памяти.Это разумно.

• main = print (sum2 3000000 (const 0))
  Используется много памяти (более 1 ГБ).Я думал, что sum2 эквивалентно sum5 (когда sum5 находится в Cont монаде).Почему?

• main = print (sum3 3000000 (const 0))
  Использует много памяти.Я думал, что sum3 эквивалентно sum1 (Cont монада).Зачем?

• main = print (runIdentity (sum1 3000000))
  Переполнение стека, именно то, что я хочу.

• main = print (sum3 3000000 id)
  Использует много памяти.Эквивалент sum1, почему?

• main = print (sum4 3000000 id)
  Использует много памяти.Почему эквивалентно sum1?

• main = print (sum [1 .. 3000000])
  Переполнение стека.Источник sum = foldl (+) 0, так что это разумно.

• main = print (foldl' (+) 0 [1 .. 3000000])
  Использует 1,5M.

Answer 1

Прежде всего, мне кажется, что sum2, sum3 и sum4 никогда не уменьшаются n. Таким образом, они используют много памяти, потому что они входят в бесконечный цикл, который выполняет распределение.

После исправления я снова запустил каждый из ваших тестов со следующими результатами, где "распределение" относится к приблизительному пиковому использованию памяти:

• main = print (sum0 3000000): переполнение стека после выделения очень маленькой памяти
• main = print (flip runCont id (sum1 3000000)): успех, распределение суммы, аналогичной тому, что вы видели
• main = print (flip runCont id (sum5 3000000)): переполнение стека после выделения таких же объемов памяти, как sum1.
• main = print (flip runCont (const 0) (sum1 3000000)): успех, распределение, аналогичное приведенному выше
• main = print (flip runCont (const 0) (sum5 3000000)): то же
• main = print (sum2 3000000 (const 0)): успех, примерно на 70% больше, чем sum1
• main = print (sum3 3000000 (const 0)): успех, примерно на 50% больше, чем sum1
• main = print (runIdentity (sum1 3000000)): переполнение стека с небольшим распределением
• main = print (sum3 3000000 id): успех - примерно на 50% больше, чем sum1
• main = print (sum4 3000000 id): Успешно, примерно на 50% больше, чем sum1
• main = print (sum [1 .. 3000000]): переполнение стека, выделение примерно на 80% больше, чем sum1
• main = print (foldl' (+) 0 [1 .. 3000000]): успех, почти без выделения

Так что это в основном то, что вы ожидали, за исключением того, почему seq делает такую ​​разницу между sum1 против sum5.