[Haskell-cafe] laziness blowup exercise

[Bas van Dijk]

On Thu, Jul 16, 2009 at 9:57 PM, Ryan Ingram<ryani.spam at gmail.com> wrote:
>> On Thu, Jul 16, 2009 at 8:22 PM, Thomas Hartman<tphyahoo at gmail.com> wrote:
>>> Is this being worked on?
>
> On Thu, Jul 16, 2009 at 12:35 PM, Bas van Dijk<v.dijk.bas at gmail.com> wrote:
>> I have no idea.
>
> Yes.
>
> Bolingbroke, Peyton-Jones.  "Types are calling conventions"
> http://lambda-the-ultimate.org/node/3319

Thanks for the pointer to this interesting paper!

However I dont't think that the type system explained in that paper is
powerful enough to differentiate between these different iterates:

iterate1, iterate2, iterate3, iterate4 :: (a -> a) -> a -> [a]

iterate1 f x = x : let nxt = f x
                   in iterate1 f nxt

iterate2 f x = let nxt = f x
               in nxt `seq` x : iterate2 f nxt

iterate3 f x = x `seq` x : let nxt = f x
                           in iterate3 f nxt

iterate4 f x = x : let nxt = f x
                   in nxt `seq` iterate4 f nxt

The type system somehow has to express the growing and shrinking of
the stack so that it can statically disallow:

iterate1 (+ 1) 0 !! (10^6) :: Int & <fits in my stack>

and allow:

iterate4 (+ 1) 0 !! (10^6) :: Int & <fits in my stack>

Bas