Previous: Evaluation Up: Contents Next: Macros

List manipulation

List manipulation

As lists are the key data structure in Arc, the language includes a large number of operations on lists and sequences. Some operations apply only to lists, while others apply to strings and tables.

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
Flattens list into a list of atoms. Any nils are removed.
 
>(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 no more than the length of the list.
 
>(split '(a b c) -1)
((a b) (a b c))

>(split '(a b c) 0)
(nil (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)
copylist args
Identical to list.
 
>(copylist '(1 2 3))
(1 2 3)

>(copylist '("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 3)
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((a . 3) (b . 1) (n . 2))

>(let tl (table)
  (counts '(1 2) tl)
  (counts '(1 3) tl))
#hash((1 . 2) (2 . 1) (3 . 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

Arc provides several ways of applying functions to the elements of a list.

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
retrieve n f list
Returns the first n elements of list for which predicate f is true. Renamed from firstn-that in arc3.
 
>(retrieve 3 odd '(1 2 3 4 5 6 7 8))
(1 3 5)

>(retrieve 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

Arc provides an efficient sorting operation based on merge sort. Sorting in Arc uses a compare predicate function that defines the sort order. Elements x and y are defined as sorted if (compare x y) is true. The compare function does not need to define a full order. That is, it is valid for (compare x y) and (compare y x) to both be true. In this case, mergesort is stable, and will preserve the existing order of the elements.

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

These operations act on lists, strings, or hash tables.

sref seq value index
Sets indexed entry in a list, string, or hash table to the given value.
 
>(let x (copy "abc")  ; make the string literal mutable
    (sref x #\d 1) x)
"adc"

>(do
    (= x '(1 2 3))
    (sref x 4 1) x)
(1 4 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))
((a 1) (b 2) (c 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
rand-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. Renamed from random-elt in arc3.
 
>(rand-elt '(1 2 3))
2

>(rand-elt "abcd")
#\d
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"
sum f seq
Applies f to the elements of the sequence and sums the results. New in arc3.
 
>(sum int "abc")
294

>(sum log '(1 2 3))
1.791759469228055

>(sum cadr (obj a 1 b 2 c 3))
6
get index
Generates a function to get the element referenced by index; the function can be applied to a table. This is useful for mapping, for instance. (It can also be applied to functions, not jus sequences.) New in arc3.
 
>(map get.2 '((a b c) (1 2 3) (p q r)))
(c 3 r)

>(get!b (obj a 10 b 20))
20

>(get.42 log)
3.7376696182833684

Other

rand-choice expr [...]
Randomly choose one of the expressions.
 
>(rand-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: compare>

>((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>

>((only +) 1 2 3)
6

>((only +))
nil
accum accfn [body ...]
Executes body. Inside body, each time accfn is called, its argument is pushed on a list that becomes the return value.
 
>(accum accfn (each x '(1 2 3) (accfn (* x 10))))
(10 20 30)
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.
 
>(summing istrue (map istrue '(1 nil nil t)))
2

Copyright 2008 Ken Shirriff.