Previous: Evaluation Up: Contents Next: Macros

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