Hacker News Reader

Comment by psykotic | Hacker News Reader

Happy fun time:

    pascal = iterate (\xs -> zipWith (+) ([0] ++ xs) (xs ++ [0])) [1]

Bread and butter:

    void pascal(int n, int *buf)
    {
        for (int row = 0; row < n; row++) {
            for (int prev = 0, col = 0; col < row; col++) {
                int curr = buf[col];
                buf[col] += prev;
                prev = curr;
            }
            buf[row] = 1;
        }
    }

View on HN

I like both of those solutions. The Haskell solution is almost the same as what I had come up with but I wasn't familiar with iterate, which makes it even nicer. So thanks for that.

Looking at the C version, I wondered if it could be done without temporaries curr and prev. My no-temporaries version is not really any nicer, though it does shave off a few lines. :P

    void pascal(int n, int *buf)
    {
        for (int i = 0; i < n; i++) {
            buf[i] = 1;
            for (int j = i - 1; j > 0; j--)
                buf[j] += buf[j - 1];
        }
    }

Yeah, that works. My left-to-right traversal would be also a little nicer if C had parallel assignments as in Python:

    for i in range(n):
        p = 0
        for j in range(i):
            buf[j], p = buf[j] + p, buf[j]
        buf[i] = 1

Of course, you can also do this in C with a riff on the old in-place swap trick, e.g. buf[j] = buf[j] + p, p = buf[j] - p, but that's too clever by half, albeit kind of cool.

F# doesn't have an in-built iterate function, but found an equivalent on the F# Snippets site -- http://fssnip.net/18.

    let rec iterate f value = seq {
        yield value
        yield! iterate f (f value) }

Using the above we get ...

    let pascal = iterate (fun xs -> List.map2 (+) (0::xs) (xs @ [0])) [1]

Reply on news.ycombinator.com