Pinned memory doesn't play a role here.
This program:
main = print $ sum $ tail ([1..100000000] :: [Int])
does not use any pinned memory directly. The pinned memory you're seeing is from the initialization of the runtime system itself. Pinned memory is allocated by GHC's byte array primitives; in user code, you're most likely to see pinned memory usage when using Data.Text or Data.ByteString both of which use byte arrays for their internal implementation. For this program, I'm going to guess that the I/O buffers for stdin and stdout are pinned, but maybe it's something else. Anyway, lists of Ints won't pin anything.
Like (almost) all Haskell programs, Pinned1.hs uses tons of heap and tons of stack (gigabytes of each) but, critically, frees it as quickly as it allocates it (or if you prefer when talking about the stack, "pops" it as quickly as it "pushes" it). The same is true of Pinned2.hs. These programs are functioning correctly.
The problem with Pinned3.hs is not that it uses stack instead of pinned memory, but rather that it uses even more stack than Pinned1 and Pinned2 and fails to pop it as quickly as it pushes it, so stack accumulates.
So, why does Pinned3 accumulate stack?
Generally speaking, stack accumulates in a recursive call if some part of the result of the recursive call is the target of a function application when it returns AND evaluating that part of the result itself requires another recursive call. Consider the program:
eatStack 100000000 = 1
eatStack n = 1 + eatStack (n + 1)
main = print $ eatStack 1
which, compiled and run with:
stack ghc -- -O2 -prof -rtsopts EatStack.hs
./EatStack +RTS -hd -p -xt
stack exec hp2ps -- -e8in -c EatStack.hp
produces the usual sort of pyramid-shaped stack accumulation (with a peak of 1.4G or so). The problem here is that the return value of the recursive eatStack (n+1) call is subject to the function application \x -> 1 + x when it returns, and calculating that result itself requires further recursion. That is, calculating eatStack 0 requires pushing \x -> 1 + x onto the stack before calling eatStack 1 which can only return its result after pushing \x -> 1 + x onto the stack before calling eatStack 2, and so on. The result is stack accumulation.
Notably, constructor applications are handled differently. The following program:
noStack 100000000 = []
noStack n = 1 : noStack (n + 1)
main = print $ last (noStack 1)
which applies the partially applied constructor (:) 1 to the recursive result noStack (n+1) uses no stack. (It appears to use 40k of pinned, but again that's really the runtime system. EatStack uses 40k of pinned, too.) In some cases (not here), constructor application like this can cause heap accumulation, but it doesn't generally accumulate stack.
For your Pinned2 and Pinned3 examples, something similar is going on, though it's obviously a little more complicated. Let's look at Pinned2 first, and consider evaluating wgoC 1 0. Matching the case and substituting in the arguments, the evaluation is equivalent to:
wgoC 1 0 =
let (nxt, ys') = wgoC 2 0
in (1, 1 + nxt * 9 : ys')
When sum . snd demands the first element of the list, namely the thunk 1 + nxt * 9, this forces nxt to be evaluated via the recursive call. Because this return value is subject to a function application (namely \x -> 1 + x * 9), this uses a bit of stack, but the evaluation of the recursive call:
wgoC 2 0 =
let (nxt, ys') = wgoC 3 0
in (2, 2 + nxt * 9 : ys')
immediately yields the required value for the locally bound nxt in the wgoC 1 0 call, namely the first element of the returned tuple fst (wgoC 2 0) = 2, without requiring further recursion. So, we take that value 2, pop off the continuation \x -> 1 + x * 9 and pass the value to the continuation to yield 1 + 2 * 9 = 19. That gives the list's first element, with no net stack usage. The rest of the list, namely the locally bound ys' in the wgoC 1 0 call, is still in a thunk 2 + nxt * 9 : ys' as closed by the wgoC 2 0 call.
When the next element is demanded, we'll need some stack to apply the continuation \x -> 2 + x * 9 to the result nxt in the recursive (nxt, ys') = wgoC 3 0, but this will be evaluated the same way, immediately returning nxt = 3 and a thunk for ys', so the continuation \x -> 2 + x * 9 will be popped off the stack and applied to nxt = 3 without further recursion, yielding 2 + 3 * 9 = 29 and a thunk 3 + nxt * 9 : ys' as closed by the wgoC 3 0 call.
Each element can be forced with no net stack use. We push a continuation and then immediately pop it and apply it to a part of the return value from the recursive call that doesn't itself require further recursion. The result is no net stack accumulation.
Now, consider Pinned3, and the call wgoD 1 0:
wgoD 1 0 =
let (ttl', ys') = wgoD 2 0
in (ttl' + 1, 1 + (ttl' + 1) * 9 : ys')
When sum . snd demands the first element of the list, namely the thunk 1 + (ttl' + 1) * 9, this forces ttl' to be evaluated via the recursive call. Because there's a pending function application \x -> 1 + (ttl' + 1) * 9, this will use a bit of stack. The recursive call:
wgoD 2 0 =
let (ttl', ys') = wgoD 3 0
in (ttl' + 2, 2 + (ttl' + 2) * 9 : ys')
can only provide the required value for the locally bound ttl' in the wgoC 1 0 call by evaluating the first component of the return tuple ttl' + 2, but this requires forcing ttl' via the recursive wgoD 3 0 call. Because ttl' is subject to a function application \x -> x + 2 when it returns, we push a little more stack and proceed to evaluate:
wgoD 3 0 =
let (ttl', ys') = wgoD 4 0
in (ttl' + 3, 3 + (ttl' + 3) * 9 : ys')
To get the required ttl' as locally bound in the wgoD 2 0 call, we need to evaluate the first component of return tuple from wgoD 3 0, namely ttl' + 3. This is a function application \x -> x + 3 which we push on the stack, applied to ttl' returned from the recursive call wgoD 4 0.
So, Pinned3 pushes a sequence of continuations \x -> x + 2, \x -> x + 3, \x -> x + 4', etc. onto the stack, all in an effort to evaluate the first component of the tuple returned by wgoD 2 0, never getting an opportunity to pop anything until it gets to wgoD 100000000 0, and then it finally gets a number finalState = 0 as the first tuple component, if there's enough stack to get that far. Then all that stack will be popped off as the continuations are applied, and we'll have the first element of the list!
Once it gets through that, things aren't so bad. All of the expressions ttl' + n have been evaluated at this point, and they can be reused in calculating the expressions n + (ttl' + n) * 9, so the remaining elements can be generated relatively quickly, though -- since their values must be kept somewhere -- you'll also get accumulating heap usage at roughly the same rate as stack usage.
You can swap out the 100000000 for something like 10000000 (seven zeros), and that runs in a reasonable amount of time and shows accumulation of both stack and heap in a pyramid shape; it peaks at 1.4 gigs or so before dropping back down to zero.
I don't see any really straightforward way of "fixing" this while still keeping the algorithmic structure of Pinned3 intact.
