listopia

2021-04-11

List manipulation library

Upstream URL

github.com/Dimercel/listopia

Author

Ito Dimercel

License

LLGPL
README

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

Copyright

Copyright (c) 2021 Ito Dimercel (xolcman@gmail.com)

License

Licensed under the LLGPL License.

Dependencies (3)

  • prove
  • rove
  • trivial-benchmark

Dependents (1)

  • GitHub
  • Quicklisp