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 -~----------~----~----~----~------~----~------~--~---
