Hacker News Reader

Comment by jwdunne | Hacker News Reader

Oh wow, thanks! I should have also noted I have no experience with the language in the examples so please ignore any ignorance there (probably should have read up on it).

Interesting! All well noted and I'll look into this more.

I'm vaguely aware of fold's power and can definitely see how filter, map and the likes would be implemented in terms of it but I would be really interested in the infodump!

I'm just wondering, ignoring laziness and typing (or any language-specifics), if foldl could be written similar to (2)? Obviously it wouldn't be very good. I've written an example in Racket of what I have in mind:

  (define (foldl fn initial lst)
    (if (null? lst) 
        initial
        (fn (car lst) (foldl fn initial (cdr lst)))))

  (define (fac n)
    (if (= n 0)
        1
        (* n (fac (- n 1)))))

  (= (fac 3)
     (foldl * 1 '(1 2 3)))

Thanks again for the info, really appreciated. :)

View on HN

Actually, what you have written is not foldl, it's foldr. Why is it going right to left? Let's expand your example:

    (foldl * 1 '(1 2 3))
    (* 1 (foldl * 1 '(2 3))
    (* 1 (* 2 (foldl * 1 '(3))))
    (* 1 (* 2 (* 3 (foldl 1 '()))))
    (* 1 (* 2 (* 3 1)))
    ...
    6

Basically, the calls to * start nesting into each other, so the one that actually gets evaluated first is the rightmost one.

What would actually be foldl is this:

    (define (foldl fn accum lst)
       (if (null? lst)
            accum
            (foldl (fn accum (car lst)) (cdr lst))
       )
    )

Now if you expand this (dropping the tail recursion):

    (foldl * 1 '(1 2 3))
    (foldl * 1 '(2 3))
    (foldl * 2 '(3))
    (foldl * 6 '())
    6

And even though you think that such a tiny thing can't be a good implementations, it actually is super efficient. The tail recursion is automatically optimized for you (and you can assume that for any functional language - it's a very crucial optimization for this style of code, after all). That's what the core of it will be in an actual implementation, though with added error handling, type checking and so on.

P.S. unlike haskell, in Racket you don't really need to fold the basic operators, they take variable arguments, so you can just:

    (apply * (list 1 2 3))

in order to get it to run on a list.

Ivo's answered so I'll just say the main trick to turning a function tail recursive is to have the function lug its state around. So always look to see if you can rewrite your function so it passes the current value explicitly to the next iteration. Non tail recursion is like winding a spring and then having it unwind, a jack in a box. Tail recursion is like a snowball rolling down a hill. You should always try to make a recursive function tail recursive if you can.

As for fold it's a bit involved and has a lot of scary sounding jargon on the way to understanding it. You can write a fold for a tree and then code depth first search in a couple lines. Folds follow some basic properties that allow for program derivation. I rarely use those but it does inform my programming. It's kind of like how knowing Lisp informs your python. There is also an opposite or dual to fold called unfold. You can write many algorithms efficiently just using fold and unfold and a couple techniques to prune inefficiencies. Fold is the same kind of object to your initial tree as say a matrix is to a vector, or a derivative is to a polynomial.

Also ignoring tail recursion for the purpose of the above piece of code, haha.

Reply on news.ycombinator.com