Почему эта реализация sorto не завершается?

Я новичок в логическом программировании.

Я пытаюсь реализовать отношение сортировки следующим образом:

(sorto [3 2 1][1 2 3]) -> #s

Я использую clojure и core.logic:

Я не понимаю, почему это не может прекратиться в большинстве случаев.

Любая идея будет полезна, спасибо.

(require '[clojure.core.logic :refer :all]
         '[clojure.core.logic.fd :as fd])

Сначала я определяю несколько маленьких помощников:

Простое отношение счета: (counto [a b] 2) -> #s

(defne counto [list n]
       ([() 0])
       ([[fl . rl] _]
         (fresh [nnxt]
                (fd/- n 1 nnxt)
                (counto rl nnxt))))

уменьшить и каждый? относительные эквиваленты:

(defne reduceo [rel acc x y]
       ([_ _ () _] (== acc y))
       ([_ _ [fx . rx] _]
         (fresh [nacc]
                (rel acc fx nacc)
                (reduceo rel nacc rx y))))

(defne everyo [g list]
       ([_ ()])
       ([_ [fl . rl]]
         (g fl)
         (everyo g rl)))

минимальное отношение: (mino 1 2 1) -> #s

(defn mino [x y z]
  (conde
    [(fd/<= x y) (== x z)]
    [(fd/> x y) (== y z)]))

отношение между списком и его минимальным элементом: (mino* [1 2 3 0] 0) -> #s

(defne mino* [xs y]
       ([[fxs . rxs] _]
         (reduceo mino fxs rxs y)))

Основное отношение: (sorto [2 3 1 4] [1 2 3 4]) -> #s

(defne sorto [x y]
       ([() ()])
       ([[fx . rx] [fy . ry]]
         (fresh [x* c]
                (counto rx c)
                (counto ry c)
                (mino* x fy)
                (rembero fy x x*)
                (sorto x* ry))))

Приведенные ниже запуски не завершаются, я хотел бы понять, почему.

(run* [q]
      (sorto q [1 2]))
; does not terminate

(run* [q]
      (sorto [2 1] q))
; does not terminate

(run* [a b]
      (everyo #(fd/in % (fd/interval 10)) a)
      (everyo #(fd/in % (fd/interval 10)) b)
      (sorto a b))
;neither

person szymanowski    schedule 08.11.2017    source источник
comment
Честно говоря, я думаю, вам нужно сузить сферу вопроса с меньшим количеством кода, который необходимо просмотреть.   -  person Pumphouse    schedule 09.11.2017
comment
Лучше подходит для CodeReview.   -  person Thumbnail    schedule 09.11.2017


Ответы (1)


Ответ высокого уровня заключается в том, что соединение проверяется по порядку. Изменение их порядка иногда может привести к завершению программы, однако в общем случае может не существовать «хорошего» порядка.

Взгляните на главу 5 в https://scholarworks.iu.edu/dspace/bitstream/handle/2022/8777/Byrd_indiana_0093A_10344.pdf

person cgrand    schedule 10.11.2017
comment
Спасибо за советы, посмотрю внимательнее - person szymanowski; 08.12.2017