Как рассуждать о сложности пространства в Haskell

Я ' m пытается найти формальный способ думать о сложности пространства в haskell. Я нашел эту статью о технике редукции графов ( GR ), которая мне кажется подходящей. Но в некоторых случаях у меня возникают проблемы с его применением. Рассмотрим следующий пример:

Допустим, у нас есть двоичное дерево:

data Tree = Node [Tree] | Leaf [Int]

makeTree :: Int -> Tree
makeTree 0 = Leaf [0..99]
makeTree n = Node [ makeTree (n - 1)
                  , makeTree (n - 1) ]

и две функции, которые проходят по дереву, одна ( count1 ), которая хорошо передает поток, а другая ( count2 ), создающий сразу все дерево в памяти; согласно профилировщику.

count1 :: Tree -> Int
count1 (Node xs) = 1 + sum (map count1 xs)
count1 (Leaf xs) = length xs

-- The r parameter should point to the root node to act as a retainer.
count2 :: Tree -> Tree -> Int
count2 r (Node xs) = 1 + sum (map (count2 r) xs)
count2 r (Leaf xs) = length xs

Я думаю, что понимаю, как это работает в случае count1 , вот что, я думаю, происходит с точки зрения сокращения графа:

count1 $ makeTree 2
=> 1 + sum $ map count1 xs
=> 1 + sum $ count1 x1 : map count1 xs
=> 1 + count1 x1                                + (sum $ map count1 xs)
=> 1 + (1 + sum $ map count1 x1)                + (sum $ map count1 xs)
=> 1 + (1 + sum $ (count1 x11) : map count1 x1) + (sum $ map count1 xs)
=> 1 + (1 + count1 x11 + sum $ map count1 x1)   + (sum $ map count1 xs)
=> 1 + (1 + count1 x11 + sum $ map count1 x1)   + (sum $ map count1 xs)
=> 1 + (1 + 100 + sum $ map count1 x1)          + (sum $ map count1 xs)
=> 1 + (1 + 100 + count x12)                    + (sum $ map count1 xs)
=> 1 + (1 + 100 + 100)                          + (sum $ map count1 xs)
=> 202                                          + (sum $ map count1 xs)
=> ...

Я думаю, из последовательности ясно, что он работает в постоянном пространстве, но что меняется в случае count2 ?

Я понимаю интеллектуальные указатели на других языках, поэтому смутно понимаю, что дополнительный параметр r в функции count2 каким-то образом сохраняет узлы дерева от разрушения, но я хотел бы знать точный механизм, или хотя бы формальный механизм, который я мог бы использовать и в других случаях.

Спасибо за внимание.