this may be a silly argument, but: (list? '()) returns true
(list? nil) returns false (list? 'nil) returns false. I don't even know what it means. therefore nil isn't a list. Then again, I already chimed in. a list isn't a set. You said so in the introduction. Maybe set's need there own print representation, like <> ..... uh oh, starting to look like C++ That or find the unicode character for the zero with the line through it. On Sat, Jan 24, 2009 at 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). > 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. > > 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. > > 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 have seen Rich's talk in which he explains that he chose to not have > an empty sequence because which empty sequence should it be? Empty > list? Empty vector? Why should one empty object be privileged? But > this reasoning never resonated with me. Sequences and lists have a > special connection. Sequences are intended to be a list-like > interface. So any sequence-producing function produces either a > concrete list, or something that looks, feels, and tastes like a list. > I've already gotten used to seeing (rest [1 2 3]) producing (2 3) in > the REPL (even though technically it's producing something list-like > and not actually producing a list). So to me, it would be perfectly > natural to see (rest [1]) producing (). () could reasonably serve as > both the empty list and the empty sequence since lists and sequences > are so closely related. > > I assume that a design decision as fundamental as the choice to have > no empty sequence is probably set in stone at this point, so I think > it's safe to assume that this dilemma is here to stay. At the moment, > I intend to advocate the use of nil over () as the closest surrogate > for an empty sequence. Clojure is designed to not give one empty > collection privileged status, so putting () inside a sequence of > sequences feels more wrong to me. Furthermore, including nil is often > more practical to code. None of Clojure's built-ins actually return > (), so it's only feasible to have () represent the empty sequence if > it's the result of a separately-coded base case. For many algorithms > where the sequence is produced by mapping a function over a bunch of > values, or by 'rest'ing a sequence until reaching empty, the algorithm > will most naturally include nil in the sequence. So for consistency, > it's probably better to always choose nil over () in sequences of > sequences. > > Anyone want to try to convince me otherwise? If you think my logic is > flawed, I'd love to hear your take on this problem. > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
