Hacker News new | ask | show | jobs
by icarot 4232 days ago
Thanks so much for that paper. That'll save me time thinking about transforming functions on my own.

Are you sure they make that optimization? How do you know? (I'm not familiar with either code base).

Are you absolutely sure that example is O(1)? It looks O(n) to me. I'm not experienced in Haskell, by the way: disclaimer.

Each call to 'fibs' constructs a list with its first argument and the recursive call. But for all of the recursions (aka, 2nd element and on) I think they'll have to build up deferred cons operations. I'm not sure about this at all. I sound suspicious, I know, but before you say anything, look here: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...

don't they look suspiciously similiar? In that example, you'd have needed to store a function pointer and the argument'(s) type(s) for each call, on the stack, making space usage O(n). Each call pushes to the stack.

Does the Haskell example seem similar to you? I'm really uncertain.
1 comments
wyager 4232 days ago
>Are you sure they make that optimization? How do you know?

Yeah, if you write a tail-call recursive fib function and turn on optimizations, the optimizer should definitely loop-ify it.

I tested this a while back on my machine. Writing C and compiling with LLVM yielded a 5-instruction loop, and writing tail-call recursive, strict (not WHNF-recursive) Haskell with optimizations on yielded a 4-instruction loop. Both were very fast. You can look at the generated assembly with a variety of tools. I used Apple's profiler tools.

>Each call to 'fibs' constructs a list with its first argument and the recursive call. But for all of the recursions (aka, 2nd element and on) I think they'll have to build up deferred cons operations.

Correct. If you saved the list, it would be O(n). However, since you throw away the head of the list and move on to the next element immediately (if you want the nth fib number), the garbage collector will get rid of all the generated list elements, so the space consumption is only the list element you want (or are looking at currently), so it's O(1).

It might look like this, in pseudo-code.

    def fibn(n){
        (curr, nextGenerator)=fibs(0, 1);
        for(i=0; i<n; i++){
            (curr, nextGenerator) = nextGenerator();
        }
        return curr;
    }
Since the rest of the list is passed as an unevaluated function, you only need to keep track of two things at once: the head of the list (in case it's the correct element) and the function to make the rest of the list.

Also, Haskell doesn't really use the stack like a lot of other languages do. That's why you can have infinitely recursive functions without running out of space. It accomplishes this using the technique I put in that loop up there: passing values around as unevaluated functions.

(Side note: Haskell doesn't keep track of types at runtime. The compiler erases any type information before compilation, and tries to eliminate any dynamic function lookup. As long as the types match up during compile time, they will match up during runtime.)

link