From: Drew Krause
Subject: rather simple list/set operation
Date: Tue, 3 Jan 2012 19:01:19 -0600

Drew Krause wrote:

> Maybe someone can help me with this?
>
> I start with a list, e.g.
>
> ((0) (1 3) (1 2) (4 6) (5 7) (7 8))
>
>
> and want all members of intersecting lists to appear in the same sublist:
>
> => ((0) (1 2 3) (4 6) (5 7 8))

Gauche Scheme:

(use srfi-1) ; "lset-" functions
(use srfi-42) ; do-ec

(define (coalesce lists)
(define accum '())
(do-ec (:list x lists)
(receive
(miss hit)
(partition (lambda (y) (null? (lset-intersection equal? x y)))
accum)
(set! accum
(cons (apply lset-union equal? x hit) miss))))
accum)

(coalesce '((2 4) (8 9) (4 5 8)))
===>
((2 9 4 5 8))

(coalesce '((2 4) (3 9) (5 6) (2 3)))
===>
((4 9 2 3) (5 6))

(coalesce '((0) (1 3) (1 2) (4 6) (5 7) (7 8)))
===>
((5 7 8) (4 6) (3 1 2) (0))

(coalesce '((2 4) (3 9) (5 6) (2 3) (55 66) (0) (66 6)))
===>
((5 55 66 6) (0) (4 9 2 3))

On 6/7/2024 1:56 AM, B. Pym wrote:
>
> From: Drew Krause
> Subject: rather simple list/set operation
> Date: Tue, 3 Jan 2012 19:01:19 -0600
>
>
> Drew Krause wrote:
>
>> Maybe someone can help me with this?
>>
>> I start with a list, e.g.
>>
>> ((0) (1 3) (1 2) (4 6) (5 7) (7 8))
>>
>>
>> and want all members of intersecting lists to appear in the same sublist:
>>
>> => ((0) (1 2 3) (4 6) (5 7 8))
I think the problem definition is ambiguous and not clarified by the
example. Consider the following input lists:
((0 1) (1 2) (2 3)),
((0 1) (0 2) (0 3)).
Any idea what Krause had in mind?
--
Jeff Barnett

Am 2024-06-07 um 20:07 schrieb Jeff Barnett:
> Any idea what Krause had in mind?
linked lists

On 6/7/2024 12:31 PM, Jens Kallup wrote:
> Am 2024-06-07 um 20:07 schrieb Jeff Barnett:
>> Any idea what Krause had in mind?
> linked lists

I'd love to see and Krause jointly specify a problem.
--
Jeff Barnett

(Common) LISP/SBCL

essential structure consists of two fields (or: one left hand field, and
one right hand field), which can extend trough other (same) fields of
the given field pair.

The lhs of the first form can be see as reference to it self or as start
point, that contain a pointer to the next form, which is represented on
the rhs.

You can cocoon this by other functions and/or commands/keywords, ...

=> here is an example: (1 2)
this is a simple form of a list, containing 1 and 2.

=> here is an example: (+ 2 1)
- this is a simple form of a operation,
- the + sign after the first paren is a "addition" function, that
take the first number from right (the 1) will be evaluate first,
and the add (+) symbol (which is a function) "signs" that the
next coming number (the 2) should be added to the (before eval 1)
so, you get as result the three (3).

=> each operation/command/task must have two objects, except, you call
a non-parameterized function or you build a list.

If you evaluate only one form, then you could be get a error message.
Or, if you evaluate a boolean value false (which is in LISP = nil) or
a boolean value true (wich is in LISP the single symbol T ).

You can create dictionaries by paring two elements or forms, where you
give a key on the left side, and a value on the right hand side:

(A . 1) or: (U . 3)

Jens

* Jeff Barnett <v3vi98$25sr1$1@dont-email.me> :
Wrote on Fri, 7 Jun 2024 12:07:33 -0600:

> On 6/7/2024 1:56 AM, W J wrote:
>> From: Drew Krause
>> Subject: rather simple list/set operation
>> Date: Tue, 3 Jan 2012 19:01:19 -0600
>> Drew Krause wrote:
>>> Maybe someone can help me with this?
>>> I start with a list, e.g.
>>>
>>> ((0) (1 3) (1 2) (4 6) (5 7) (7 8))
>>>
>>>
>>> and want all members of intersecting lists to appear in the same sublist:
>>>
>>> => ((0) (1 2 3) (4 6) (5 7 8))

> I think the problem definition is ambiguous and not clarified by the
> example.
> Consider the following input lists:
> ((0 1) (1 2) (2 3)),
> ((0 1) (0 2) (0 3)).
> Any idea what Krause had in mind?

One way to answer this is to write a program and define the problem to
by what the program solves.

Here is a suitably cringeworthy function to do that in lisp.

(defun krause-group (list-of-lists &aux ret)
(dolist (list list-of-lists)
(assert (consp list))
(let ((cons (or (find-if (lambda (x) (find (car list) x)) ret)
(let ((cons (list (car list))))
(push cons ret)
cons))))
(dolist (elt (cdr list))
(unless (find elt cons)
(setf (cdr cons) (cons elt (cdr cons)))))))
(nreverse ret))

(krause-group '((0) (1 3) (1 2) (4 6) (5 7) (7 8)))
=> ((0) (1 2 3) (4 6) (5 8 7))

(krause-group '((0 1) (1 2) (2 3)))
(krause-group '((0 1) (0 2) (0 3)))

So obviously krause wanted both of these lists to produce 1 list
((0 3 2 1))

B. Pym wrote:

> From: Drew Krause
> Subject: rather simple list/set operation
> Date: Tue, 3 Jan 2012 19:01:19 -0600

> Drew Krause wrote:

>> Maybe someone can help me with this?
>>
>> I start with a list, e.g. ((0) (1 3) (1 2) (4 6) (5 7) (7 8))
>>
>> and want all members of intersecting lists to appear in the same
>> sublist:
>> => ((0) (1 2 3) (4 6) (5 7 8))

> Gauche Scheme:

> (use srfi-1) ; "lset-" functions
> (use srfi-42) ; do-ec

> (define (coalesce lists)
> (define accum '())
> (do-ec (:list x lists)
> (receive
> (miss hit)
> (partition (lambda (y) (null? (lset-intersection equal? x y)))
> accum)
> (set! accum
> (cons (apply lset-union equal? x hit) miss))))
> accum)

> (coalesce '((2 4) (8 9) (4 5 8)))
> ===>
> ((2 9 4 5 8))

> (coalesce '((2 4) (3 9) (5 6) (2 3)))
> ===>
> ((4 9 2 3) (5 6))

> (coalesce '((0) (1 3) (1 2) (4 6) (5 7) (7 8)))
> ===>
> ((5 7 8) (4 6) (3 1 2) (0))

> (coalesce '((2 4) (3 9) (5 6) (2 3) (55 66) (0) (66 6)))
> ===>
> ((5 55 66 6) (0) (4 9 2 3))

Do-ec and Receive often go together?
Is there a set of programs (or Problems) or Tutorial for this style of
programming?

Transitive closure constructs the output graph from the
input graph.
In computer science, the concept of transitive closure can be thought of
as constructing a data structure that makes it possible to answer
reachability questions.