2.6 list-utils

contents ← prev up next →

2.6 list-utils🔗

This module contains functions that operate on list structures.

(require sicm/general/list-utils)

package: rktsicm

2.6.1 list sections🔗

procedure
(last-pair lst) → pair?
lst : pair?

Return the last cons for which the cdr is not a pair?.

procedure
(except-last-pair lst) → list?
lst : pair?

Return a new list consisting of every element of lst except the last cons.

procedure
(last lst) → any/c
lst : list?

Retern the last element of lst.

procedure
(butlast lst) → list?
lst : list?

Return a new list consisting of every element of lst except the last element.

procedure
(split-list lst pred? receiver) → any/c
  lst : list?
  pred? : predicate/c
  receiver : (-> any/c any/c any/c)

Equivalent to

(let-values ([(yes no) (partition pred? lst)]) (receiver yes no))

procedure
(sublist lst start end) → list?
  lst : list?
  start : integer?
  end : integer?

Create a list starting from element at index start till end (non inclusive).

procedure
(delete-nth lst n) → list?
lst : list?
n : integer?

Create a new list without the nth element.

procedure
(delq-once lst element) → list?
lst : list?
element : any/c

Create a new list with the first item for which item is eq? to element removed.

2.6.2 substitution🔗

procedure
(subst new old expression) → any/c
  new : any/c
  old : any/c
  expression : any/c

In a nested list structure, replace any element that is eq? to old with new.

procedure
(substitute-multiple expression
substitutions) → any/c
expression : any/c
substitutions : (listof (list/c any/c any/c))

In a nested list structre, replace any element that is simple:equal? to a car in the substitution dictionary with its cadr. Care is taken to keep subexpression that did not change eq? to the original.

2.6.3 Count and search🔗

procedure
(count-elements pred? lst) → integer?
pred? : predicate/c
lst : list?

Count the elements in the list for which pred? returns #t.

procedure
(countsymbols expression) → integer?
expression : any/c

Count all the elements in the expression and subexpressions for which symbol? returns #t.

procedure
(find-first pred? lst) → any/c
pred? : predicate/c
lst : list?

Returns the first element for which pred? returns #t.

procedure
(find-infimum lst cmpr) → any/c
lst : list?
cmpr : (-> any/c any/c any/c)

Returns the first element e for which (cmpr e l) returns #t, where l are all other elements after e in lst.

procedure
(list-index-of elmnt lst) → (or/c #f integer?)
elmnt : any/c
lst : list?

Returns the index of the first element that is eqv? to elmnt.

2.6.4 map and fold🔗

procedure
(safe-map fct lst) → pair?
fct : (-> any/c any/c)
lst : pair?

map that works on a single, possible improper lists.

procedure
(reduce combine def lst) → any/c
  combine : (-> any/c any/c any/c)
  def : any/c
  lst : list?
procedure
(reduce-left combine def lst) → any/c
  combine : (-> any/c any/c any/c)
  def : any/c
  lst : list?

Similar as foldl but if lst is null?, def is returned. If lst is a singleton, the first/only element is returned. If the lst is longer than 1, the first two elements to which fct is applied are the first two elements of the list.

procedure
(reduce-right combine def lst) → any/c
  combine : (-> any/c any/c any/c)
  def : any/c
  lst : list?

Similar as foldr but if lst is null?, def is returned. If lst is a singleton, the first/only element is returned. If the lst is longer than 1, the first two elements to which fct is applied are the last two elements of the list.

Examples:

> (reduce (λ (a b) `(fct ,a ,b)) 'nil '(1))
1
> (reduce-left (λ (a b) `(fct ,a ,b)) 'nil '(1 2 3))
'(fct (fct 1 2) 3)
> (reduce-right (λ (a b) `(fct ,a ,b)) 'nil '(1 2 3))
'(fct 1 (fct 2 3))

procedure
((list:elementwise fct) lists ...) → list?
fct : procedure?
lists : list?

Equal to

(apply map proc lists)

procedure
(map&reduce fct combine init lsts ...) → an
  fct : procedure?
  combine : (-> any/c any/c any/c)
  init : any/c
  lsts : list?

Equivalent to:

(foldl combine init (apply map fct lsts))

without constructing the intermediate list. Note works like foldl and not like the reduce-left as defined above.

2.6.5 combinations of 2 elements🔗

procedure
(distinct-pairs lst) → (listof (cons/c any/c any/c))
lst : list?

Creates a list containing all distinct pairs of 2 elements in the list.

procedure
(map-distinct-pairs fct lst) → list?
  fct : (-> any/c any/c any/c)
  lst : list?
procedure
(for-each-distinct-pair fct lst) → void?
  fct : (-> any/c any/c any/c)
  lst : list?

Equivalent to using map or for-each as in

(map (λ (p) (f (car p) (cdr p))) (distinct-pairs lst))

without constructing the intermediate list.

2.6.6 set operations on list🔗

Operations on lists that are treated as sets. Due to the implementation, if set1 has duplicates, the result still might have duplicates.

procedure
(lset= is-equal? set1 set2) → boolean?
  is-equal? : (-> any/c any/c any/c)
  set1 : list?
  set2 : list?

Checks if two sets are the same, duplicates are ignored.

procedure
(lset-adjoin is-equal? e set1) → list?
  is-equal? : (-> any/c any/c any/c)
  e : any/c
  set1 : list?

Add an element to the set, if not yet present.

procedure
(lset-union is-equal? set1 set2) → list?
  is-equal? : (-> any/c any/c any/c)
  set1 : list?
  set2 : list?

Add all unique items from set2, to set1.

procedure
(lset-difference is-equal? set1 set2) → list?
  is-equal? : (-> any/c any/c any/c)
  set1 : list?
  set2 : list?

Remove all items from set2 from set1.

procedure
(lset-intersection is-equal? set1 set2) → list?
  is-equal? : (-> any/c any/c any/c)
  set1 : list?
  set2 : list?

Keep only the items that are both in set1 and set2.

2.6.7 other🔗

procedure
((fringe-smaller-than? n) expression) → (or/c #f integer?)
n : integer?
expression : any/c

Equivalent to:

(let ([len (length (flatten expr))])
(if (< len n) len #f))

But breaking early if the result is #f

procedure
(list-transpose lsts) → (listof list?)
lsts : (listof list?)

For lsts a list of n lists with (same) length m, return a new list T of m lists with length n so that (eq? (list-ref (list-ref lsts i) j) (list-ref (list-ref T j) i)).

procedure
(cons-if-necessary a b c) → (cons/c any/c any/c)
  a : any/c
  b : any/c
  c : (cons/c any/c any/c)

Returns a cons of a and b. If however (and (eq? a (car c)) (eq? b (cdr c))) it returns c.

procedure
(variable<? a b) → boolean?
a : symbol?
b : symbol?

Equal to symbol<?

contents ← prev up next →

1	Introduction
2	General
3	Kernel
4	Display

2.1	eq-properties
2.2	equals
2.3	equation-style-unifier
2.4	gjs-cselim
2.5	hashcons
2.6	list-utils
2.7	logic-utils
2.8	memoize
2.9	notes
2.10	permute
2.11	resource-limit
2.12	sets
2.13	stack-queue
2.14	table
2.15	weak

2.6.1	list sections
2.6.2	substitution
2.6.3	Count and search
2.6.4	map and fold
2.6.5	combinations of 2 elements
2.6.6	set operations on list
2.6.7	other