Clojure中的Powerset

Question

我认为我已经正确地在Clojure中实现了Powerset。

(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)))))))

当然，我感兴趣的是库函数如何将上面的一行代码变成一行代码，但我也感兴趣的是如何使上面的代码变得更加地道。

1. (if (nil? (first input))觉得不对。
2. 使用let块复制命令式计算。可以接受吗？
3. 我可以使用->>使下面的行更易读吗？(union result (set (list input set-of-x input-no-x)))
4. 我没有使用recur，因为我得到了“重复必须在尾部位置”编译器错误。

编辑删除的(loop)从最初发布的版本。-在我已经开始尝试引入循环/重复(尾递归)之后，我错误地复制了粘贴的代码。如何在这个函数中使用循环/重述？

Answer 1

关于您的代码的几个随机注释：

• 它不能正确地解析，我猜在loop绑定之后关闭的paren被错误地放置了。即使在修好它之后我也无法运行。
• 为什么需要第二个输入参数？我希望签名只将输入集作为参数。
• (if (nil (first input)) then else)是更具体的编写(注意当时的分支的倒置) (if (seq input) else then)。
• input-no-x可以以更简单的方式获得：(let [input-no-x (disj input x)])

Answer 2

我知道这是个老生常谈的问题，但请看这里的解释，有一种简单得多的方法：

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

代码(来自https://gist.github.com/796299 )

(defn powerset [ls]
  (if (empty? ls) '(())
      (union (powerset (next ls))
        (map #(conj % (first ls)) (powerset (next ls))))))