I, personally, like yours better, but I don't really use best.
Note, though, that you're changing the behavior of the function in two ways:
1. nil is not returned when passed an empty list. I notice arc code does this often with the expectation that when composing your functions you may iterate though many lists to assemble them. So assembling with empty lists will break with your new function:
old > (best > '())
nil
new> (best > '())
Error: "procedure best2: expects 2 arguments, given 0"
2. arc's current best return the first item of the two when the compare function fails, where with yours it's the opposite, and if none of them pass, arc's current one will return the first item, yours will return the last.
old > (best (fn (x y)(> (+ x y) 10)) '(3 2 2 1 1 1))
3
new > (best (fn (x y)(> (+ x y) 10)) '(3 2 2 1 1 1))
1
I'm not sure if this matters, since I have not checked where & what 'best' is actually used for. I'm just noting that you're changing the behavior quite a bit.
#2 is the old foldl vs foldr conundrum[1]: http://en.wikipedia.org/wiki/Fold_%28higher-order_function%2.... I think it's irrelevant which fold you use for best because the answer will only diverge if all the elements in the list are 'equal' according to the metric. Your example is like that.
Then again, you could argue that the original behavior is more 'stable': it's like sorting the list and taking the first element.
[1] Rich Hickey recently called fold/reduce 'complex' because of the variants. http://arclanguage.org/item?id=15269; I didn't expect to be able to cite it so soon :)
"I think it's irrelevant which fold you use for best because the answer will only diverge if all the elements in the list are 'equal' according to the metric."
If anyone called 'best on an infinite list, I'd expect it to diverge regardless of how it was implemented. You never know if something's the maximal/minimal element unless you've checked all the others.
(If 'best operated on heaps or something, then you might be able to say "this potentially infinite substructure has no better candidates" because the heap structure makes guarantees like that.)
Anyway, #2 is still irrelevant because it's trivial to fix:
(def best (f seq)
(reduce (fn (a x)
- (if (f a x) a x))
+ (if (f x a) x a))
seq))
Even if we used 'rreduce instead of 'reduce here, this fix would still be necessary (if we consider #2 important to fix at all).
Here's a fix for #1 as well, along with a return to the original variable names:
This still leaves one inconsistency with the original: This version behaves more intuitively in the presence of continuations, because it doesn't use mutation.
"If anyone called 'best on an infinite list, I'd expect it to diverge regardless of how it was implemented."
Oops, I didn't consider that 'best in Arc actually does operate on a data structure that has enough information to tell you whether an infinite substructure can contain a better candidate: If any tail of the list is 'is to one of the tails you've already encountered, its length is infinite but it certainly has no better candidates (since you've already seen them all). All infinite lists in Arc have tails that contain themselves as tails, so it's possible to make an Arc 'best that terminates on any infinite list.
"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.
He wasn't talking about "consistency" in the sense of the principle of least astonishment.
If two parts of the program observe the system at the same time but see different states, that's called inconsistency. Consistency is difficult to achieve in a distributed program, thanks to the fact that "observation" isn't necessarily instantaneous or reliable. Per the CAP theorem (http://en.wikipedia.org/wiki/CAP_theorem), to achieve full consistency in a distributed program you have to sacrifice availability or partition tolerance. These three properties are inherently complected.
A popular sacrifice is to only guarantee a sort of eventual consistency (http://en.wikipedia.org/wiki/Eventual_consistency). That is, for any given state of the system, given enough time to communicate, every part of the system will catch up to that state. It's like saying that a garbage-collected program eventually releases memory.
I think you're over analyzing. Although "consistency" in the general sense, was not the only thing he was talking about... it was obvious he was including that, he even dumbed it down to that point within his presentation.
Things that are consistent are simpler than things that are not.
And I do feel that way about arc code. Having half your functions accounting for nil, while ignoring it for the other half, would make coding in arc less simple, than making sure they all accounted for it (as a general statement without debating the specifics).
Sure, I agree he was talking about that kind of consistency too. I spoke too matter-of-factly for once. ^_^
I was more specifically referring to the part at 31:17 where he had Inconsistency vs. Consistency on the slide and he explained the complexity as "taking a set of things that stand apart and trying to think of them all at the same time." He finished that line of thought with "And anybody who's tried to use a system that's eventually consistent knows that."
(Note that he's talking about eventual consistency as being on the "Inconsistency" side, which I guess is because an eventually consistent system is often on the way to consistency rather than being there.)
I wouldn't assume something is incidental unless the purpose has been researched. And, I believe, its correctness can only be determined by its intended use... Which is why I was kinda suggesting someone check where and why it's actually used.
As a guess, 'best' is probably used for http://arclanguage.org/best
in the news.arc code. In which case it's probably not an issue... ?
At any rate, references should probably be checked? Or maybe, instead, news.arc code should be dropped from anarki? Could it be that supporting news.arc only stifles arc's development?
I think supporting anything stifles development. It's a contradiction I just try to accept. :-p
I don't see the purpose of 'best. I don't see a bigger purpose in most of Arc. If what Arc gives me isn't what I need, I reinvent it.
(In fact, I think if we try to keep working on the same language, rather than tearing it down and reinventing it, we're worrying about at least some kind of "support" and stifling our development. But too much tearing down can be destructive too, of course. :-p I appreciate that you're applying a scientific-ish mindset to this.)
There are a few ways to cut through this Arc ennui:
- If Arc gives me tools I can use to reinvent things, those tools are extra-relevant, since even if I don't like them I'll use them on my way to replacing them. This is not something 'best does for me.
- Sometimes we may want everyone in the language community to use the same variant of something, so that the tools we build around that thing can work together. Are we trying to optimize 'best in the compiler/runtime? Nope. Do people often extend 'best with extra capabilities? Nope. Even if these things were true, are we even having an issue with people reinventing 'best all the time? Nope, I don't think so.
I agree with everything you're saying... and, also, in thinking about it further, I believe that having namespaces as a first class feature is the best way to solve this kinda problem.
For example, in Clojure, I can just build my project by excluding the function in question and replace it with my version. Anyone else that wants to use Clojure doesn't need to worry about another persons great idea.
; example
(ns a-project.core
(:refer-clojure :exclude (best))
(:gen-class))
(defn best []
...)
And anyone else wanting to use my library and/or only use my version can do so, simply:
But I don't even really want 'reduce. If the function is '+, an empty list should give 0. If the function is '*, an empty list should give 1. Instead of trying to divine this value from nowhere, I think it makes more sense to pass the base case manually, as with 'foldl.
