Quicksort en MiniKanren.

Un algoritmo que me gusta mucho es el quicksort, porque es un algoritmo por demás claro. Ya he escrito lo fácil que es implementarlo en Erlang, Rust, haskell y lisp

Ahora le toca a MiniKanren, el lenguaje de programación lógica/relacional. Básicamente, el algoritmo toma un pivote y agrupa los menores que el pivote al principio y los mayores al final y aplica quicksort a estos dos grupos. Y si la lista es vacía o tiene un elemento, ya está ordenada. 

Vamos al código: 

(define (quicksorto xs ys)

  (conde

    [(== xs '())

     (== ys '())]

    [(fresh (pivot rest smaller larger

                    sorted-smaller sorted-larger)

       (== xs (cons pivot rest))

       (partitiono pivot rest smaller larger)

       (quicksorto smaller sorted-smaller)

       (quicksorto larger sorted-larger)

       (appendo sorted-smaller

                (cons pivot sorted-larger)

                ys))]))