Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I think I have correctly implemented Powerset in Clojure.

(use '(clojure set))

(defn powerset [input result]
  (if (nil? (first input))
    (concat result #{})
    (set (reduce concat
           (for [x input]
             (let [set-of-x #{x}
                   input-no-x (set (remove set-of-x input))
                   next-result (union result (set (list input set-of-x input-no-x)))]
               (powerset input-no-x next-result)))))))

Of course I'm interested in how a library function could make the above a one-liner, but I'm also interested in how the above code could be made more idiomatic.

  1. (if (nil? (first input)) feels wrong.
  2. Using the let block to replicate imperative calculations. Acceptable?
  3. Could I use ->> to make the following line more readable? (union result (set (list input set-of-x input-no-x)))
  4. I'm not using recur as I got the "recur must be in the tail position" compiler error.

EDIT Removed (loop) from originally-posted version. - I had erroneously copy-pasted code after I had already commenced attempting to introduce loop/recur (tail recursion). How use loop/recur in this function?

share|improve this question
    
Feedback from @stevelknievel on twitter: use if-let –  noahz Jun 24 '12 at 3:36
1  
Library that does the job: math.combinatorics/subsets –  skuro Jun 24 '12 at 7:45
    
And it's part of Clojure Contrib. –  noahz Jun 25 '12 at 14:55

2 Answers 2

up vote 3 down vote accepted

A couple of random comments on your code:

  • it doesn't parse correctly, I guess the closed paren right after loop bindings is misplaced. I couldn't run it even after fixing that.

  • why do you need a second input parameter? I would expect the signature to only have the input set as parameter

  • (if (nil (first input)) then else) is more idiomatically written (note the inversion of the then-else branches) (if (seq input) else then)

  • input-no-x can be obtained in a simpler way: (let [input-no-x (disj input x)])

share|improve this answer
    
Fixed the code - I had copy-pasted a late attempt at introducing loop \ recur - which didn't work (want to do this). Regarding the second parameter - it's an accumulator for the recursive call, so another improvement is that the function could be overloaded. –  noahz Jun 25 '12 at 14:58

I know this is an old question, but see the explanation here for a much simpler way:

http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch1/solutions/recursionSol.html

Code (from https://gist.github.com/796299 )

(defn powerset [ls]
  (if (empty? ls) '(())
      (union (powerset (next ls))
        (map #(conj % (first ls)) (powerset (next ls))))))
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.