Hello everyone,
I wrote a number of functions to perform operations on the lists of predica=
tes. Some of them are very convenient and most of them is non-trivial. I'm =
sharing them with you, because perhaps you could help me improve some of th=
em, or come up with better and more coherent names for them, or point to a =
library that already contains such functions, or show me that there are bet=
ter solutions and that I should abandon this way of thinking.

I was using guile to actually implement the code, and I was frequently usin=
g the "while" macro that can be found in guile-2.0.2/module/ice-9/boot-9.sc=
m
http://git.savannah.gnu.org/gitweb/?p=3Dguile.git;a=3Dblob;f=3Dmodule/ice-9=
/boot-9.scm;h=3D3bf4922804a27dd0780f4edd2b60e14635cb4c40;hb=3Drefs/heads/ma=
ster#l2934

Besides, the code uses srfi-1 and srfi-8 (although the latter could be avoi=
ded easily)

My initial motivation was to write the function "sublists" (I don't really =
like that name) that accepts a list of elements and a list of predicates an=
d returns all sub-sequences of all the permutations that satisfy the consec=
utive predicates.

So, for instance, I would like
(sublists (list even? odd?) '(1 2 3 4 5))
to return ((1 2) (1 4) (3 2) (3 4) (5 2) (5 4))

My first idea was, that in order to write such a function, I'd need a funct=
ion "*find-sublist-pred" (I know, that's even a worse name) that would retu=
rn the first sublist of a given list that would satisfy the consecutive ele=
ments:
(*find-sublist-pred (list even? odd?) '(1 2 3 4 5))
-> (2 3)

But if I had such a function, it would be difficult to use it to implement =
"sublists", because it discards information about the elements that were an=
d were not searched. So perhaps it would be better to contain this informat=
ion in the return value as well. Therefore, I decided to write "find-sublis=
t-pred" that would return three values: the list of items searched so far, =
the list satisfying the criteria, and the list of remaining elements. To ma=
ke things more complicated, I took this idea literally and actually used th=
e 'values' function to form a return value, instead of returning a list of =
lists.

So here's the code for "find-sublists-pred":

(define (find-sublist-pred predicate-list element-list)
"PREDICATE-LIST is a list of predicates, and ELEMENT-LIST a list to be sear=
ched for a sublist of subsequent elements, such that all elements satisfy t=
he corresponding predicates. It returns three values: (1) elements that hav=
e been searched through so far, (2) the desired sublist (or '() if none was=
 found) and (3) the remaining elements."
(let ((current-position element-list)
      (sublist-found '())
      (revised '()))
  (while (not (null? current-position))
    (let ((truth-values (map (lambda (f x) (f x))
                             predicate-list current-position)))
      (if (and (=3D (length truth-values) (length predicate-list))
               (every true? truth-values))
        (begin
          (set! sublist-found (take current-position (length predicate-list=
)))
          (set! current-position (drop current-position (length truth-value=
s)))
          (break))
      ;else
        (begin
          (set! revised (append/cons revised (car current-position)))
          (set! current-position (cdr current-position))))))
  (values revised sublist-found current-position)))

As a cautious reader might have noticed, two mysterious functions appear in=
 the code:

(define (append/cons x . rest)
  (if (list? x)
    (append x rest)
 ;;else
    (cons x rest)))

(define (true? x) (if x #t #f))

Besides the code should be clear, even if not optimal. It doesn't take long=
 to find out that the function works:
(sublists (list even? odd?) '(1 2 3 4 5))
=3D> #<values ((1) (2 3) (4 5))>

Once this function was written, it is tempting to write a "map" variant tha=
t would apply a given function to the arguments that satisfy the criteria. =
So for instance,
(map-sublists-pred (list even? odd?) Fxyz '(1 2 3 4 5 6 7))
would return a list created by applying
(Fxyz (1)(2 3)(4 5 6 7))
(Fxyz (1 2 3)(4 5)(6 7))
(Fxyz (1 2 3 4 5)(6 7)())
and appending the results.

(define (map-sublists-pred predicate-list fxyz element-list)
"map-sublist applies fxyz to all subsequent sublists of ELEMENT-LIST that s=
atisty predicates in PREDICATE-LIST, also passing the complement of ELEMENT=
-LIST in the following manner: FXYZ takes three arguments: (FXYZ previous t=
his next), where PREVIOUS are all the elements considered so far, THIS is t=
he currently considered sublist that satisfies the requirements (empty if n=
one found), and NEXT is the list of elements that weren't considered yet. W=
hen FXYZ is called, the following predicate is true within it: (equal? elem=
ent-list (append prev this next)).=20

If PREDICATE-LIST is null, the behavior is unspecified."
(let ((revised '())
      (result '()))
  (while (not (null? element-list))
    (receive (rev found rest)(find-sublist-pred predicate-list element-list=
)
      (set! revised (append revised rev))
      (if (not (null? found))
        (begin
          (set! element-list (append (cdr found) rest))
          (set! result (append result (fxyz revised found rest)))
          (set! revised (append revised (list (car found)))))
     ;;else
        (break))))
  result))

Although the name of the function might seem mysterious, it turned out to b=
e quite useful for me recently, as I've been writing a simple library that =
treats the lists of lists as matrices, and so I could easily implement a fu=
nction that calculates all minors of rank n-1 for a matrix of rank n.

It is also a pleasure now to write a function that would split a list into =
two lists, first containing the elements that satisfy the predicate list, a=
nd the second containing the remaining elements:

(define (distinguish-sublists predicate-list element-list)
"Return all consecutive sublists of ELEMENT-LIST that satisfy the correspon=
ding predicates from PREDICATE-LIST, paired with the remaining elements of =
the list. For example, (distinguish-sublists (list even? odd?) '(1 2 3 4 5)=
) would return (((2 3) (1 4 5)) ((4 5) (1 2 3)))"
(map-sublists-pred predicate-list
                   (lambda(prev this next)
                     (list (list this (append prev next))))
                   element-list))

This function makes it extremely easy, for instance, to write a function th=
at would return all permutations of a given list:

(define (all-permutations l)
  (let ((n (length l)))
    (cond ((=3D n 0) '())
          ((=3D n 1) (list l))
          ((=3D n 2) (list (list (first l) (second l))
                         (list (second l) (first l))))
          (#t (append-map (lambda (x)
                            (map (lambda(y)
                                   (append (first x) y))
                                 (all-permutations (second x))))
                          (distinguish-sublists (list true?) l))))))

Having this set of tools, it is now possible to write a concise definition =
of aforementioned "sublists":

(define (sublists predicate-list element-list)
"returns all possible sublists of all the permutations of ELEMENT-LIST, suc=
h that their elements satisfy the consecutive predicates from PREDICATE-LIS=
T, which should be non-empty.=20
So for instance, (sublists (list odd? even?) '(1 2 3 4 5)) would return ((1=
 2) (1 4) (3 2) (3 4) (5 2) (5 4))"
(if (singleton? predicate-list)
  (map first (distinguish-sublists predicate-list element-list))
;;else
  (append-map (lambda(x)
                (map (lambda(y)
                       (append (first x) y))
                     (sublists (cdr predicate-list)(second x))))
              (distinguish-sublists (list (car predicate-list)) element-lis=
t))))

It may look simple, but writing these 7 lines of code took 3 days of my lif=
e and caused a terrible vertigo. The only thing that starves for an explana=
tion is the function "singleton?", which is my pretentious abbreviation for=
 (lambda(x)(=3D (length x) 1)).

As you can see, the explanation of the behavior of functions like 'map-subl=
ists-pred' in the natural language was rather difficult, which is a serious=
 argument against the use of that function. On the other hand, one can sens=
e a certain conceptual simplicity somewhere beneath.

I don't know what to do with that code. Perhaps some of you would have an i=
dea.
Thank you for your attention.
Best regards
Panicz

godek.maciek writes:

> Hello everyone,
> I wrote a number of functions to perform operations on the lists of
> predicates. Some of them are very convenient and most of them is
> non-trivial. I'm sharing them with you, because perhaps you could
> help me improve some of them, or come up with better and more
> coherent names for them, or point to a library that already contains
> such functions, or show me that there are better solutions and that
> I should abandon this way of thinking.

I like your thinking. I present two contributions. First, what you
call a sublist, a given number of elements in any order, has been
called a variation in combinatorics: the permutations of a set of n
elements are its n-variations, and shorter variations are permutations
of its proper combinations (and the null combination). This might lead
to happier names for your functions.

Second, I will show my own take on the problem and some comments along
the way, just to compare notes.

> I was using guile to actually implement the code, and I was
> frequently using the "while" macro that can be found in

I use the "named let" of Scheme instead. It is a very general
iteration/recursion construct that works nicely without set!. However,
the two procedures I present still require set! or something
equivalent to be useful, just like Scheme's for-each; without it they
just spin the wheels.

The underlying tool I use is a procedure (select proc elts) that calls
proc with each element in elts together with the list of preceding
elements and the list of following elements, inspired by a common
Prolog procedure with the same name. I don't know if it appears in any
Scheme libraries so far. I wrote it from scratch again.

guile> (select (lambda (b e a) (display (list b e a)) (newline))
               '(3 1 4 1))
(() 3 (1 4 1))
((3) 1 (4 1))
((3 1) 4 (1))
((3 1 4) 1 ())

So, here is what I do with my select:

(define (for-variations/pattern yield pattern elements)
  (let dive ((pattern (reverse pattern))
	     (tail '())
	     (rest elements))
    (if (pair? pattern)
	(select (lambda (before next after)
		  (if ((car pattern) next)
		      (dive (cdr pattern)
			    (cons next tail)
			    (append before after))))
		rest)
	(yield tail))))

Read: "for variations with pattern". It applies the procedure yield
for each variation of the elements that satisfies the pattern, where
the pattern is your list of predicates. This is a second version,
after I remembered that the pattern is a perfectly good representation
of its own length.

That's using "named let" for deep recursion, hence "(let dive ...)"
instead of the more usual "(let loop ...)". The "named let" in select
is more mundane:

(define (select yield elements)
  (if (pair? elements)
      (let loop ((before '())
		 (next (car elements))
		 (after (cdr elements)))
	(yield (reverse before) next after)
	(if (pair? after)
	    (loop (cons next before)
		  (car after)
		  (cdr after))))))

Lots of consing under the hood, and it is not safe to modify the
returned lists, but otherwise these are nice tools.

> My initial motivation was to write the function "sublists" (I don't
> really like that name) that accepts a list of elements and a list of
> predicates and returns all sub-sequences of all the permutations
> that satisfy the consecutive predicates.
> 
> So, for instance, I would like
> (sublists (list even? odd?) '(1 2 3 4 5))
> to return ((1 2) (1 4) (3 2) (3 4) (5 2) (5 4))

I think you mean the other way around.

(define (variations/pattern pattern elements)
  (let ((result '()))
    (for-variations/pattern
     (lambda (variation)
       (set! result (cons variation result)))
     pattern
     elements)
    result))

guile> (variations/pattern (list even? odd?) '(1 2 3 4 5))
((4 5) (2 5) (4 3) (2 3) (4 1) (2 1))

>                (every true? truth-values))

I think you could use (every values truth-values) here, or maybe
(lambda (x) x) for the identity function. (Though values _is_ the
identity function.)

> (define (append/cons x . rest)
>   (if (list? x)
>     (append x rest)
>  ;;else
>     (cons x rest)))

This feels just wrong, though I admit that I did not pay careful
attention to what you are using it for. What if the elements of the
original list are lists?

> If PREDICATE-LIST is null, the behavior is unspecified."

The empty list satisfies the null pattern:

guile> (variations/pattern (list) '(1 2 3 4 5))
(())

> It is also a pleasure now to write a function that would split a
> list into two lists, first containing the elements that satisfy the
> predicate list, and the second containing the remaining elements:

This I don't know what to do about.

> This function makes it extremely easy, for instance, to write a
> function that would return all permutations of a given list:
> 
> (define (all-permutations l)

(variations/pattern (map (lambda (:) list) l) l)

> for an explanation is the function "singleton?", which is my
> pretentious abbreviation for (lambda(x)(= (length x) 1)).

That's a perfectly good name for that.

> As you can see, the explanation of the behavior of functions like
> 'map-sublists-pred' in the natural language was rather difficult,
> which is a serious argument against the use of that function. On the
> other hand, one can sense a certain conceptual simplicity somewhere
> beneath.

I like your thinking.

I didn't mean to write in such length and now I have no time to make
it shorter. Best regards.

Thanks a lot!

The idea to call the function 'variations/pattern' certainly looks much cle=
aner.
On the other hand, the name 'select' might be not so fortunate, because fir=
stly there is a long unix tradition to use it to name a system call (which =
should have been called 'fdcheck' or likewise), and secondly it still doesn=
't describe the function adequately.
I've been thinking about the name 'map3', because the magic number could co=
nvince the user to read the documentation. However, this name suggests that=
 the function maps, so there should be a return value, therefore the actual=
 implementation of map3 should behave more like this:

(define (rmap3 yield elements)
  (if (pair? elements)
    (let loop ((before '())
               (next (car elements))
               (after (cdr elements))
               (return '()))
      (let ((result (yield (reverse before) next after)))
        (if (pair? after)
          (loop (cons next before)
                (car after)
                (cdr after)
                (cons result return))
        (cons result return))))))

The other name that came into my head was 'skim'.

> >                (every true? truth-values))
>=20
> I think you could use (every values truth-values) here, or maybe
> (lambda (x) x) for the identity function. (Though values _is_ the
> identity function.)

Yes, I guess you're right. At first I thought that defining a "true?" predi=
cate would make the code more pleasant to read, but it turned out that it o=
nly became more bothersome to maintain.

> > (define (append/cons x . rest)
> >   (if (list? x)
> >     (append x rest)
> >  ;;else
> >     (cons x rest)))
>=20
> This feels just wrong, though I admit that I did not pay careful
> attention to what you are using it for. What if the elements of the
> original list are lists?

I didn't think about it :]
By the way, I once came up with another brilliant function of that sort,

(define (cons/list a b)
  (if (list? b)
    (cons a b)
 ;;else
    (list a b)))

because it was helpful to define a Cartesian product of two lists:

(define (cart . args)
  (let ((n (length args)))
    (cond ((=3D n 0) '())
          ((=3D n 1) (car args))
          (#t (append-map (lambda(x)
                            (map (lambda(y)
                                   (cons/list y x))
                                 (car args)))
                          (apply cart (cdr args)))))))

Maybe it's not the best idea, but I think it makes the code a little cleane=
r.

> > If PREDICATE-LIST is null, the behavior is unspecified."
>=20
> The empty list satisfies the null pattern:
>=20
> guile> (variations/pattern (list) '(1 2 3 4 5))
> (())

:) nice

> > This function makes it extremely easy, for instance, to write a
> > function that would return all permutations of a given list:
> >=20
> > (define (all-permutations l)
>=20
> (variations/pattern (map (lambda (:) list) l) l)

I didn't find that surprising at all :)

> > for an explanation is the function "singleton?", which is my
> > pretentious abbreviation for (lambda(x)(=3D (length x) 1)).
>=20
> That's a perfectly good name for that.

It is, isn't it? :) And it's so much more convenient to write, because you =
don't have to press shift so many times to open and close the parentheses (=
only once for the question mark!)

> > As you can see, the explanation of the behavior of functions like
> > 'map-sublists-pred' in the natural language was rather difficult,
> > which is a serious argument against the use of that function. On the
> > other hand, one can sense a certain conceptual simplicity somewhere
> > beneath.
>=20
> I like your thinking.
>=20
> I didn't mean to write in such length and now I have no time to make
> it shorter. Best regards.

It wasn't
so long
:)