listopia
2021-04-11
List manipulation library
Listopia
List manipulation library inspired by Haskell package Data.List
Usage
(:import-from :listopia :name)
or
(:use :cl :listopia) (:shadowing-import-from :listopia :and :break :find :last :map :or)
Installation
(ql:quickload :listopia)
Basic functions
head (list &optional (default nil))
Extract the first element of a list. If list is empty, returns DEFAULT value.
(head '(1 2 3)) ;; => 1 (head '(1)) ;; => 1 (head '() 666) ;; => 666
last (list &optional (default nil))
Extract the last element of a list. If list is empty, returns DEFAULT value.
(last '(1 2 3)) ;; => 3 (last '(1)) ;; => 1 (last '() 666) ;; => 666
tail (list &optional (default nil))
Extract the elements after the head of a list. If list is empty, returns DEFAULT value.
(tail '(1 2 3)) ;; => '(2 3) (tail '(1)) ;; => '() (tail '() 666) ;; => 666
init (list &optional (default nil))
Return all the elements of a list except the last one. If list is empty, returns DEFAULT value.
(init '(1 2 3)) ;; => '(1 2) (init '(1)) ;; => '() (init '() 666) ;; => 666
uncons (list &optional (default nil))
Decompose a list into its head and tail. If the list is empty, returns DEFAULT. If the list is non-empty, returns '(x, xs), where x is the head of the list and xs its tail.
(uncons '(1 2 3)) ;; => '(1 (2 3)) (uncons '(1)) ;; => '(1 ()) (uncons '() 666) ;; => 666
List transformations
map (fn list)
Result - is the list obtained by applying FN to each element of LIST.
(map #'1+ '(1 2 3)) ;; => '(2 3 4) (map #'1+ '()) ;; => nil
intersperse (sep lisp)
The intersperse
function takes an element and a list and 'intersperses' that element between the elements of the list.
(intersperse 0 '(1 2 3)) ;; => '(1 0 2 0 3) (intersperse "," '("1" "2" "3")) ;; => '("1" "," "2" "," "3") (intersperse 0 '()) ;; => nil
intercalate (sep list)
(intercalate sep list)
is equivalent to (concat (intersperse sep list))
. It inserts the list SEP in between the lists in LIST and concatenates the result.
(intercalate '(0) '((1) (2) (3))) ;; => '(1 0 2 0 3) (intercalate '(0) '((1) (2 3) (4 5 6))) ;; => '(1 0 2 3 0 4 5 6) (intercalate '(0) '()') ;; => nil
Reducing lists (folds)
foldl (fn init-val list)
Left-associative fold of a list.
(foldl (lambda (acc x) (append acc (list (1+ x))) '(1 2) '(2 3 4))) ;; => '(1 2 3 4 5) (foldl (lambda (acc x) (cons x acc)) '() '(1 2 3)) ;; => '(3 2 1) (foldl (lambda (acc x) (cons x acc)) '() '()) ;; => '()
foldl1 (fn list)
A variant of foldl
that has no base case, and thus may only be applied to non-empty lists.
(foldl1 #'+ '(1 2 3)) ;; => 6 (foldl1 #'list '(1 2 3 4)) ;; => '(((1 2) 3) 4)
foldr (fn init-val list)
Right-associative fold of a list.
(foldr (lambda (x acc) (append acc (list (1+ x))) '(1 2) '(4 3 2))) ;; => '(1 2 3 4 5) (foldr (lambda (x acc) (cons x acc)) '() '(1 2 3)) ;; => '(1 2 3) (foldr (lambda (x acc) (cons x acc)) '() '()) ;; => '()
foldr1 (fn list)
A variant of foldr
that has no base case, and thus may only be applied to non-empty lists.
(foldr1 #'+ '(1 2 3)) ;; => 6 (foldr1 #'list '(1 2 3 4)) ;; => '(1 (2 (3 4)))
Special folds
concat (list)
The concatenation of all the elements of a container of lists.
(concat '((1) (2 3) (4 5 6))) ;; => '(1 2 3 4 5 6) (concat '((1)) ;; => '(1) (concat '(() ()) ;; => '()
concat-map (fn list)
Map a function over all the elements of a container and concatenate the resulting lists.
(concat-map #'list '(1 2 3)) ;; => '(1 2 3) (concat-map (lambda (x) (list x x)) '(1 2 3)) ;; => '(1 1 2 2 3 3) (concat-map #'null '()) ;; => NIL
and (list)
and
returns the conjunction of values in LIST.
(and '(t t)) ;; => t (and '(t nil)) ;; => nil (and '()) ;; => t
or (list)
or
returns the disjunction of values in LIST.
(or '(t nil t)) ;; => t (or '(nil nil nil)) ;; => nil (or '()) ;; => nil
any (fn list)
Determines whether any element of the list satisfies the predicate.
(any #'numberp '("1" "2" 3)) ;; => t (any #'numberp '()) ;; => nil
all (fn list)
Determines whether all elements of the LIST satisfy the predicate.
(all #'numberp '(1 2 3)) ;; => t (all #'numberp '(1 "2" 3)) ;; => nil (all #'numberp '()) ;; => t
sum (list)
The sum
function computes the sum of the numbers of a LIST.
(sum '(1 2 3)) ;; => 6 (sum '()) ;; => 0
product (list)
The product
function computes the product of the numbers of a LIST.
(product '(1 2 3)) ;; => 6 (product '()) ;; => 1
maximum (list)
The largest element of a non-empty LIST.
(maximum '(1 2 3 4 5)) ;; => 5 (maximum '(1 2 3.0)) ;; => 3.0
minimum (list)
The least element of a non-empty LIST.
(minimum '(1 2 3 4 5)) ;; => 1 (minimum '(1.0 2 3)) ;; => 1.0
Building lists
Scans
scanl (fn init-value list)
scanl
is similar to foldl
, but returns a list of successive reduced values from the left:
(scanl fn init '(x1 x2 ...)) == (list init (fn init x1) (fn (fn init x1) x2) ...)
(scanl #'+ 1 '(2 3 4)) ;; => '(1 3 6 10) (scanl #'+ 1 '()) ;; => '(1)
scanl1 (fn list)
scanl1
is a variant of scanl
that has no starting value argument.
(scanl1 #'+ '(1 2 3 4)) ;; => '(1 3 6 10) (scanl1 #'+ '()) ;; => nil
scanr (fn init-value list)
scanr
is the right-to-left dual of scanl
.
(scanr #'+ 1 '(2 3 4)) ;; => '(10 8 5 1) (scanr #'+ 1 '()) ;; => '(1)
scanr1 (fn list)
scanr1
is a variant of scanr
that has no starting value argument.
(scanr1 #'+ '(2 3 4 1)) ;; => '(10 8 5 1) (scanr1 #'+ '(5 4 3 2 1)) ;; => '(15 10 6 3 1) (scanr1 #'+ '()) ;; => nil
Accumulating maps
map-accum-l (fn init-val list)
map-accum-l
applies a function to each element of a LIST, passing an accumulating parameter from left to right, and returning a final value of this accumulator together with the new structure.
(map-accum-l (lambda (acc x) (list acc (+ x acc))) 1 '(1 2 3)) ;; => '(1 (2 3 4)) (map-accum-l (lambda (acc x) (list (1+ acc) (+ x acc))) 1 '(1 2 3)) ;; => '(4 (2 4 6))
map-accum-r (fn init-val list)
map-accum-r
applies a function to each element of a LIST, passing an accumulating parameter from right to left, and returning a final value of this accumulator together with the new structure.
(map-accum-r (lambda (acc x) (list acc (+ x acc))) 1 '(1 2 3)) ;; => '(1 (2 3 4)) (map-accum-r (lambda (acc x) (list (1+ acc) (+ x acc))) 1 '(1 2 3)) ;; => '(4 (4 4 4))
Infinite lists
iterate (fn init-val)
(iterate fn val)
returns an list of repeated applications of fn to val:
(iterate f x) == (list x (f x) (f (f x)) ...)
(take 4 (iterate #'1+ 0)) ;; => '(0 1 2 3)' (take 0 (iterate #'1+ 0)) ;; => nil
repeat (init-val)
(repeat x)
is an list, with x the value of every element.
(take 4 (repeat 1)) ;; => '(1 1 1 1) (take 2 (repeat :foo)) ;; => '(:foo :foo) (take 0 (repeat :foo)) ;; => nil
replicate (size init-val)
(replicate n x)
is a list of length n with x the value of every element.
(replicate 4 1) ;; => '(1 1 1 1) (replicate 2 :foo) ;; => '(:foo :foo) (replicate 0 :foo) ;; => nil
cycle (list)
cycle
ties a finite list into a circular one, or equivalently, the infinite repetition of the original list. It is the identity on infinite lists.
(take 5 (cycle '(1 2 3))) ;; => '(1 2 3 1 2) (take 0 (cycle '(1 2 3))) ;; => nil
Unfolding
unfoldr (fn init-val)
The unfoldr
function is a dual to foldr
: while foldr
reduces a list to a summary value, `unfoldr`` builds a list from a seed value. The function takes the element and returns NIL if it is done producing the list or returns '(a b), in which case, a is a prepended to the list and b is used as the next element in a recursive call.
(unfoldr (lambda (x) (if (= x 0) nil (list x (1- x)))) 10) ;; => '(10 9 8 7 6 5 4 3 2 1) (unfoldr (lambda (x) (if (= x 6) nil (list (expt 2 x) (1+ x)))) 1) ;; => '(2 4 8 16 32)
Sublists
Extracting sublists
take (count list)
(take n xs)
returns the prefix of xs of length n, or xs itself if n > length xs.
(take 3 '(1 2 3 4 5)) ;; => '(1 2 3) (take 3 '(1 2)) ;; => '(1 2) (take 3 '()) ;; => nil (take -1 '(1 2)) ;; => nil (take 0 '(1 2)) ;; => nil
This function maybe use with infinite lists.
(take 4 (cycle '(1 2 3))) ;; => '(1 2 3 1) (take 4 (iterate #'1+ 0)) ;; => '(0 1 2 3) (take 4 (repeat 1)) ;; => '(1 1 1 1)
drop (count list)
(drop n xs)
returns the suffix of xs after the first n elements, or NIL if n > length xs.
(drop 3 '(1 2 3 4 5)) ;; => '(4 5) (drop 3 '(1 2)) ;; => nil (drop 3 '()) ;; => nil (drop -1 '(1 2)) ;; => '(1 2) (drop 0 '(1 2)) ;; => '(1 2)
split-at (count list)
(split-at n xs)
returns a list where first element is xs prefix of length n and second element is the remainder of the list.
(split-at 3 '(1 2 3 4 5)) ;; => '((1 2 3) (4 5)) (split-at 1 '(1 2 3) ;; => '((1) (2 3)) (split-at 3 '(1 2 3) ;; => '((1 2 3) nil) (split-at 4 '(1 2 3) ;; => '((1 2 3) ()) (split-at 0 '(1 2 3) ;; => '(nil (1 2 3)) (split-at -1 '(1 2 3) ;; => '(nil (1 2 3))
take-while (pred list)
take-while
, applied to a predicate PRED and a LIST, returns the longest prefix (possibly empty) of LIST of elements that satisfy PRED.
(take-while #'evenp '(1 2 3 4)) ;; => '() (take-while #'evenp '(2 4 5 6)) ;; => '(2 4)
drop-while (pred list)
(drop-while p xs)
returns the suffix remaining after (take-while p xs)
.
(drop-while #'numberp '(1 2 3 nil nil 1 2 3)) ;; => '(nil nil 1 2 3) (drop-while #'numberp '(1 2 3)) ;; => '() (drop-while #'stringp '(1 2 3)) ;; => '(1 2 3)
drop-while-end (pred list)
The drop-while-end
function drops the largest suffix of a list in which the given predicate holds for all elements.
(drop-while-end #'numberp '("foo" "bar" 1 2 3)) ;; => '("foo" "bar") (drop-while-end #'numberp '("foo" 1 2 3 "bar")) ;; => '("foo" 1 2 3 "bar") (drop-while-end #'numberp '(1 2 3)) ;; => '()
span (pred list)
span
, applied to a predicate PRED and a LIST, returns a list where first element is longest prefix (possibly empty) of LIST of elements that satisfy PRED and second element is the remainder of the list.
(span (lambda (x) (< x 3)) '(1 2 3 4 1 2 3 4)) ;; => '((1 2) (3 4 1 2 3 4)) (span (lambda (x) (< x 9)) '(1 2 3)) ;; => '((1 2 3) ()) (span (lambda (x) (< x 0)) '(1 2 3)) ;; => '(() (1 2 3))
break (pred list)
break
, applied to a predicate PRED and a LIST, returns a list where first element is longest prefix (possibly empty) of LIST of elements that do not satisfy PRED and second element is the remainder of the list
(break (lambda (x) (> x 3)) '(1 2 3 4 1 2 3 4)) ;; => '((1 2 3) (4 1 2 3 4)) (break (lambda (x) (< x 9)) '(1 2 3)) ;; => '(() (1 2 3)) (break (lambda (x) (> x 9)) '(1 2 3)) ;; => '((1 2 3) ())
strip-prefix (prefix list &optional (default nil))
The strip-prefix
function drops the given prefix from a list. It returns DEFAULT value if the list did not start with the prefix given, or the list after the prefix, if it does.
(strip-prefix '(1 2) '(1 2 3 4)) ;; => '(3 4) (strip-prefix '(1 2) '(1 2)) ;; => '() (strip-prefix '(1 2) '(3 4 1 2)) ;; => NIL (strip-prefix '(1 2) '(3 4 1 2 5 6)) ;; => NIL
inits (list)
The inits
function returns all initial segments of the argument, shortest first.
(inits '(1 2 3)) ;; => '(nil (1) (1 2) (1 2 3)) (inits '()) ;; => '(nil)
tails (list)
The tails
function returns all final segments of the argument, longest first.
(tails '(1 2 3)) ;; => '((1 2 3) (2 3) (3) nil) (tails '()) ;; => '(nil)
Predicates
is-prefix-of (prefix list)
The is-prefix-of
function takes two lists and returns T
if the first list is a prefix of the second.
(is-prefix-of '(1 2) '(1 2 3 4)) ;; => T (is-prefix-of '(1 2) '(4 3 2 1)) ;; => nil (is-prefix-of '() '(1 2 3)) ;; => T
is-suffix-of (suffix list)
The is-suffix-of
function takes two lists and returns T
if the first list is a suffix of the second.
(is-suffix-of '(2 1) '(4 3 2 1)) ;; => T (is-suffix-of '(1 2) '(4 3 2 1)) ;; => nil (is-suffix-of '() '(1 2 3)) ;; => T
is-infix-of (infix list)
The is-infix-of
function takes two lists and returns T
if the first list is contained, wholly and intact, anywhere within the second.
(is-infix-of '(1 2) '(3 3 1 2 3 3)) ;; => T (is-infix-of '(1 2 3) '(4 1 2 4 3)) ;; => nil (is-infix-of '() '(1 2 3)) ;; => T
is-subsequence-of (subseq list)
The is-subsequence-of
function takes two lists and returns T
if all the elements of the first list occur, in order, in the second. The elements do not have to occur consecutively.
(is-subsequence-of '(1 2 3) '(1 0 2 0 3 0)) ;; => T (is-subsequence-of '(1 2 3) '(1 0 2 0 4 0)) ;; => nil (is-subsequence-of '() '(1 2 3)) ;; => T
Searching lists
Searching by equality
elem (element list &key (test 'equalp))
Does the element occur in the structure?
(elem 1 '(1 2 3)) ;; => T (elem "one" '(1 "one" 3) :test 'eql) ;; => nil
not-elem (element list &key (test 'equalp))
not-elem
is the negation of elem.
(not-elem 7 '(1 2 3)) ;; => T (not-elem "one" '(1 "one" 3) :test 'eql) ;; => T
Searching with a predicate
find (pred list &optional (default nil))
The find
function takes a predicate and a LIST and returns the leftmost element of the list matching the predicate, or DEFAULT argument if there is no such element.
(find #'numberp '(:foo :bar 1 2 3)) ;; => 1 (find #'numberp '(:foo :bar)) ;; => nil (find #'numberp '(:foo :bar) 666) ;; => 666
filter (pred list)
filter
, applied to a predicate and a LIST, returns the list of those elements that satisfy the predicate; i.e.,
(filter #'numberp '(:foo 1 :bar 2 3)) ;; => '(1 2 3) (filter #'numberp '(:foo :bar)) ;; => nil
partition (pred list)
The partition
function takes a predicate a LIST and returns the pair of lists of elements which do and do not satisfy the predicate, respectively; i.e.,
(partition #'numberp '(:foo 1 :bar 2)) ;; => '((1 2) (:foo :bar)) (partition #'numberp '(:foo :bar)) ;; => '(() (:foo :bar))
Indexing lists
elem-index (item list &optional (default nil))
The elem-index
function returns the index of the first element in the given list which is equal to the query element, or DEFAULT if there is no such element.
(elem-index 2 '(1 2 3)) ;; => 1 (elem-index 2 '(1 2 3 2 1)) ;; => 1 (elem-index 0 '(1 2 3) 42) ;; => 42
elem-indices (item list)
The elem-indices
function extends elem-index
, by returning the indices of all elements equal to the query element, in ascending order.
(elem-indices 42 '(1 42 3 42)) ;; => '(1 3) (elem-indices 42 '(1 2 3)) ;; => '()
find-index (pred list &optional (default nil))
The find-index
function takes a predicate and a LIST and returns the index of the first element in the list satisfying the predicate, or DEFAULT if there is no such element.
(find-index #'keywordp '(1 :foo 3)) ;; => 1 (find-index #'keywordp '(1 :foo 3 :bar 1)) ;; => 1 (find-index #'keywordp '(1 2 3) 42) ;; => 42
find-indices (pred list)
The find-indices
function extends find-index
, by returning the indices of all elements satisfying the PRED, in ascending order.
(find-indices #'keywordp '(1 :foo 3 :bar)) ;; => '(1 3) (find-indices #'keywordp '(1 2 3)) ;; => '()
Zipping and unzipping lists
zip (&rest lists)
Zip LISTS together. Group the head of each list, followed by the second elements of each list, and so on. The lengths of the returned groupings are equal to the length of the shortest input list.
(zip '(1 2) '(3 4) '(5 6))) ;; => '((1 3 5) (2 4 6)) (zip '(1 2 3) '(4) '(5 6))) ;; => '((1 4 5)) (zip '(1 2 3) '() '(5 6))) ;; => '()
zip-with (fn &rest lists)
zip-with
generalises zip
by zipping with the function given as the first argument.
(zip-with #'+ '(1 2) '(3 4) '(5 6))) ;; => '(9 12) (zip-with #'list '(1 2) '(3 4) '(5 6))) ;; => '((1 3 5) (2 4 6)) (zip-with #'+ '(1 2 3) '() '(5 6))) ;; => '()
unzip (lists)
Opposite by sense to zip
.
(unzip '((1 2) (3 4) (5 6))) ;; => '((1 3 5) (2 4 6)) (unzip (.zip '(1 2) '(3 4) '(5 6))) ;; => '((1 2) (3 4) (5 6)) (unzip '((1 2 3) '(4) '(5 6))) ;; => '((1 4 5)) (unzip '((1 2 3) '())) ;; => '()
Author
- Ito Dimercel (xolcman@gmail.com)
Copyright
Copyright (c) 2021 Ito Dimercel (xolcman@gmail.com)
License
Licensed under the LLGPL License.