On Jan 24, 3:43 am, Mark Engelberg <mark.engelb...@gmail.com> wrote:
> Now that everyone's had a day to mull this puzzle over, here are my thoughts.
>
> One way to think about this, is to think about what the statement of
> purpose / contract of a generalized powerset function would be. In
> general, most functions on seq-able objects return sequences. For
> example, (rest [1 2 3]) yields (2 3). So we'd want to make powerset
> consistent with Clojure's general behavior. Also, like most Clojure
> core functions, we'd expect sequences in the output to be lazy. I
> think there are two basic lines of reasoning:
>
> 1. The most straightforward generalization is:
> The powerset of a seq-able S is the (lazy) sequence of all (lazy)
> subsequences of (seq S).
This is already wrong, right? Don't you mean (set s)? You haven't said
what (powerset [1 2 3 2 1]) is going to be. subsequences != subsets.
> Thinking in this vein, you might figure that
> (powerset [1 2 3]) should be (nil (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3)).
> One way to rationalize it is that we really need to have an empty
> sequence in the sequence of answers, but there is no such thing as an
> empty sequence, so we must use nil.
> But the obvious flaw here is that this output violates our contract.
> We said we'd generate a sequence of sequences, but (seq? nil) is
> false.
> nil is not the empty sequence, nor is it a sequence at all, so
> we haven't accurately captured the function's intention with this
> output.
>
> 2. So one way to try to "fix" this problem is to put a concrete empty
> object in the output sequence. Since sequences are inspired by lists,
> perhaps it makes sense to replace the nil with the empty list (). So,
> (powerset [1 2 3]) yields (() (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3)).
> But this has problems as well. First, even though the result prints
> as a list of lists, it is important to remember that these things are
> not lists, but sequences derived from vectors (since the input is a
> vector in our example). For example, (cons 1 [2 3]) prints as (1 2
> 3), but (list? (cons 1 [2 3])) is false.
> So it's difficult to even imagine what the contract would be for such
> a function. Perhaps, "The powerset of a seq-able S is the (lazy)
> sequence of the empty list and all the (lazy) subsequences of (seq
> S)." would be one way to word the statement of purpose. But if the
> input is a vector, it seems really odd to see an empty list in the
> output. Why a list?
>
> So I think that the answer is that there is no good answer. We really
> need an empty sequence here, and Clojure doesn't have such a notion.
That doesn't follow.
Basically it's not hard to make a promise and behavior that match if
you don't keep trying to redefine what sequence means. You've said
you'd generate sequences but haven't defined what they are (in your
mind), then criticize as if they were logical flaws problems with your
formulations that have more to do with terminology mismatches than
logic.
You gotten tied up, here and elsewhere, conflating sequence with
container, and almost all of your problems stem from wanting to say
sequence and have it mean container. If you want to put the contents
of a (possibly empty) set into a sequential container, use a
sequential container - () or []. The sequential? predicate will cover
both of those as well as lazy sequences of set contents.
seq? tests if something implements ISeq, no more, no less - it is not
the defining predicate of sequence. Is that what you want to promise?
Or do you want to promise you'll return something on which (seq x)
works? It works for nil and () and [], and the user wouldn't look for
any one specifically.
Or do you want to promise that it returns the result of seq. It is
this notion that is most commonly meant by sequence in Clojure,
whether you like it or not.
Hmmm...
(defn sequence? [x] (or (nil? x) (seq? x)))
Take your pick, they all could work.
Most important, why promise more than you need to?
What you can't do is say - look, I promised sequence but it's broken
because (seq? nil) -> false.
>
> Clojure's choice to not have an empty sequence doesn't really cause
> any inconvenience when dealing with flat sequences, but I have found
> that it results in these sorts of dilemmas almost any time you deal
> with sequences of sequences. In discussions about generating a
> sequence of all permutations, all combinations, etc., you inevitably
> end up with arguments over issues like what (permutations nil) should
> be (some say (nil), some say (()), and some say nil). If you have an
> empty sequence, these issues go away.
>
Really? Don't you still have a problem with "some say (empty-seq),
some say empty-seq" - why would that be different?
> So ultimately, you just have to make a choice between nil and () and
> go with it. It all comes down to a gut feeling about which one is a
> better stand-in for the notion of an empty sequence, even though
> neither one truly is the empty sequence. In practice, it doesn't seem
> to matter too much which choice you make. nil and () are almost
> entirely interchangeable.
> (cons 1 nil) is the actual concrete list (1), just as (cons 1 '()) is.
> (conj nil 1) is the same as (conj '() 1)
> (first nil) and (first '()) both yield nil.
> (rest nil) and (rest '()) both yield nil.
> (empty? nil) and (empty? '()) both yield true
> (seq nil) and (seq '()) both yield nil.
>
> There are certainly a few differences, of course. nil and '() respond
> differently to nil?, list? and not, for example. But I haven't found
> these sorts of tests to be common in code operating on nested
> sequences.
>
> Even though it doesn't make a huge difference, the lack of a clearcut
> correct choice means that people will make different choices in
> different codebases, which could prove problematic.
>
I don't see how this follows from "In practice, it doesn't seem to
matter" and "I haven't found these sorts of tests to be common". In
practice it doesn't matter, as people just call (seq x) on it and get
on with their lives.
I'm not arguing against a convention here, and am amenable to your
argument about the practicality of nil, which is covered by the
promises "something on which (seq x) works" and "the result of seq".
It is only when code overpromises re: types etc that consumers become
brittle as they marry implementation details, i.e., even if you return
embedded nils, don't promise embedded nils.
Rich
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to clojure@googlegroups.com
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
