"Rich Hickey recently called fold/reduce 'complex' because of the variants."
Because of the variants? The only mention of fold I found was this one:
Rich Hickey (at 30:33): "Imperative loops--fold, even, which seems kinda higher-level? Still has some implications that tie two things together... whereas set functions are simple."
I thought he was referring to the way the calls to the folded function are all lined up in a dependency chain, just like they'd be lined up if you were using an iterative loop.
(state before the iteration, input to this iteration)
-> state after the iteration
To illustrate, in a procedural language, it's easy and efficient to define a left fold as an iterative loop:
(def foldl (first rest func)
(ret result first
(each elem rest
(zap func result elem))))
This is the same as the 'best change we're talking about. But since Arc's continuations make more sense when there's no mutation going on, I recommend not implementing 'foldl and 'best this way.
With "set functions," you can determine certain properties about the result if you know some subsets' results:
- The result of (some odd (join '(17) foo)) is t, because (some odd '(17)) is t.
- The result of (keep odd (join '(17) foo)) has at least the element 17 in it, because (keep odd '(17)) has that element in it.
Rich Hickey's main point is that these "simple to reason about" properties help humans. But they also mean that if we know enough about these function calls statically (which we never do, in Arc), we might be able to turn them into constants without knowing the value of 'foo, or at least we might be able to parallelize them. These set functions may be implemented as special cases of fold, but fold doesn't have the same reasoning potential in the general case.
Instead of saying "you can compile it better," Rich Hickey would probably spin this as "you can leave the 'how' up to the language implementor."
"Loops and fold! Loops are pretty obviously complecting what you're doing and how to do it. Fold is a little bit more subtle, 'cause it seems like this nice 'somebody else is taking care of it,' but it does have this implication about the order of things. This left-to-right bit."
I can see how you'd get that. I think our interpretations are related. As far as how they're related goes...
The underlying issue may be that introducing non-commutativity makes an operation more cumbersome when used with sets, and introducing non-associativity makes it even worse.
- Commutative and associative: If you apply '* or 'max pairwise to a set, you can only get one result. (It's possible to implement 'some this way, and a 'keep that returns an unordered bag.)
- Associative: If you apply 'compose or 'join pairwise to a set, you can get many results, but you can choose between them by putting the items in a list. (It's possible to implement 'keep this way.)
- Commutative: If you apply XOR pairwise to a set, you can get many results, but you can choose between them by placing the items on the leaves of a rooted binary tree.
- Neither: If you apply 'cons pairwise to a set, you can get many results, but you can choose between them by placing them on the leaves of a rooted binary tree with a distinction between left children and right children.
Both 'foldl and 'foldr are specific enough to be deterministic when they're used with non-associative, non-commutative operations like 'cons. The fact that they're so specific is why there isn't just one 'fold.
I was intentionally avoiding 'is as an example, since it has an intuitive meaning when applied to a set (IMO), which is different from applying it piecewise.
