Hacker News Reader

Comment by jrockway | Hacker News Reader

Guido is exactly right. reduce is one line of code, not "a few" lines of code.

The Haskell 98 Report takes two lines:

    foldr f z []     =  z
    foldr f z (x:xs) =  f x (foldr f z xs)

Clojure does it like this (note the overloading - this is both "foldl" and "foldl1" in Haskell terms): http://github.com/richhickey/clojure/blob/49a7d6b8e14050a45d...

To be true, it's customary that you also add a line for the types in Haskell. Though not necessary.

Couldn't we do this?

r' f (x:xs) | xs == [] = (f x):[] | otherwise = (f x):(r' f xs)

or:

[(f a) | a <- myList]

- another edit -

r' f (x:xs) | xs == [] = x | otherwise = f x (r' f xs)

That's map, not reduce.

SICP defines fold-right in 5 lines, so I'd rather say he's just wrong.

Well, to be really fair, most of the people I've seen trying to prove him wrong ended up implementing it as, basically, "let my_reduce = reduce", or something similar but obfuscated enough to make it not look completely tautologous. Which is really the point: a lot of the modern FP languages make folds and other similar constructs so fundamental to the language ("primitives" in terms of the quote) that it can be difficult -- either due to mindset or due to the language itself getting in the way -- to drop down a level or two on the abstraction ladder and try different approaches.

(and the fact that everybody who hasn't implemented a tautologous reduce has basically used the same tail-recursive algorithm lends a bit more support to this theory)

The more I think about it, it's just another expression of the old "when all you have is a hammer" aphorism. Guido's being yelled at and called names not because he's wrong or because he's stupid or doesn't understand what he's talking about, he's being yelled at and called names because the "hammer" in this case -- functional programming -- is a bit of a sacred cow, and a lot of people get really defensive about it.

Fold/reduce is not a primitive in Clojure, Erlang, Haskell, SML, Mercury, or any other functional language I know (though it is a standard library function in all of them). Do you have any counter-examples?

Of course all functional programmers write the same tail-recursive implementation of "reduce." That's like observing that everyone uses a loop to implement "reduce" in an imperative language. It's the simple, straightforward way to do it. (And since folds are trivially implemented in any functional language with tail recursion, why would the language designer include them as a primitive?)

I took "primitive" to mean not only language syntax, but built-in functions which are so fundamental to programming in a given language that it's difficult to escape them. For, say, Haskell, that's quite true of folds.

I don't think it's true in Haskell at all. A fold is just walking a list with an accumulator. That's not weird or low-level; it's as common for Haskell programmers as loops and variables for C programmers. It actually took me a while (when first learning SML and Scheme) to realize I could use the built-in reduce functions more, instead of writing loops "by hand" all the time.

It's also very common in Haskell to implement your own fold for various reasons. For example, in a simple 50-line text processing script[1], I defined a fold for a list-of-trees data structure without calling any builtin fold function[2].

[1]: http://github.com/mbrubeck/outline-grep

[2]: http://github.com/mbrubeck/outline-grep/blob/master/OutlineG...

P.S. I like your blog, and huge thanks for Django!

Actually, a fold is walking a Foldable with an accumulator :)

Reply on news.ycombinator.com