235: Combinators235: Combinatorsby John Cowan (text), Arvydas Silanskas (code)
This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-235@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.
This SRFI contains various procedures that accept and return procedures, as well as a few others, drawn from an earlier version of Chicken. Common Lisp has a few of them too, and more come from the Standard Prelude from Programming Praxis. Using these procedures helps to keep code terse and reduce the need for ad hoc lambdas.
Many procedures such as map, filter,
fold, and their equivalents for data structures other
than lists accept an argument specifying the behavior to be performed
on each element of the data structure.
This can be done in one of two ways:
lambda to describe the needed behavior
define, which requires finding a
good name and splits the action into different locations, making the
code harder to read.Those composition procedures, called combinators, have been identified by the Scheme and Common Lisp communities as reducing such fragmentation while keeping the code dense.
Many of these procedures are documented in the style of
SRFI 219.
Rather than showing only how the procedures themselves are invoked,
it also shows how the returned procedures would be invoked.
This is done in order to make the descriptions easier to understand.
For example, if complement were documented in the standard style,
the description would say "Returns a procedure which, when applied to an argument,
returns #t when proc would return #f when applied to the same argument,
and #f otherwise", which is more convoluted and harder to understand.
However, this is merely a documentation style;
it would be pointless to actually invoke these procedures in this fashion.
((constantly obj ...) arg ...)
Returns the objs as its values, ignoring args.
(map (constantly 3) '(1 2 3)) => (3 3 3)
((complement proc) obj)
Returns #t when (proc obj) returns #f, and #f otherwise.
(map (complement (lambda (x) #f)) '(1 2 3)) => (#t #t #t) (map (complement (lambda (x) 3)) '(1 2 3)) => (#f #f #f)
((flip proc) . objs)
Returns what (apply proc (reverse objs ) returns.
((flip list) 1 2 3) => (3 2 1)
((swap proc) obj₁ obj₂ . objs)
Returns (apply proc obj₂ obj₁ objs).
((swap cons) 1 2) => (2 . 1)
((on-left proc) obj₁ obj₂)
Returns (proc obj₁).
(map (on-left list) '(1 2 3) '(4 5 6)) => '((1) (2) (3))
((on-right proc) obj₁ obj₂)
Returns (proc obj₂).
(map (on-right list) '(1 2 3) '(4 5 6)) => '((4) (5) (6))
((conjoin predicate ...) arg ...)
#f is returned.
If all predicates return true, then the last value is returned.
If there are no predicates, #t is returned.
(map (conjoin even? exact?) '(1.0 1 2.0 2)) => '(#f #f #f #t)
((disjoin predicate ...) arg ...)
#f is returned.
(map (disjoin even? exact?) '(1.0 1 2.0 2)) => '(#f #t #t #t)
((each-of proc ... ) arg ...)
Applies each of the procs in turn to args, discarding the results and returning an unspecified value.
(define (print-sum . numbers)
(display
(string-join (map number->string numbers)
"+" 'infix))
(newline))
(define (print-product . numbers)
(display
(string-join (map number->string numbers)
"*" 'infix))
(newline))
((each-of print-sum print-product) 1 2 3) => undefined ;prints:
1+2+3
1*2*3
((all-of predicate) list)
Applies predicate to each element of list in turn,
and immediately returns #f if predicate is not satisfied by that element.
If every element satisfies predicate,
returns the result of the last call to predicate.
If list is empty, returns #t.
((all-of even?) '(2 4 6)) => #t ((all-of odd?) '(1 2 3)) => #f
((any-of predicate) list)
Applies predicate to each element of list in turn,
and if predicate is satisfied by that element,
immediately returns the result of calling predicate.
If no element satisfies predicate returns #f.
If list is empty, returns #f.
((any-of even?) '(2 4 5)) => #t ((any-of odd?) '(2 4 6)) => #f
((on reducer mapper) obj₁ obj ...)
Applies mapper to each obj in any order and then applies reducer to all of the results in left to right order.
((on + -) 1 2 3) => -6
((left-section proc arg ...) obj ...)
Applies proc to args concatenated with objs.
(map (left-section - 1) '(1 2 3)) => (0 -1 -2)
((right-section proc arg ...) obj ...)
Applies proc to objs concatenated with the value of (reverse args).
(map (right-section - 1) '(1 2 3)) => (0 1 2)
((apply-chain proc₁ proc ...) arg ...)`
Applies the last proc to args returning zero or more values,
then applies the previous proc to the values, returning more values,
until the first proc has been invoked; its values are returned.
For example, (apply-chain car cdr) returns a procedure that
behaves like cadr:
(map (apply-chain car cdr) '((1 2 3) (4 5 6))) => (2 5)
((arguments-drop proc n) arg ...)((arguments-drop-right proc n) arg ...)((arguments-take proc n) arg ...)((arguments-take-right proc n) arg ...)
Apply proc to the args after taking/dropping n arguments from args.
(apply (arguments-drop + 2) '(1 2 3 4 5)) => 12 (apply (arguments-drop-right + 2) '(1 2 3 4 5)) => 6 (apply (arguments-take + 2) '(1 2 3 4 5)) => 3 (apply (arguments-take-right + 2) '(1 2 3 4 5)) => 9
((group-by key-proc [=]) list)
Takes the elements of list and applies key-proc
to each of them to get their keys. Elements
whose keys are the same (in the sense of =,
which defaults to equal?)
are grouped into newly allocated lists, and a list of
these lists is returned. Within each list, the elements
appear in the same order as they do in list; in addition,
the first elements of each list also appear in the same
order as they do in list. If list is the empty list,
it is returned.
((group-by car) '((1 2 3) (2 2 3) (1 4 5))) => (((1 2 3) (1 4 5)) ((2 2 3))
These are Scheme procedures that correspond to basic syntax. As usual in Lisps, thunk means a procedure that does not require arguments.
The following procedures are understood to be defined in this section:
(define (a) (display #\a)) (define (b) (display #\b)) (define (c) (display #\c)) (define (z) (display #\z))
(begin-procedure thunk ...)
Invokes thunks in order, and returns what the last thunk returns, or an unspecified value if there are no thunks.
(begin-procedure a b c) => unspecified (displays "abc")
(if-procedure value then-thunk else-thunk)
If value is true, invokes then-thunk and returns what it returns. Otherwise, invokes else-thunk and returns what it returns.
(if-procedure #t (lambda () 1) (lambda () 2)) => 1 (if-procedure #f (lambda () 1) (lambda () 2)) => 2
(when-procedure value thunk ...)(unless-procedure value thunk ...)
If value is false/true, immediately returns. Otherwise, invokes each thunk in turn and then returns. In all cases an unspecified value is returned.
(when-procedure #t a b c) => unspecified ;prints "abc" (when-procedure #f a b c) => unspecified ;prints nothing (unless-procedure #t a b c) => unspecified ;prints nothing (unless-procedure #f a b c) => unspecified ;prints "abc"
(value-procedure value then-proc else-thunk)
If value is true, invokes then-proc on it and returns what then-proc returns. Otherwise, invokes else-thunk and returns what it returns.
(value-procedure 2 (lambda (x) (+ x 1)) (lambda () 0)) => 3) (value-procedure #f (lambda (x) (+ x 1)) (lambda () 0)) => 0)
(case-procedure value thunk-alist [ else-thunk ])
Searches thunk-alist for value (as if by assv).
If there is a matching entry in thunk-alist,
its cdr is invoked as a thunk, and case-procedure returns what the thunk returns.
If there is no such entry in thunk-alist,
invokes else-thunk (if present) and returns what it returns.
If else-thunk is not present, the result is undefined.
(case-procedure 0 `((1 . ,a) (2 . ,z) (3 . ,c)) z) => undefined ;displays "z" (case-procedure 0 `((1 . ,a) (2 . ,z) (3 . ,c))) => undefined ;displays nothing (case-procedure 2 `((1 . ,a) (2 . ,b) (3 . ,c))) => undefined ;displays "b"
(and-procedure thunk ...)
The thunks are invoked from left
to right, and if any thunk returns false,
then #f is returned.
Any remaining thunks are not invoked.
If all the thunks return true
values, the values of the last thunk are returned. If
there are no thunks, then #t is returned.
(and-procedure (lambda () #t) (lambda () #f) (lambda () (error "fail"))) => #f
(eager-and-procedure thunk ...)
All the thunks are invoked from left
to right. If any thunk returns false,
then #f is returned. If all the thunks return true
values, the value of the last thunk is returned. If
there are no thunks, then #t is returned.
(eager-and-procedure (lambda () #t) (lambda () #f) (lambda () (error "fail"))) => error
(or-procedure thunk ...)
The thunks are invoked from left
to right, and the first true value is returned.
Any remaining thunks are not invoked.
If all thunks return
#f or if there are no thunks, then #f is returned.
(or-procedure (lambda () #t) (lambda () #f) (lambda () (error "fail"))) => #t
(eager-or-procedure thunk ...)
All the thunks are invoked from left
to right, and then the first true value is returned.
If all thunks return
#f or if there are no thunks, then #f is returned.
(eager-or-procedure (lambda () #t) (lambda () #f) (lambda () (error "fail"))) => error
(funcall-procedure thunk)
Invokes thunk once, and returns what it returns.
Note that the name funcall is derived from Common Lisp.
(loop-procedure thunk)
Invokes thunk repeatedly. Does not return unless via call/cc.
(loop-procedure (lambda () (a) (b))) => ; #displays "abab..." forever
(while-procedure thunk)
Invokes thunk repeatedly until it returns false. Returns an unspecified value.
(let ((i 0))
(while-procedure
(lambda ()
(display i)
(set! i (+ i 1))
(< i 10)))) => unspecified ;prints "0123456789"
(until-procedure thunk)
Invokes thunk repeatedly until it returns true. Returns an unspecified value.
(let ((i 10))
(until-procedure
(lambda ()
(set! i (- i 1))
(display i)
(> i 0)))) => unspecified ;prints "9876543210"
(always obj ...)
Ignores its arguments and always returns #t.
(always 1 2 3) => #t
(never obj ...)
Ignores its arguments and always returns #f.
(never 1 2 3) => #f
(boolean obj)
If obj is true, returns #t; otherwise returns #f.
(boolean 3) => #t (boolean #f) => #f
The sample implementation is in the SRFI 235 repository.
Thanks to Kon Lovett, author of the Chicken egg (who credits Graham Fawcett and Philip L. Bewig); to the anonymous author of the Programming Praxis web site; and to the members of the SRFI-235 mailing list.
© 2022 John Cowan, Arvydas Silanskas.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.