((section 2 "Outdated egg!" (p "This is an egg for CHICKEN 4, the unsupported old release.  You're almost certainly looking for " (int-link "/eggref/5/traversal" "the CHICKEN 5 version of this egg") ", if it exists.") (p "If it does not exist, there may be equivalent functionality provided by another egg; have a look at the " (link "https://wiki.call-cc.org/chicken-projects/egg-index-5.html" "egg index") ". Otherwise, please consider porting this egg to the current version of CHICKEN.") (tags "egg" "data") (toc) (p "This page is maintained in the package's " (link "https://github.com/abarbu/traversal" "github repository") ".")) (section 2 "Traversal" (p "This is a Chicken Scheme egg which contains various list and vector traversal functions. Many of the functions provided by this egg originate from Jeff Siskind's QobiScheme.") (section 3 "overall" (p "The final character of many of these functions denotes the compairson function being used. 'q' compares with 'eq?', 'v' compares with 'eqv?', 'e' with 'equal?', 'p' and the lack of a final character denotes that the function takes a user-provided predicate.") (p "The following documentation uses the following notation: 'l' list, 'n' number, 'v' vector, 'p' procedure (usually a predicate).") (p "Some of the functionality of this egg is provided by other eggs, like srfi-1, with different naming conventions.") (section 4 "lists" (def (sig (procedure "(countq x l)" (id countq)) (procedure "(countv x l)" (id countv)) (procedure "(counte x l)" (id counte)) (procedure "(countp p x l)" (id countp)) (procedure "(count-if p l)" (id count-if)) (procedure "(count-if-not p l)" (id count-if-not)))) (def (sig (procedure "(findq x l)" (id findq)) (procedure "(findv x l)" (id findv)) (procedure "(finde x l)" (id finde)) (procedure "(findp p x l)" (id findp)) (procedure "(find-if p l)" (id find-if)) (procedure "(find-if-not p l)" (id find-if-not)))) (def (sig (procedure "(positionq x l)" (id positionq)) (procedure "(positionv x l)" (id positionv)) (procedure "(positione x l)" (id positione)) (procedure "(position p l)" (id position)) (procedure "(positionp p x l)" (id positionp)) (procedure "(position-if p l)" (id position-if)) (procedure "(position-if-not p l)" (id position-if-not)) (procedure "(vector-positione val vector)" (id vector-positione)))) (def (sig (procedure "(remove-if p l)" (id remove-if)) (procedure "(remove-if-not p l)" (id remove-if-not)) (procedure "(removee x l)" (id removee)) (procedure "(removep p x l)" (id removep)) (procedure "(removeq x l)" (id removeq)) (procedure "(removev x l)" (id removev)))) (def (sig (procedure "(remove-duplicatesq l)" (id remove-duplicatesq)) (procedure "(remove-duplicatesv l)" (id remove-duplicatesv)) (procedure "(remove-duplicates p l)" (id remove-duplicates)) (procedure "(remove-duplicatese x l)" (id remove-duplicatese)))) (def (sig (procedure "(list-set! l i x)" (id list-set!)) (procedure "(list-insert l i x)" (id list-insert)) (procedure "(list-remove l i)" (id list-remove)) (procedure "(list-replace l i x)" (id list-replace)))) (def (sig (procedure "(equivalence-classesq x)" (id equivalence-classesq)) (procedure "(equivalence-classesv x)" (id equivalence-classesv)) (procedure "(equivalence-classes p x)" (id equivalence-classes)) (procedure "(equivalence-classese x)" (id equivalence-classese)) (procedure "(transitive-equivalence-classes p x)" (id transitive-equivalence-classes)))) (def (sig (procedure "(adjoinq x l)" (id adjoinq)) (procedure "(adjoinv x l)" (id adjoinv)) (procedure "(adjoin x l)" (id adjoin)) (procedure "(adjoinp p x l)" (id adjoinp)))) (def (sig (procedure "(rest l)" (id rest)) (procedure "(but-last l)" (id but-last)) (procedure "(sublist list start end)" (id sublist)) (procedure "(every-other list)" (id every-other)))) (def (sig (procedure "(take-until p l)" (id take-until)) (procedure "(drop-until p l)" (id drop-until))) (p "Misc list manipulation stuff.")) (def (sig (procedure "(group-by key l)" (id group-by))) (p "Find equivalence classes of the elements of l that are " (i "equal?") " given output of " (i "key") ".")) (def (sig (procedure "(sort list predicate key)" (id sort))) (p "Merge sort.")) (def (sig (procedure "(lexicographically<? <? =?)" (id lexicographically<?)) (procedure "(minimal-membersp <? =? l)" (id minimal-membersp)))) (def (sig (procedure "(unzip l)" (id unzip))) (p "Transposes lists.")))) (section 3 "creation" (def (sig (procedure "(enumerate n)" (id enumerate)) (procedure "(enumerate-vector n)" (id enumerate-vector))) (p "Produce a list or a vector containing 0 through n-1."))) (section 3 "assertions" (def (sig (procedure "(some p l)" (id some)) (procedure "(some-n p n)" (id some-n)) (procedure "(some-vector p v)" (id some-vector)) (procedure "(every-n p n)" (id every-n)) (procedure "(every-vector p v)" (id every-vector)) (procedure "(one p l . &rest)" (id one)) (procedure "(one-n p n)" (id one-n)) (procedure "(one-vector p v . &rest)" (id one-vector)))) (def (sig (procedure "(pairwise? p l)" (id pairwise?))) (p "Does p hold on each adjacent pair of elements in l."))) (section 3 "traversal" (def (sig (procedure "(for-each-n f n)" (id for-each-n)) (procedure "(for-each-n-decreasing f n)" (id for-each-n-decreasing)) (procedure "(map-n f n)" (id map-n)) (procedure "(map-n-vector f n)" (id map-n-vector)) (procedure "(for-each-from-a-up-to-b f a b)" (id for-each-from-a-up-to-b)) (procedure "(for-each-m-n f m n)" (id for-each-m-n)) (procedure "(for-each-m-n-indexed f m n)" (id for-each-m-n-indexed)) (procedure "(for-each-m-n-dec f m n)" (id for-each-m-n-dec)) (procedure "(map-m-n f m n)" (id map-m-n)) (procedure "(map-m-n-indexed f m n)" (id map-m-n-indexed)))) (def (sig (procedure "(for-each-vector f v . &rest)" (id for-each-vector)) (procedure "(map-vector f v . &rest)" (id map-vector))) (p "Like 'vector-map' but take an arbitrary number of vectors.")) (def (sig (procedure "(map-linear f start end n)" (id map-linear))) (p "Map linearly between 'start' and 'end' in 'n' steps.")) (def (sig (procedure "(reduce-n f i n)" (id reduce-n)) (procedure "(reduce-vector f i v)" (id reduce-vector)) (procedure "(map-reduce g i f l . ls)" (id map-reduce)) (procedure "(map-reduce-n g i f n)" (id map-reduce-n)) (procedure "(map-reduce-vector g i f v . vs)" (id map-reduce-vector)) (procedure "(map-reduce2 g i f l)" (id map-reduce2)) (procedure "(map-reduce3 g i f l1 l2)" (id map-reduce3))) (p "Reduces are left folds.")) (def (sig (procedure "(for-each-indexed f l)" (id for-each-indexed)) (procedure "(map-indexed f l)" (id map-indexed)) (procedure "(for-each-indexed-vector f v)" (id for-each-indexed-vector)) (procedure "(map-indexed-vector f v . &rest)" (id map-indexed-vector))) (p "Passes 'f' both the element and an offset into the list/vector.")) (def (sig (procedure "(map-medial f l key)" (id map-medial))) (p "'f' is passed each adjacent pair of elements in l after being sorted by the key. Key must return a number given each element of l.")) (def (sig (procedure "(all-pairs l)" (id all-pairs)) (procedure "(map-all-pairs f l)" (id map-all-pairs))) (p "'f' is passed each adjacent pair of elements in l.")) (def (sig (procedure "(memp p x l)" (id memp)) (procedure "(assp p x alist)" (id assp))) (p "Like memq and assq but take a predicate for comparison.")) (def (sig (procedure "(map-accum f i l)" (id map-accum))) (p "f will be passed the accumulator and each element of the list."))) (section 3 "sets" (def (sig (procedure "(set-unionq x y)" (id set-unionq)) (procedure "(set-unionv x y)" (id set-unionv)) (procedure "(set-union p x y)" (id set-union)) (procedure "(set-unione x y)" (id set-unione)) (procedure "(set-unionvt x y)" (id set-unionvt)))) (def (sig (procedure "(set-differenceq x y)" (id set-differenceq)) (procedure "(set-differencev x y)" (id set-differencev)) (procedure "(set-difference p x y)" (id set-difference)) (procedure "(set-differencee x y)" (id set-differencee)) (procedure "(set-differencevt x y)" (id set-differencevt)))) (def (sig (procedure "(set-intersectionq x y)" (id set-intersectionq)) (procedure "(set-intersectionv x y)" (id set-intersectionv)) (procedure "(set-intersection p x y)" (id set-intersection)) (procedure "(set-intersectione x y)" (id set-intersectione)) (procedure "(set-intersectionvt x y)" (id set-intersectionvt)))) (def (sig (procedure "(set-equalq? x y)" (id set-equalq?)) (procedure "(set-equalv? x y)" (id set-equalv?)) (procedure "(set-equale? x y)" (id set-equale?)) (procedure "(set-equal? p x y)" (id set-equal?)))) (def (sig (procedure "(subsetq? x y)" (id subsetq?)) (procedure "(subsetv? x y)" (id subsetv?)) (procedure "(subsete? x y)" (id subsete?)) (procedure "(subset? p x y)" (id subset?)) (procedure "(subsetvt? x y)" (id subsetvt?)))) (section 4 "rings" (def (sig (procedure "(ring-backward l)" (id ring-backward)) (procedure "(ring-forward l)" (id ring-forward)) (procedure "(ring-forward-between r a b)" (id ring-forward-between)) (procedure "(ring-forward-to l o)" (id ring-forward-to))) (p "These manipulate a list while treating it as a ring."))) (section 4 "minimizing and maximizing" (def (sig (procedure "(maximump l)" (id maximump)) (procedure "(minimump l)" (id minimump)) (procedure "(maximum p l)" (id maximum)) (procedure "(minimum p l)" (id minimum)) (procedure "(maximum-with-position l)" (id maximum-with-position)) (procedure "(minimum-with-position l)" (id minimum-with-position))) (p "p is a function that returns a number."))) (section 4 "math" (def (sig (procedure "(sum l)" (id sum)) (procedure "(sum p n)" (id sum)) (procedure "(sum p l)" (id sum)) (procedure "(product l)" (id product)) (procedure "(product p n)" (id product)) (procedure "(product p l)" (id product)))) (def (sig (procedure "(factorial n)" (id factorial)) (procedure "(choose n m)" (id choose))))) (section 4 "QobiScheme compatibility" (def (sig (procedure "(qfind x l)" (id qfind)) (procedure "(qcount x l)" (id qcount)) (procedure "(qposition x l)" (id qposition)) (procedure "(qremove x l)" (id qremove)) (procedure "(qremove-duplicates l)" (id qremove-duplicates)) (procedure "(qtopological-sort p l)" (id qtopological-sort)) (procedure "(qset-difference x y)" (id qset-difference)) (procedure "(qset-intersection x y)" (id qset-intersection)) (procedure "(qset-union x y)" (id qset-union)) (procedure "(qset-equal? x y)" (id qset-equal?)) (procedure "(qreduce f l i)" (id qreduce)) (procedure "(qreduce-vector f v i)" (id qreduce-vector)) (procedure "(qreduce-n f n i)" (id qreduce-n)) (procedure "(qmap-reduce g i f l . ls)" (id qmap-reduce)) (procedure "(qmap-reduce-n g i f n)" (id qmap-reduce-n)) (procedure "(qmap-reduce-vector g i f v . vs)" (id qmap-reduce-vector)) (procedure "(qequivalence-classes x)" (id qequivalence-classes)) (procedure "(qtransitive-equivalence-classesp p x)" (id qtransitive-equivalence-classesp)) (procedure "(qmaximum l)" (id qmaximum)) (procedure "(qminimum l)" (id qminimum)) (procedure "(qmaximump l p)" (id qmaximump)) (procedure "(qminimump l p)" (id qminimump)))))) (section 3 "License" (pre "  Copyright 1993-1995 University of Toronto. All rights reserved.\n  Copyright 1996 Technion. All rights reserved.\n  Copyright 1996 and 1997 University of Vermont. All rights reserved.\n  Copyright 1997-2001 NEC Research Institute, Inc. All rights reserved.\n  Copyright 2002-2013 Purdue University. All rights reserved.") (pre "  Contact Andrei Barbu at andrei@0xab.com.") (pre "  This program is free software: you can redistribute it and/or modify\n  it under the terms of the GNU Lesser General Public License as published by\n  the Free Software Foundation, either version 3 of the License, or\n  (at your option) any later version.\n  This program is distributed in the hope that it will be useful,\n  but WITHOUT ANY WARRANTY; without even the implied warranty of\n  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n  GNU Lesser General Public License for more details.\n  You should have received a copy of the GNU Lesser General Public License\n  along with this program.  If not, see http://www.gnu.org/licenses."))))