list.tem

(page "List manipulation"
(newtable "List manipulation"
  (text "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.")

  (op car "list" "First element of <code>list</code>." 
    (tests "(car '(1 2 3))")) 
  (op cdr "list" "Remainder of <code>list</code>." 
    (tests "(cdr '(1 2 3))")) 
(def caar "list" "Equivalent to <code>(car (car list))</code>." (tests (caar '((1 2) 3 4))))
(def cadr "list" "Equivalent to <code>(car (cdr list))</code>." (tests (cadr '((1 2) 3 4))))
(def cddr "list" "Equivalent to <code>(cdr (cdr list))</code>.  Note that <code>cdar</code> is not part of Arc." (tests (cddr '((1 2) 3 4))))
(mac conswhen "f x y" "Cons <code>x</code> and <code>y</code> if <code>(f x)</code> is true.  Otherwise returns <code>y</code>."
(tests (conswhen [< (len _) 3] '(1 2) '(3 4 5))
(conswhen [< (len _) 3] '(1 2 3 4) '(3 4 5))))
(def consif "x list" "Cons <code>x</code> onto <code>list</code> if <code>x</code> is not <code>nil</code>." (tests (consif 1 '(2 3)) (consif nil '(2 3))))
(def firstn "n list" "Returns the first <code>n</code> elements of <code>list</code>." (tests (firstn 3 '(1 2)) (firstn 3 '(a b c d e))))
(def nthcdr "n list" "Returns <code>list</code> after skipping the first <code>n</code> elements." (tests (nthcdr 0 '(1 2 3)) (nthcdr 2 '(1 2 3)) (nthcdr 10 '(1 2 3))))
(def last "list" "Returns the last element of <code>list</code>." (tests (last '(1 2 3))))
(def flat "list" "Flattens <code>list</code> into a list of atoms.  Any <code>nil</code>s are removed." (tests (flat '(1 2 () (3 4 (5))))
))
(def rev "list" "Reverses <code>list</code>." (tests (rev '(1 2 3)) (rev '(1 (2 3) 4))))
(def carif "x" "Returns <code>(car x)</code> if <code>x</code> is a list, and returns <code>x</code> otherwise.  This provides a 'safe' way to return the first element of something that may or may not be a list." (tests (carif '(1 2)) (carif 3)))
(def predicate caris "x val" "Tests if <code>x</code> is a list and <code>(car x)</code> is <code>val</code>." (tests (caris '(1 2) 1) (caris 1 1)))
(def intersperse "x list" "Inserts <code>x</code> between elements of <code>list</code>.  If <code>list</code> has fewer than 2 elements, there is no effect."
(tests (intersperse 1 '(a b (c d) e)) (intersperse nil '(1 2 3))))
(def split "list pos" "Splits <code>list</code> into two lists at the given position, which must be no more than the length of the list." (tests
(split '(a b c) -1)
(split '(a b c) 0)
(split '(a b c) 1)
(split '(a b c) 2)
(split '(a b c) 3)
))
(def pair "list [f]" "Splits <code>list</code> into pairs.  By default, each pair is made into a list.  If specified, function f is applied to each pair." (tests (pair '(a b c d)) (pair '(a b c d e)) (pair '(1 2 3 4) +) (pair '(10 2 3 40 50 6) max)))
(def tuples "list [n]" "Splits <code>list</code> into groups of <code>n</code>. <code>tuples</code> is a generalization of <code>pair</code>." (tests (tuples '(1 2 3 4 5) 1) (tuples '(1 2 3 4 5)) (tuples '(1 2 3 4 5) 3)))
(def join "[list ...]" "Joins lists into one list." (tests (join '(1 2) nil '(3 4))))
(def list "[arg ...]" "Creates a list of the arguments." (tests (list 1 2 3) (list "a" '(1 2) 3)))
(def copylist "args" "Identical to list." (tests (copylist '(1 2 3)) (copylist '("a" (1 2) 3))))
(def range "start end" "Creates a list of numbers from start to end in steps of 1.  The last number is <= end." (tests (range 0 10) (range 1.5 3.8)))
(mac n-of "n expr" "Evaluates <code>expr</code> <code>n</code> times and returns a list of the results." (tests (n-of 5 "a") (w/instring ins "abcdefg" (n-of 5 (readc ins)))))
(def adjoin "elt list [test]" "Cons <code>elt</code> onto <code>list</code> unless <code>(test elt y)</code> is true for some <code>y</code> in <code>list</code>.  By default, <code>test</code> is <code>iso</code>, so <code>elt</code> will be joined if it is not present in <code>list</code>." (tests (adjoin 2 '(1 2 3)) (adjoin 2 '(1 3 5)) (adjoin 2 '(1 2 3) <) (adjoin 2 '(0 1 2) <)))
(def destructive counts "list [table]" "Counts how many times each element of <code>list</code> 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." (tests (counts '(b a n a n a))
"(let tl (table)
  (counts '(1 2) tl)
  (counts '(1 3) tl))"))
(def commonest "list" "Returns the element of <code>list</code> occurring most frequently, along with its count." (tests (commonest '(b a n a n a)) (commonest nil)))
)
(newtable "Applying functions to lists"
(text "Arc provides several ways of applying functions to the elements of a list.")
(def reduce "f list" "Reduces <code>list</code> using <code>f</code>.  Applies <code>f</code> to the first two elements of <code>list</code>.  Then recursively applies <code>f</code> to that result and the next element of <code>list</code>." (tests (reduce + '(1 2 3 4 5)) (reduce + '("a" "b" "c")) (reduce / '(1 2 3))))
(def rreduce "f list" "Reduces <code>list</code> using <code>f</code> in reverse.  Applies <code>f</code> to the last two elements of <code>list</code>.  Then recursively applies <code>f</code> to that result and the previous element of <code>list</code>." (tests (rreduce + '(1 2 3 4 5)) (rreduce / '(1 2 3))))
(def retrieve "n f list" "Returns the first <code>n</code> elements of <code>list</code> for which predicate <code>f</code> is true.  Renamed from firstn-that in arc3." (tests (retrieve 3 odd '(1 2 3 4 5 6 7 8)) (retrieve 3 odd '(2 4 6 8))))
(def most "f list" "Returns the element of <code>list</code> for which rating function <code>f</code> returns the largest value." (tests (most len '("cat" "bird" "dog")) (most abs '(3 -10 5)) (most abs '(-1 1 -1))))
(def map1 "f list" "Applies <code>f</code> to the elements of <code>list</code>.  The results are cons'd together into a list."
(tests (map1 [list _ (* _ 10)] '(1 2 3)) (map1 cdr '((1) (2 3) (4 5)))))
(def mappend "f [list ...]" "Maps <code>f</code> on the arguments, and then joins the results together.  <code>f</code> must return a list.  <code>nil</code> results are omitted."
(tests (mappend [list _ (* _ 10)] '(1 2 3)) (mappend cdr '((1) (2 3) (4 5)))))
(def reclist "f list" "Recursively applies f to tail subsequences of <code>list</code> and returns the first true result.  Returns <code>nil</code> if none." (tests (reclist (fn (x) (prn x) nil) '(a b c)) (reclist [if (is (len _) 2) _] '(a b c))))
(def mem "test list" "Tests elements of list.  If test is true for an element, returns the remainder of the list from that point. <code>test</code> is either an element or a predicate." (tests (mem [odd _] '(2 4 5 6 7)) (mem 6 '(2 4 5 6 7))))
(def trues "f list" "Maps function <code>f</code> onto <code>list</code> and returns only the true (non-nil) values." (tests (trues cdr '((1 2) (3) (4 5))) (trues [if (odd _) (* 10 _)] '(1 2 3 4 5))))

)
(newtable "Sorting"
(text "Arc provides an efficient sorting operation based on merge sort.  Sorting in Arc uses a <code>compare</code> predicate function that defines the sort order.  Elements <code>x</code> and <code>y</code> are defined as sorted if <code>(compare x y)</code> is true.  The <code>compare</code> function does not need to define a full order.  That is, it is valid for <code>(compare x y)</code> and <code>(compare y x)</code> to both be true.  In this case, <code>mergesort</code> is stable, and will preserve the existing order of the elements.")
(def destructive mergesort "compare list" "Destructively sorts <code>list</code> using the given comparison function.  The sort is stable; if two elements compare as equal with <code>compare</code>, they will remain in the same order in the output.  The original list is destroyed." (tests
(mergesort < '(3 0 10 -7))
"(mergesort (fn (a b) (< (len a) (len b)))
            '(\"horse\" \"dog\" \"elephant\" \"cat\"))"))
(def destructive merge "compare list1 list2" "Merges two sorted lists into a sorted list.  The original lists must be ordered according to the predicate function <code>compare.</code>" (tests (merge < '(1 2 3 5) '(2 4 6))
"(merge (fn (a b) (> (len a) (len b)))
  '(\"aaa\" \"b\") '(\"cccc\" \"ddd\" \"ee\"))"
))
(def insert-sorted "compare elt list" "Creates a new list with <code>elt</code> inserted into the sorted list <code>list</code>.  The original list must be sorted according to the comparison function.  The original list is unmodified." (tests (insert-sorted > 5 '(10 3 1)) (insert-sorted > 5 '(10 5 1))))
(mac destructive insort "(compare elt list)" "Insert <code>elt</code> into previously-sorted <code>list</code>, updating <code>list</code>." (tests (let x '(2 4 6) (insort < 3 x) x)))
(def reinsert-sorted "compare elt list" "Creates a new list with <code>elt</code> inserted into the sorted list <code>list</code> if it is not already present.  The original list must be sorted according to the comparison function.  The original list is unmodified." (tests (reinsert-sorted > 5 '(10 3 1)) (reinsert-sorted > 5 '(10 5 1))))
(mac destructive insortnew "(compare elt list)" "Insert <code>elt</code> into previously-sorted <code>list</code> if it is not present, updating <code>list</code>." (tests (let x '(2 4 6) (insortnew < 3 x) x)) (let x '(2 4 6) (insortnew < 2 x) x))
(def best "compare list" "Returns the 'best' element of <code>list</code> as determined by function <code>compare</code>." (tests (best > '(3 1 4 5 9 6))))
(def bestn "n compare list" "Returns the first <code>n</code> elements of <code>list</code> when sorted according to comparison function <code>compare</code>." (tests (bestn 3 > '(3 1 4 5 9 6)) (bestn 3 < '(3 1 4 5 9 6))))
(def sort "test seq" "Sorts the sequence (list or string) using the specified comparison function.  The original sequence is unmodified." (tests (sort < '(3 1 4 9 0)) (sort > "Test word")))
)

(newtable "Sequence manipulation"
(text "These operations act on lists, strings, or hash tables.")
  (op destructive sref "seq value index" "Sets indexed entry in a list, string, or hash table to
  the given value." 
    (tests "(let x (copy \"abc\")  ; <span style='color:blue'>make the string literal mutable</span>
    (sref x #\\d 1) x)"
       "(do
    (= x '(1 2 3))
    (sref x 4 1) x)"))
(def count "test seq" "Counts the number of elements of <code>seq</code> that satisfy <code>test</code>.  <code>test</code> is an object or predicate.  For a table, the elements are the values." (tests (count #\a "banana") (count [odd _] '(1 2 3 4 5))) (count [odd _] (obj a 1 b 2 c 3)))
(def union "f xs ys" "Takes union of sequence <code>xs</code> and <code>ys</code>.  Predicate <code>f</code> is used to determine equality to filter out duplicates. <code>xs</code> and <code>ys</code> must both be lists or strings."  (tests
(union is '(1 2 3) '(2 3 4))
(union is "ab" "banana")
(union (fn (a b) (is (mod a 10) (mod b 10))) '(1 2 3) '(13 24 35))
))
  (op len "seq" "Computes the length of <code>seq</code>."
    (tests (len "abc") (len '(1 2 3)) (len (obj a 1 b 2))) )
(def predicate  len< "seq n" "Tests if length of <code>seq</code> is less than <code>n</code>."
(tests (len< "abc" 4) (len< '(1 2 3) 4) (len< (obj a 1 b 2) 4) ))
(def predicate len> "seq n" "Tests if length of <code>seq</code> is greater than <code>n</code>."
(tests (len> "abc" 4) (len> '(1 2 3) 4) (len> (obj a 1 b 2) 4) ))
(def dedup "seq" "Returns contents of <code>seq</code> without duplicates.  For a string, returns a list of characters.  For a table, returns a list of values." (tests (dedup '(1 2 3 2 1)) (dedup "abcba") (dedup (obj a 1 b 2 c 1))))
(def predicate single "list" "Returns true if given a list of length one."
(tests (single '(1)) (single 1) (single '())))
(def pos "test seq [start]" "Returns the index of the first element of <code>seq</code> that satisfies <code>test</code>.  <code>seq</code> is a list or string</code>.  <code>test</code> is either an object or predicate function.  If <code>start</code> is given, testing starts at that element." (tests (pos 'c '(a b c d)) (pos #\c "abcd") (pos #\c "abcdc" 3) (pos odd '(2 4 5 6 7)) (pos odd '(2 4 6))))
(def predicate before "t1 t2 seq [start]" "Tests if <code>t1</code> is true before <code>t2</code> in <code>seq</code>.  <code>seq</code> is either a list or string.  The tests are either objects or predicate functions.  If <code>start</code> is given, search starts with the specified element." (tests (before 4 odd '(2 4 1 3)) (before 4 odd '(2 3 4 1)) (before #\a #\n "banana") (before #\a #\n "banana" 2)))
(def 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." (tests (rand-elt '(1 2 3)) (rand-elt "abcd")))
(def mismatch "s1 s2" "Compares sequences and returns the position of the
first mismatch (as determined by <code>is</code>).  Returns <code>nil</code> if
the sequences are identical." (tests (mismatch "abcde" "abXde") (mismatch '(1
2 3) '(1 9 3)) (mismatch "abc" "abc")))
(def find "test seq" "Finds and returns the first element of <code>seq</code> that satisfies <code>test</code> (object or predicate).  <code>seq</code> can be a list or string." (tests (find odd '(2 3 4 5)) (find odd '(2 4 6)) (find alphadig "...abc...")))
(def cut "seq start [end]" "Returns subsequence of <code>seq</code> from <code>start</code> to <code>end</code>.  If <code>end</code> is not specified,  the remainder of <code>seq</code> is used.  The seq can be a list or string." (tests (cut "abcde" 2) (cut "abcde" 2 4) (cut '(a b c d) 2) (cut '(a b c d) 2 4)))
(def rem "test seq" "Removes elements from <code>seq</code> that satisfy <code>test</code>.  <code>test</code> is either a function or an object.  <code>seq</code> is either a list or string." (tests (rem odd '(1 2 3 4 5)) (rem 3 '(1 2 3 4 5)) (rem #\c "abcde") (rem [in _ #\a #\b] "abcde") ))
(def keep "test seq" "Keeps elements from <code>seq</code> that satisfy <code>test</code>.  <code>test</code> is either a function or an object.  <code>seq</code> is either a list or string." (tests (keep odd '(1 2 3 4 5)) (keep 3 '(1 2 3 4 5)) (keep #\c "abcde") (keep [in _ #\a #\b] "abcde") ))
(def map "f [seq ...]" "Applies <code>f</code> to the elements of the sequences, taking the first from each, the second from each, and so on.  If there are <code>n</code> sequences, <code>f</code> must be a function accepting <code>n</code> arguments.  The sequences can be lists or strings.  If any sequence is a string, then <code>f</code> must return a character, and the result will be a string made up of the results from <code>f</code>.  Otherwise, the result will be a list of the results from <code>f</code>.  The sequences are processed up to the length of the shortest sequence.  For a single list, <code>map</code> is the same as <code>map1</code>."
(tests
 "(map (fn (a b c) (+ (* a 100) (* b 10) c))
  '(1 2 3) '(4 5 6) '(7 8 9 10))"

(map [list _ (* _ 10)] '(1 2 3)) (map cdr '((1) (2 3) (4 5)))
(map (fn (c n) (coerce (+ n (coerce c 'int)) 'char)) "abc" '(0 2 4))
(map min "bird" "elephant")))
(def sum "f seq" "Applies f to the elements of the sequence and sums the results.  New in arc3." (tests (sum int "abc") (sum log '(1 2 3)) (sum cadr (obj a 1 b 2 c 3))))

(def 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."
(tests (map get.2 '((a b c) (1 2 3) (p q r))) (get!b (obj a 10 b 20)) (get.42 log)))
)
(newtable "Other"
(mac rand-choice "expr [...]" "Randomly choose one of the expressions." (tests (rand-choice "a" 42 '(1 2 3))))
(def compare "comparer scorer" "Creates a procedure on two values that applies <code>scorer</code> to each value, and then applies <code>comparer</code> to the two scores. " (tests (compare < len) ((compare < len) "yz" "abc")))
(def only "f" "Creates a procedure that will apply <code>f</code> to its arguments only if there are arguments." (tests (only +) ((only +) 1 2 3) ((only +))))

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