Hi Will!
The `split` relation in the code you linked (llmr.scm) is a very similar
relation on the domain of multisets. Thank you for sharing!
Regarding another use of `riffleo`: I have been trying to transform an
undirected graph into a sequence of nonoverlapping bicliques (complete
bipartite subgraphs). This is always possible, since every graph has a
maximum independent edge set (which can be thought of as (1, 1)-bicliques).
This decomposition into bicliques has an application in graph coloring.
I have found `riffleo` useful for partitioning the vertices of the graph
into 3 sets: `left`, `right`, and `rest-v`. Then I can check if there is an
edge from every vertex in `left` to every vertex in `right`. Here is the
code for that. Hopefully the implicit relations make sense.
(defrel (bicliqueso graph bicliques)
(conde
((== bicliques '()) (empty-grapho graph))
((fresh (v e rest-v rest-e rest-g rest-bicliques left right*rest-v
right)
;; A biclique is a pair of vertex sets
(== bicliques `((,left . ,right) . ,rest-bicliques))
(pairo left)
(pairo right)
;; Assume an efficient undirected graph data structure
(verticeso g v)
(verticeso rest-g rest-v)
(edgeso g e)
(edgeso rest-g rest-e)
* ;; partition the vertices into nonempty `left`, nonempty `right`,
and `rest-v`*
* (riffleo left right*rest-v v) (riffleo right rest-v
right*rest-v)*
;; check that every vertex in `left` is connected to every vertex in
`right`
(is-bicliqueo left right g)
;; Keep only the edges which have both vertices in `rest-v`
(filtero e rest-v rest-e)
(bicliqueso rest-g rest-bicliques)))))
This ended up being unfeasible since I could not think of a good data
structure for representing an undirected graph in miniKanren, and I found
it difficult to write `is-bicliqueo`. I ended up porting `riffleo` into
Python as `unriffle`.
def unriffle(o: List[T]) -> Iterator[Tuple[List[T], List[T]]:
...
I used that for a while in Python until I figured out a bottom-up way to
find all bicliques by constructing a table all_bicliques_of_size[m][n].
TL;DR - `riffleo` can be used to partition a set into n disjoint subsets,
which may be useful for detecting bicliques.
Brett
On Monday, October 24, 2022 at 1:16:10 PM UTC-4 William Byrd wrote:
> Hi Brett!
>
> I don't recall if I've used `riffleo` before, but I agree that it looks
> useful!
>
> We may have used something similar in this code:
>
> https://github.com/webyrd/linear-logic-multiset-rewriting
>
> What are other examples of uses of `riffleo` that you have encountered?
>
> Cheers,
>
> --Will
>
> On Mon, Oct 24, 2022 at 12:35 PM Brett Schreiber <[email protected]>
> wrote:
>
>> Hello all,
>> I have become very interested in relational programming, and I have
>> enjoyed trying to a variety of search problems in miniKanren. I have found
>> a relation that has been useful to many of these problems.
>>
>> Consider the relation a * b = o where:
>>
>> 1. a is a list
>> 2. b is another list, and
>> 3. o is the result of nondeterministically merging the lists, i.e.,
>> (a * b)
>>
>> It reminds me of the "riffle" step when shuffling a deck of cards.
>> Here is an example:
>>
>> a = '( a b c d e f)
>> b = '(1 2 3 4 5 6 7 8 )
>> o = '(1 2 a 3 b c 4 5 d 6 e 7 8 f)
>>
>> Some properties:
>>
>> - a * (b * c) = (a * b) * c
>> - |a * b| = |a| + |b|
>> - (a * b) contains a and b as subsequences
>> - which implies if (a * b) is sorted, then a is sorted and b is
>> sorted
>> - a * b = b * a
>>
>> Notice that appendo shares all of these properties except the last one.
>> So this is some sort of generalization of appendo.
>>
>> Here is the relation's definition in miniKanren, where a * b = o is
>> written (riffleo a b o)
>>
>> (defrel (riffleo a b o)
>> (fresh (car-a cdr-a car-b cdr-b car-o cdr-o)
>> (conde
>> ;; If `a` and `b` are both empty, then the output is empty.
>> ((== a '()) (== b '()) (== o '()))
>>
>> ;; If `a` is non-empty and `b` is empty,
>> ;; then the output is equal to `a`.
>> ((== a `(,car-a . ,cdr-a)) (== b '()) (== o a))
>>
>> ;; If `a` is empty and `b` is non-empty,
>> ;; then the output is equal to `b`.
>> ((== a '()) (== b `(,car-b . ,cdr-b)) (== o b))
>>
>> ;; When both `a` and `b` are non-empty
>> ((== a `(,car-a . ,cdr-a)) (== b `(,car-b . ,cdr-b)) (== o
>> `(,car-o . ,cdr-o))
>> (conde
>> ((== car-o car-a) (riffleo cdr-a b cdr-o))
>> ((== car-o car-b) (riffleo a cdr-b cdr-o)))))))
>>
>> And after applying a correctness-preserving transformation:
>>
>> (defrel (riffleo a b o)
>> (fresh (car-a cdr-a car-b cdr-b car-o cdr-o *z0 z1*)
>> (conde
>> ;; If `a` and `b` are both empty,
>> ;; then the output is empty.
>> ((== a '()) (== b '()) (== o '()))
>>
>> ;; If `a` is non-empty and `b` is empty,
>> ;; then the output is equal to `a`.
>> ((== a `(,car-a . ,cdr-a)) (== b '()) (== o a))
>>
>> ;; If `a` is empty and `b` is non-empty, then the output is
>> equal to `b`.
>> ((== a '()) (== b `(,car-b . ,cdr-b)) (== o b))
>>
>> ;; When both `a` and `b` are non-empty
>> ((== a `(,car-a . ,cdr-a)) (== b `(,car-b . ,cdr-b)) (== o
>> `(,car-o . ,cdr-o))
>>
>>
>>
>>
>> *(conde ((== car-o car-a) (== z0 cdr-a) (== z1 b))
>> ((== car-o car-b) (== z0 a) (== z1 cdr-b)))
>> (riffleo z0 z1 cdr-o)*))))
>>
>> I have found riffleo to be useful as a "choose" function when the
>> arguments are considered multisets rather than lists. For example, it makes
>> it easy to write the NP-complete 3-partition problem
>> <https://en.wikipedia.org/wiki/3-partition_problem> as a relation.
>>
>> (defrel (three-partitiono l partitions sum)
>> (fresh (e0 e1 e2 rest-l e0+e1 rest-partitions)
>> (conde
>> ;; Base case
>> ((== l '())
>> (== partitions '())))
>>
>> ;; Recursive case
>> ((== partitions `((,e0 ,e1 ,e2) . ,rest-partitions))
>> (riffleo `(,e0 ,e1 ,e2) rest-l l)
>> (+o e0 e1 e0+e1)
>> (+o e0+e1 e2 sum)
>> (three-partitiono rest-l rest-partitions sum))))
>>
>>
>> Has anyone else encountered this riffle relation?
>>
>> Best,
>> Brett Schreiber
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "minikanren" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to [email protected].
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/minikanren/ac5e6700-f7c6-4e1c-8915-d9db0907c715n%40googlegroups.com
>>
>> <https://groups.google.com/d/msgid/minikanren/ac5e6700-f7c6-4e1c-8915-d9db0907c715n%40googlegroups.com?utm_medium=email&utm_source=footer>
>> .
>>
>
--
You received this message because you are subscribed to the Google Groups
"minikanren" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/minikanren/b916b9a1-d5e9-4627-bd1c-d94d25713ed7n%40googlegroups.com.
