Arc: List manipulation

List manipulation

car list First element of list.	>(car '(1 2 3)) 1
cdr list Remainder of list.	>(cdr '(1 2 3)) (2 3)
caar list Equivalent to (car (car list)).	>(caar '((1 2) 3 4)) 1
cadr list Equivalent to (car (cdr list)).	>(cadr '((1 2) 3 4)) 3
cddr list Equivalent to (cdr (cdr list)). Note that cdar is not part of Arc.	>(cddr '((1 2) 3 4)) (4)
conswhen f x y Cons x and y if (f x) is true. Otherwise returns y.	>(conswhen (fn (_) (< (len _) 3)) '(1 2) '(3 4 5)) ((1 2) 3 4 5) >(conswhen (fn (_) (< (len _) 3)) '(1 2 3 4) '(3 4 5)) (3 4 5)
consif x list Cons x onto list if x is not nil.	>(consif 1 '(2 3)) (1 2 3) >(consif nil '(2 3)) (2 3)
firstn n list Returns the first n elements of list.	>(firstn 3 '(1 2)) (1 2) >(firstn 3 '(a b c d e)) (a b c)
nthcdr n list Returns list after skipping the first n elements.	>(nthcdr 0 '(1 2 3)) (1 2 3) >(nthcdr 2 '(1 2 3)) (3) >(nthcdr 10 '(1 2 3)) nil
last list Returns the last element of list.	>(last '(1 2 3)) 3
flat list [stringstoo] Flattens list into a list of atoms. Any nils are removed. If stringstoo is true, empty strings are removed, but flat will fail if the list contains any non-empty strings.	>(flat '(1 2 () (3 4 (5)))) (1 2 3 4 5)
rev list Reverses list.	>(rev '(1 2 3)) (3 2 1) >(rev '(1 (2 3) 4)) (4 (2 3) 1)
carif x Returns (car x) if x is a list, and returns x otherwise. This provides a 'safe' way to return the first element of something that may or may not be a list.	>(carif '(1 2)) 1 >(carif 3) 3
caris x val Tests if x is a list and (car x) is val.	>(caris '(1 2) 1) t >(caris 1 1) nil
intersperse x list Inserts x between elements of list. If list has fewer than 2 elements, there is no effect.	>(intersperse 1 '(a b (c d) e)) (a 1 b 1 (c d) 1 e) >(intersperse nil '(1 2 3)) (1 nil 2 nil 3)
split list pos Splits list into two lists at the given position, which must be between 1 and the length of the list.	>(split '(a b c) 0) ((a) (b c)) >(split '(a b c) 1) ((a) (b c)) >(split '(a b c) 2) ((a b) (c)) >(split '(a b c) 3) ((a b c) nil)
pair list [f] Splits list into pairs. By default, each pair is made into a list. If specified, function f is applied to each pair.	>(pair '(a b c d)) ((a b) (c d)) >(pair '(a b c d e)) ((a b) (c d) (e)) >(pair '(1 2 3 4) +) (3 7) >(pair '(10 2 3 40 50 6) max) (10 40 50)
tuples list [n] Splits list into groups of n. tuples is a generalization of pair.	>(tuples '(1 2 3 4 5) 1) ((1) (2) (3) (4) (5)) >(tuples '(1 2 3 4 5)) ((1 2) (3 4) (5)) >(tuples '(1 2 3 4 5) 3) ((1 2 3) (4 5))
join [list ...] Joins lists into one list.	>(join '(1 2) nil '(3 4)) (1 2 3 4)
list [arg ...] Creates a list of the arguments.	>(list 1 2 3) (1 2 3) >(list "a" '(1 2) 3) ("a" (1 2) 3)
range start end Creates a list of numbers from start to end in steps of 1. The last number is <= end.	>(range 0 10) (0 1 2 3 4 5 6 7 8 9 10) >(range 1.5 3.8) (1.5 2.5 3.5)
n-of n expr Evaluates expr n times and returns a list of the results.	>(n-of 5 "a") ("a" "a" "a" "a" "a") >(w/instring ins "abcdefg" (n-of 5 (readc ins))) (#\a #\b #\c #\d #\e)
adjoin elt list [test] Cons elt onto list unless (test elt y) is true for some y in list. By default, test is iso, so elt will be joined if it is not present in list.	>(adjoin 2 '(1 2 3)) (1 2 3) >(adjoin 2 '(1 3 5)) (2 1 3 5) >(adjoin 2 '(1 2 3) <) (1 2 3) >(adjoin 2 '(0 1 2) <) (2 0 1 2)
counts list [table] Counts how many times each element of list occurs. The results are returned as a table mapping from the element to the count. If a table is passed in, it will be updated.	>(counts '(b a n a n a)) #hash((n . 2) (a . 3) (b . 1)) >(let tl (table) (counts '(1 2) tl) (counts '(1 3) tl)) #hash((3 . 1) (1 . 2) (2 . 1))
commonest list Returns the element of list occurring most frequently, along with its count.	>(commonest '(b a n a n a)) (a 3) >(commonest nil) (nil 0)

Applying functions to lists

reduce f list Reduces list using f. Applies f to the first two elements of list. Then recursively applies f to that result and the next element of list.	>(reduce + '(1 2 3 4 5)) 15 >(reduce + '("a" "b" "c")) "abc" >(reduce / '(1 2 3)) 1/6
rreduce f list Reduces list using f in reverse. Applies f to the last two elements of list. Then recursively applies f to that result and the previous element of list.	>(rreduce + '(1 2 3 4 5)) 15 >(rreduce / '(1 2 3)) 3/2
firstn-that n f list Returns the first n elements of list for which predicate f is true.	>(firstn-that 3 odd '(1 2 3 4 5 6 7 8)) (1 3 5) >(firstn-that 3 odd '(2 4 6 8)) nil
most f list Returns the element of list for which rating function f returns the largest value.	>(most len '("cat" "bird" "dog")) "bird" >(most abs '(3 -10 5)) -10 >(most abs '(-1 1 -1)) -1
map1 f list Applies f to the elements of list. The results are cons'd together into a list.	>(map1 (fn (_) (list _ (* _ 10))) '(1 2 3)) ((1 10) (2 20) (3 30)) >(map1 cdr '((1) (2 3) (4 5))) (nil (3) (5))
mappend f [list ...] Maps f on the arguments, and then joins the results together. f must return a list. nil results are omitted.	>(mappend (fn (_) (list _ (* _ 10))) '(1 2 3)) (1 10 2 20 3 30) >(mappend cdr '((1) (2 3) (4 5))) (3 5)
reclist f list Recursively applies f to tail subsequences of list and returns the first true result. Returns nil if none.	>(reclist (fn (x) (prn x) nil) '(a b c)) (a b c) (b c) (c) nil >(reclist (fn (_) (if (is (len _) 2) _)) '(a b c)) (b c)
mem test list Tests elements of list. If test is true for an element, returns the remainder of the list from that point. test is either an element or a predicate.	>(mem (fn (_) (odd _)) '(2 4 5 6 7)) (5 6 7) >(mem 6 '(2 4 5 6 7)) (6 7)
trues f list Maps function f onto list and returns only the true (non-nil) values.	>(trues cdr '((1 2) (3) (4 5))) ((2) (5)) >(trues (fn (_) (if (odd _) (* 10 _))) '(1 2 3 4 5)) (10 30 50)

Sorting

mergesort compare list Destructively sorts list using the given comparison function. The sort is stable; if two elements compare as equal with compare, they will remain in the same order in the output. The original list is destroyed.	>(mergesort < '(3 0 10 -7)) (-7 0 3 10) >(mergesort (fn (a b) (< (len a) (len b))) '("horse" "dog" "elephant" "cat")) ("dog" "cat" "horse" "elephant")
merge compare list1 list2 Merges two sorted lists into a sorted list. The original lists must be ordered according to the predicate function compare.	>(merge < '(1 2 3 5) '(2 4 6)) (1 2 2 3 4 5 6) >(merge (fn (a b) (> (len a) (len b))) '("aaa" "b") '("cccc" "ddd" "ee")) ("cccc" "aaa" "ddd" "ee" "b")
insert-sorted compare elt list Creates a new list with elt inserted into the sorted list list. The original list must be sorted according to the comparison function. The original list is unmodified.	>(insert-sorted > 5 '(10 3 1)) (10 5 3 1) >(insert-sorted > 5 '(10 5 1)) (10 5 5 1)
insort (compare elt list) Insert elt into previously-sorted list, updating list.	>(let x '(2 4 6) (insort < 3 x) x) (2 3 4 6)
reinsert-sorted compare elt list Creates a new list with elt inserted into the sorted list list if it is not already present. The original list must be sorted according to the comparison function. The original list is unmodified.	>(reinsert-sorted > 5 '(10 3 1)) (10 5 3 1) >(reinsert-sorted > 5 '(10 5 1)) (10 5 1)
insortnew (compare elt list) Insert elt into previously-sorted list if it is not present, updating list.	>(let x '(2 4 6) (insortnew < 3 x) x) (2 3 4 6)
best compare list Returns the 'best' element of list as determined by function compare.	>(best > '(3 1 4 5 9 6)) 9
bestn n compare list Returns the first n elements of list when sorted according to comparison function compare.	>(bestn 3 > '(3 1 4 5 9 6)) (9 6 5) >(bestn 3 < '(3 1 4 5 9 6)) (1 3 4)
sort test seq Sorts the sequence (list or string) using the specified comparison function. The original sequence is unmodified.	>(sort < '(3 1 4 9 0)) (0 1 3 4 9) >(sort > "Test word") "wtsroedT "

Sequence manipulation

sref seq value index Sets indexed entry in a list, string, or hash table to the given value.	>(do (= x "abc") (sref x #\d 1) x) "adc" >(do (= x '(1 2 3)) (sref x #\d 1) x) (1 #\d 3)
count test seq Counts the number of elements of seq that satisfy test. test is an object or predicate. For a table, the elements are the values.	>(count #\a "banana") 3 >(count (fn (_) (odd _)) '(1 2 3 4 5)) 3
union f xs ys Takes union of sequence xs and ys. Predicate f is used to determine equality to filter out duplicates. xs and ys must both be lists or strings.	>(union is '(1 2 3) '(2 3 4)) (1 2 3 4) >(union is "ab" "banana") "abnn" >(union (fn (a b) (is (mod a 10) (mod b 10))) '(1 2 3) '(13 24 35)) (1 2 3 24 35)
len seq Computes the length of seq.	>(len "abc") 3 >(len '(1 2 3)) 3 >(len (obj a 1 b 2)) 2
len< seq n Tests if length of seq is less than n.	>(len< "abc" 4) t >(len< '(1 2 3) 4) t >(len< (obj a 1 b 2) 4) t
len> seq n Tests if length of seq is greater than n.	>(len> "abc" 4) nil >(len> '(1 2 3) 4) nil >(len> (obj a 1 b 2) 4) nil
dedup seq Returns contents of seq without duplicates. For a string, returns a list of characters. For a table, returns a list of values.	>(dedup '(1 2 3 2 1)) (1 2 3) >(dedup "abcba") (#\a #\b #\c) >(dedup (obj a 1 b 2 c 1)) (2 1)
single list Returns true if given a list of length one.	>(single '(1)) t >(single 1) nil >(single '()) nil
pos test seq [start] Returns the index of the first element of seq that satisfies test. seq is a list or string. test is either an object or predicate function. If start is given, testing starts at that element.	>(pos 'c '(a b c d)) 2 >(pos #\c "abcd") 2 >(pos #\c "abcdc" 3) 4 >(pos odd '(2 4 5 6 7)) 2 >(pos odd '(2 4 6)) nil
before t1 t2 seq [start] Tests if t1 is true before t2 in seq. seq is either a list or string. The tests are either objects or predicate functions. If start is given, search starts with the specified element.	>(before 4 odd '(2 4 1 3)) t >(before 4 odd '(2 3 4 1)) nil >(before #\a #\n "banana") t >(before #\a #\n "banana" 2) nil
random-elt seq Returns a random element from a list, or a random character from a string. It also works on a table with integer keys from 0 to n.	>(random-elt '(1 2 3)) 3 >(random-elt "abcd") #\c
mismatch s1 s2 Compares sequences and returns the position of the first mismatch (as determined by is). Returns nil if the sequences are identical.	>(mismatch "abcde" "abXde") 2 >(mismatch '(1 2 3) '(1 9 3)) 1 >(mismatch "abc" "abc") nil
find test seq Finds and returns the first element of seq that satisfies test (object or predicate). seq can be a list or string.	>(find odd '(2 3 4 5)) 3 >(find odd '(2 4 6)) nil >(find alphadig "...abc...") #\a
cut seq start [end] Returns subsequence of seq from start to end. If end is not specified, the remainder of seq is used. The seq can be a list or string.	>(cut "abcde" 2) "cde" >(cut "abcde" 2 4) "cd" >(cut '(a b c d) 2) (c d) >(cut '(a b c d) 2 4) (c d)
rem test seq Removes elements from seq that satisfy test. test is either a function or an object. seq is either a list or string.	>(rem odd '(1 2 3 4 5)) (2 4) >(rem 3 '(1 2 3 4 5)) (1 2 4 5) >(rem #\c "abcde") "abde" >(rem (fn (_) (in _ #\a #\b)) "abcde") "cde"
keep test seq Keeps elements from seq that satisfy test. test is either a function or an object. seq is either a list or string.	>(keep odd '(1 2 3 4 5)) (1 3 5) >(keep 3 '(1 2 3 4 5)) (3) >(keep #\c "abcde") "c" >(keep (fn (_) (in _ #\a #\b)) "abcde") "ab"
map f [seq ...] Applies f to the elements of the sequences, taking the first from each, the second from each, and so on. If there are n sequences, f must be a function accepting n arguments. The sequences can be lists or strings. If any sequence is a string, then f must return a character, and the result will be a string made up of the results from f. Otherwise, the result will be a list of the results from f. The sequences are processed up to the length of the shortest sequence. For a single list, map is the same as map1.	>(map (fn (a b c) (+ (* a 100) (* b 10) c)) '(1 2 3) '(4 5 6) '(7 8 9 10)) (147 258 369) >(map (fn (_) (list _ (* _ 10))) '(1 2 3)) ((1 10) (2 20) (3 30)) >(map cdr '((1) (2 3) (4 5))) (nil (3) (5)) >(map (fn (c n) (coerce (+ n (coerce c 'int)) 'char)) "abc" '(0 2 4)) "adg" >(map min "bird" "elephant") "bied"

Other

>(summing
i
true (map istrue '(1 nil nil t)))
2

rand-choice expr [...] Randomly choose one of the expressions.	>( and-choice "a" 42 '(1 2 3)) (1 2 3)
compare comparer scorer Creates a procedure on two values that applies scorer to each value, and then applies comparer to the two scores.	>(compare < len) #<procedure> pre> >((compare < len) "yz" "abc") t
only f Creates a procedure that will apply f to its arguments only if there are arguments.	>(only +) #<procedure> >((only +) 1 2 3) 6 >((only +)) nil
/a> accum accfn [body ...] Executes body. Inside body, each time cfn is called, its argument is pushed on a list that becomes the return value. Note that the list is in reverse order.	>(accum accfn (each x '(1 2 3) (accfn (* x 10)))) (30 20 10)
summing sumfn [body ...] Sums the number of times sumfn is called with a true argument in body. The sum is returned. The sumfn argument specifies the name under which the summing function is available to the body.

Copyright 2008 Ken Shirriff.