common-list module

Description: this doesn't quite fit with the overall purpose of these docs, but it pisses me off that I always seem to end up re-writing at least some of these. Basically, this is a collection of useful list functions (a la common lisp), which may eventually be usurped by SRFI-1 (Olin Shivers list proposal), but which are useful.

Note: The chapter on sequences in the common lisp hyperspec describes a cl implementations of these (which are much the same, but the cl versions have a few bells and whistles).

Another note: the set based operations (adjoin, union, intersection, set-difference) treat the lists as simple sets (that is, each element will only occur once). Also, satisfies predicate means predicate does not return #f.

Function: adjoin element list

Returns a list which contains element and the elements of list.

Function: union list1 list2

Returns a list containing the elements of list1 and list2

Function: intersection list1 list2

Returns a list containing the elements in both list1 and list2

Function: set-difference list1 list2

Returns a list containing the elements of list1 not in list2

Function: reduce-init proc init list

Returns the result of using proc to combine the elements of init and list. This is the same as doing (reduce proc (cons init list)), so see reduce for an explanation.

Function: reduce proc list

[NOTE: beware all ye who enter ... I'm probably going to end up confusing more people than I help with this one ;) ]

Combines the elements of list using proc, working from left to right. proc must take two arguments.

(reduce proc list)
-> (reduce proc (cons (proc (car list) (cadr list)) (cddr list)))
-> (reduce proc (cons res1 (cddr list)))
-> (reduce proc (cons (proc res1 (car (cddr list))) (cdr (cddr list))))
...

And so on, until all the values of list have been combined by proc. The result is the final result of

(proc [the results of all previous applications] [last element of list])

If list is null [ should this be '() instead?? ] , the result is null. If list contains one element, the result is that element.

It's probably easier to see what happens with a few examples:

(reduce (lambda (x y) (cons x y)) '(1 2 3 4 5))
=> ((((1 . 2) . 3) . 4) . 5)

(reduce (lambda (x y) (+ x y)) '(1 2 3 4 5))
=> 15

;;; Show the left -> right nature
(reduce (lambda (x y) (- x y)) '(1 2 3 4 5))
=> -13

(reduce (lambda (x y) (- x y)) '(5 4 3 2 1))
=> -5

This is quite a useful (though somewhat hard to explain ;) function. Note that, for functions which take any arbitrary number of arguments (like +), the effect is the same as doing (apply proc list), but it won't run into any problems with the maximum number of args per function in a given implementation.

Function: some pred list [lists]

Returns true if pred is true when applied to any element of list. If more than one list is given, pred must take a number of arguments equal to the number of list arguments, and is applied to each corresponding element in the list arguments. An error is signalled if the length of the lists are not equal (well, technically, an error is signalled if the length of the first list is longer than any of the following lists, and the error isn't exactly obvious, as demonstrated below).

(some even? '(1 2 3 4))
=> #t

(some (lambda (x y) (and (even? x) (even? y))) '(1 2 3 4) '(2 3 4 5))
=> #f

;;; Here's what happens if the first list is longer than another
;;; argument list

(some (lambda (x y) (and (even? x) (even? y))) '(1 2 3 4 5) '(2 3 4 5))
error--> /usr/local/share/guile/1.3.1/ice-9/common-list.scm:77:46: In procedure car in expression (map car rest):
error--> /usr/local/share/guile/1.3.1/ice-9/common-list.scm:77:46: Wrong type argument in position 1: ()
error--> ABORT: (wrong-type-arg)

Function: every pred list [lists]

Returns #t if every element of list satisfies pred, else returns #f. As with some, if more than one list is given, pred is applied to each corresponding element of each argument list. Same error bizarreness as some.

(every number? '(1 2 3 4 5))
=> #t

(every (lambda (x y) (and (number? x) (number? y))) '(1 2 3 4) '(a b c d))
=> #f

Function: notany pred list [lists]

Like some and every, except this returns #t if pred isn't satisfied, and #f if it is.

(notany even? '(1 2 3))
=> #f

Function: notevery pred list [lists]

#t if there is an element that doesn't satisfy pred, else #f. Same calling conventions as some and every.

(notevery (lambda (x y) (and (even? x) (even? y))) '(1 2 3 4) '(2 3 4 5))
=> #t

Function: find-if pred list

Returns the first element of list that satisfies pred, else #f

(find-if even? '(1 2 3 4))
=> 2

(find-if even? '(1 3 5 7))
=> #f

Function: member-if pred list

Like member, except instead of checking for a particular element, it checks for an element that satisfies pred, and returns the rest of list, starting with the element that satisfied the pred.

(member-if even? '(1 2 3 4))
=> (2 3 4)

Function: remove-if pred list

Returns list with each element that satisfies pred removed.

(remove-if even? '(1 2 3 4))
=> (1 3)

Function: delete-if! pred list

As (remove-if pred list), but can destructively modify list. As with most potentially destructive operations, you should still set the variable to the result of calling delete-if!

(define l '(1 2 3 4))
(set! l (delete-if! even? l))
;; Note: l may or may not be modified by the actual call to delete-if!

l
=> (1 3)

Function: delete-if-not pred list

Equivalent to (delete-if (lambda (x) (not (pred x))) list). This one demonstrates why you still need to set the variable to the result of the `destructive' function.

(define l '(1 2 3 4))
(delete-if-not! even? l)
=> (2 4)

l
=> (1 2 4)
;;; Ack!

Function: butlast list n

Returns a list which contains the first (- (length list) n) elements of list.

(butlast '(1 2 3 4) 1)
=> (1 2 3)

(butlast '(1 2 3 4) 4)
=> ()

Function: and? [args]

Returns #t if args are null, or if all args are not #f.

(and? 1 2 3)
=> #t

(and? 1 'yep 3)
=> #t

(and? 1 #f 2)
=> #f

Function: or? [args]

Returns #t if any of args are not #f. Returns #f if args is null.

(or? 1 2 3)
=> #t

(or? 1 #f 3)
=> #t

(or? #f #f #f)
=> #f

Function: has-duplicates? list

Returns #t if list contains an element more than once, else returns #f.

(has-duplicates? '(1 2 3 1))
=> #t

(has-duplicates? '(1 2 3))
=> #f

Function: list* elem [elements]

Like list, but the last element is appended to the newly formed list.

(list 1 2 3 4 5)
=> (1 2 3 4 5)

(list* 1 2 3 4 5)
=> (1 2 3 4 . 5)

(list 1 2 3 4 '(5 6 7))
=> (1 2 3 4 (5 6 7))

(list* 1 2 3 4 '(5 6 7))
=> (1 2 3 4 5 6 7)

Function: pick pred list

Returns a list of elements of the argument list for which pred is not #f. It isn't stable (i.e elements can be in any order). Essentially the same as (delete-if-not pred list).

(pick even? '(1 2 3 4))
=> (4 2)

(delete-if-not! even? '(1 2 3 4))
=> (2 4)

Function: pick-mappings pred list

Returns a list of the non-#f results of applying pred to the elements of list. This one is also not stable, but for a predicate p, the elements of (pick-mappings p list) correspond to the elements of (pick p list)

(pick-mappings (lambda (x) (if (> x 2) (- x 2) #f)) '(1 2 3 4))
=> (2 1)

(pick (lambda (x) (if (> x 2) (- x 2) #f)) '(1 2 3 4))
=> (4 3)

Function: uniq list

Returns a list which contains only one of each element in the argument list (not stable).

(uniq '(1 2 3 4 3 3 2 3))
=> (1 4 2 3)