clojure - 核心逻辑: how to generate a repeated sequence of number?

Question

我正在尝试使用 core.logic 生成数字序列 ((1), (1, 2), (1, 2, 1), (1, 2, 1, 2) ...):

(defn generator
  ([q] (generator q '()))
  ([q r]
   (lc/fresh [rw rws]
     (lc/conso 1 r rw)
     (lc/conjo rw 2 rws)
     (lc/conde
      [(lc/== q rw)]
      [(lc/== q rws)]
      [(generator q rws)]))))

(lc/run 6 [q]
    (generator q)))

但是我遇到了这个异常

clojure.core.logic.LCons 无法转换为 clojure.lang.IPercientCollection

如果我用 conso 替换 conjo:

(defn generator
  ([q] (generator q '()))
  ([q r]
   (lc/fresh [rw rws]
     (lc/conso 1 r rw)
     (lc/conso 2 rw rws)
     (lc/conde
      [(lc/== q rw)]
      [(lc/== q rws)]
      [(generator q rws)]))))

我得到了正确的结果，但顺序不正确:

((1), (2, 1), (1, 2, 1), (2, 1, 2, 1) ...)

为什么我在使用 conjo 时遇到错误，但在使用 conso 时却没有错误？

我应该如何继续以正确的顺序生成序列？

Answer 1

解决方案

首先，这是一种利用特定问题结构的方法:

(defn generator
  ([q] (generator q '(1) '(1 2)))
  ([q x y]
   (l/fresh [x' y']
     (l/appendo '(1 2) x x')
     (l/appendo '(1 2) y y')
     (l/conde
       [(l/== q x)]
       [(l/== q y)]
       [(generator q x' y')]))))

在 REPL 上:

(l/run 6 [q] (generator q))
;= ((1) (1 2) (1 2 1) (1 2 1 2) (1 2 1 2 1) (1 2 1 2 1 2))

请注意，这是非常有效的，因为它只将项目添加到列表中。

为什么原来的方法不起作用？

从表面上看，conso 使用传统的 Lisp cons 单元，使用 core.logic 内部的类型表示。这些不是常规的 Clojure 持久集合，conjo 不接受它们作为参数。

在更深层次上，即使 conjo 接受 lcons 单元格作为参数，这里它实际上相当于 conso，因为 conj ( conjo 的功能对应项)将项目添加到列表中(此处 lconses 代表列表)。这是因为列表仅支持有效的前置；将项目添加到列表末尾涉及重建整个列表，因此是一个 O(n²) 操作。

最后，即使 conjo 可以在列表末尾附加项目，但这仍然不起作用，因为你会得到一个序列

((1) (1 2) (1 1 2) (1 1 2 2) (1 1 1 2 2) (1 1 1 2 2 2) …)

事实上，您可以使用 appendo 对 core.logic 执行此操作 - 尝试放入 (appendo rw '(2) rws) 代替您的 conjo 调用查看。

如果您愿意，您可以采用原来的方法，将 conso 的单一使用替换为 conjo，将 () 文字替换为一个 [] 文字，并运行 generator 来获取向量序列:

([1] [1 2] [1 2 1] [1 2 1 2] [1 2 1 2 1] [1 2 1 2 1 2])

这是因为向量支持在右端高效附加元素。