picl

Anish Moorthy mailto:anlsh@protonmail.com

Python Itertools in Common Lisp (v1.0.0). Pronounced like "pickle"

A (very nearly) complete port of Python's itertools package, complete with laziness where applicable.

This project currently lives on Github. Pull requests welcome!

Objectives and Rationale

PICL aims to provide a complete port of itertools, complete with laziness, without any reliance on cl-cont.

cl-itertools and snakes, provide similar functionality. Unfortunately both libraries rely on cl-cont, meaning they wont always play nice with the condition system, and cl-itertools remains very incomplete on top of that

Installation

PICL is in Quicklisp, and can be installed as follows

(ql:quickload :picl)

Do not :use this package: it might export new symbols in the future. You have been forewarned.

Documentation

Thanks to Staple you can read the documentation online or build it yourself like so

(staple:generate :picl :if-exists :supersede)

If you don't have PICL's dependencies loaded into your image yet, you'll get some harmless warnings about invalid definitions

Testing

A fairly comprehensive test suite written with FiveAM is provided. You can run it yourself either manually or through asdf

;; The easy way
(asdf:test-system :picl)
;; The slightly less easy way
(ql:quickload :picl/tests)
(fiveam:run! 'picl/tests:suite)

Concepts and How-To

An "iterator" in PICL is simply a thunk producing two values: the payload and the alive-indicator. The alive-indicator should be truthy until after the iterator is consumed.

By example

(let ((it (make-iterator '(1 2))))
  (next it)  ;; (values 1 t)
  (next it)  ;; (values 2 t)
  (next it)) ;; (values nil nil)

After returning nil, all further next calls should also produce nil as quickly as possible. Furthermore when the alive indicator is nil, the payload should be ignored.

To create iterators over your own objects, specialize the make-iterator generic function appropriately. For instance, the make-iterator definition for lists is

(defmethod make-iterator ((obj list))
  (lambda ()
    (if obj
        (values (prog1 (car obj) (setf obj (cdr obj))) t)
        (values nil nil))))

Specializations for lists and vectors are predefined. A universal in-it driver is also provided for Iterate through the picl/iterate system.

(ql:quickload '(:picl :picl/iterate))
;; The "iterate" package has been :use'd here
(iterate
    (for i in-it (picl:permutations '(1 2 3)))
    (collect i))
;; (#(1 2 3) #(1 3 2) #(2 1 3) #(2 3 1) #(3 1 2) #(3 2 1))

Note: All of the combinatoric iterators produce vectors, which can be annoying because those are second-class citizens in CL (you can't destructure them, for instance). To get around this, you can wrap the iterator in (picl:map #'iter-to-list <>)

(picl:iter-to-list (picl:map #'picl:iter-to-list (picl:permutations '(1 2 3))))
;; ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

It's a bit clunky for sure, so in the future I might extend the in-it clause to perform conversions like this when specified

Future Work

Functions still missing from Python's itertools (due to laziness: if you need these drop an issue/PR and I'll get around to implementing them) - groupby - accumulate

Extensions to library - Port the more-itertools recipes found at bottom of the Python itertools package - Port the more-iterools package (seems like a big job) - Some sort of integration with fset's sequence type?

License

This project is provided under the MIT License (see LICENSE.md)

System Information

Definition Index

• PICL

  No documentation provided.

  • EXTERNAL FUNCTION

    ALWAYS

    • ITERABLE

    Source

    Truthy iff every element of the argument is truthy

    (always '(1 2 3))
    ;; t
    (always '(nil))
    ;; nil
    (always nil)
    t

  • EXTERNAL FUNCTION

    APPLY

    • FN
    • &REST
    • ARGS

    Source

    Like regular apply, except that the final argument can be an arbitrary iterable.

    (picl:apply #'+ 1 #(2 3))
    ;; 6

  • EXTERNAL FUNCTION

    CHAIN

    • &REST
    • ITERABLES

    Source

    Yields the elements of the first iterable in iterable, then the second, etc.

    (chain '(1 2 3) '(4 5 6) (count 7))
    ;; 1, 2, 3, 4, 5, 6, 7 etc

  • EXTERNAL FUNCTION

    COMBINATIONS

    • R
    • ITERABLE

    Source

    r-combinations of input iterable, returned as vectors in lexicographic order.

    (combinations 2 '(1 2 3))
    ;; #(1 2), #(1 3), #(2 3)

  • EXTERNAL FUNCTION

    COMBINATIONS-WITH-REP

    • R
    • ITERABLE

    Source

    r-combinations with replacement of input iterable, returned as vectors in lexicographic order

    (combinations 2 '(1 2 3))
    ;; #(1 1), #(1 2), #(1 3), #(2 1), #(2 2), #(2 3), #(3 1), #(3 2), #(3 3)

  • EXTERNAL FUNCTION

    COMPRESS

    • BASE-ITERABLE
    • BOOL-ITERABLE

    Source

    Yields elements of base-iterable while the corresponding element in bool-iterable is truthy.

    Stops when either of its arguments is consumed

    (iterator-compress (count) (t nil t nil t nil))
    ;; 0 2 4

  • EXTERNAL FUNCTION

    COUNT

    • &OPTIONAL
    • START
    • STEP

    Source

    Yields the elements `start, start + 1step, start + 2step, etc

    (count 2 4)
    ;; 2, 6, 10, 14, etc

  • EXTERNAL FUNCTION

    CYCLE

    • ITERABLE

    Source

    Continually yields the elements of its argument in order, starting over when the end is reached

    If the base iterator is empty, the result of iterator-cycle will be too

    (cycle '(1 2 3 4))
    ;; 1, 2, 3, 4, 1, 2, 3, 4, etc
    (iter-to-list (cycle '()))
    ;; nil

  • EXTERNAL FUNCTION

    DROPWHILE

    • PREDICATE
    • ITERABLE

    Source

    Drops all elements of base-iter until pred first returns false, then yields all further elements

    (dropwhile (lambda (x) (< 3 x) (count)))
    ;; 3, 4, 5, etc

  • EXTERNAL FUNCTION

    EMPTY-ITERATOR

    Source

    Returns an empty iterator

    (iter-to-list (empty-iterator))
    ;; nil

  • EXTERNAL FUNCTION

    ENUMERATE

    • ITERABLE
    • &OPTIONAL
    • CURR

    Source

    Yield two-element lists of indices (beginning at curr) and their corresponding elements in iterable

    (enumerate '(a b c d))
    ;; (0 a), (1 b), (2 c), (3 d)
    (enumerate '(a b c d) 3)
    ;; (3 a), (4 b), (5 c), (6 d)

  • EXTERNAL FUNCTION

    FILTER

    • PREDICATE
    • ITERABLE

    Source

    Yields elements of iterable for which predicate returns true

    (filter (lambda (x) (evenp x) (count)))
    ;; 0, 2, 4, etc

  • EXTERNAL FUNCTION

    FILTERFALSE

    • PREDICATE
    • ITERABLE

    Source

    Yields elements of iterable for which predicate returns false

    (filterfalse (lambda (x) (evenp x) (count)))
    ;; 1, 3, 5, etc

  • EXTERNAL FUNCTION

    ISLICE

    • ITERABLE
    • START
    • STOP
    • DELTA

    Source

    Works like Python's islice

  • EXTERNAL FUNCTION

    ITER-TO-LIST

    • ITERABLE

    Source

    Reads iterable into a list

    (iter-to-list (range 4))
    ;; (0 1 2 3)
    (iter-to-list (count))
    ;; Out of memory error!

  • EXTERNAL FUNCTION

    ITER-TO-VEC

    • ITERABLE

    Source

    Reads iterable into a vector

    (iter-to-list (range 4))
    ;; #(0 1 2 3)
    (iter-to-list (count))
    ;; Out of memory error!

  • EXTERNAL FUNCTION

    MAP

    • PREDICATE
    • &REST
    • ITERABLES

    Source

    Applies fn to the first elements of each iterable in iterables, then to the seconds, etc

    (map #'+ '(1 2) '(3 4))
    ;; 4, 6

  • EXTERNAL FUNCTION

    NEVER

    • ITERABLE

    Source

    Truthy iff every element of the argument is nil

    (never '(1 2 3))
    ;; nil
    (never '(nil))
    ;; t
    (never nil)
    t

  • EXTERNAL FUNCTION

    NEXT

    • ITERATOR

    Source

    Produces two values, the payload and the alive-indicator

    While iterator is not yet exhausted, calling next will yield its next item and a truthy alive-indicator

    After iterator has been exhausted all further calls should yield an alive-indicator of nil, and the payload should be ignored by the callee

  • EXTERNAL FUNCTION

    NFOLD-PRODUCT

    • N
    • ITERABLE

    Source

    Computes the n-fold Cartesian product of an iterable with itself.

    Essentially equivalent to (apply #'product (iter-to-list (tee n iterable)), but with much better memory usage

    (nfold-product 3 '(1 2))
    ;; #(1 1 1), #(1 1 2), #(1 2 1), #(1 2 2), #(2 1 1), #(2 1 2), #(2 2 1), #(2 2 2)

  • EXTERNAL FUNCTION

    PERMUTATIONS

    • S0
    • &OPTIONAL
    • S1

    Source

    r-permutations of input iterable, returned as vectors in lexicographic order.

    When a single argument is given, it should be an iterable and r will default to its length.

    When two arguments are given, the first corresponds to r and the second to the iterable

    (permutations '(1 2 3))
    ;; #(1 2 3), #(1 3 2), #(2 1 3), #(2 3 1), #(3 1 2), #(3 2 1)
    (permutations 2 '(1 2 3))
    ;; #(1 2), #(1 3), #(2 1), #(2 3), #(3 1), #(3 2)

  • EXTERNAL FUNCTION

    PRODUCT

    • &REST
    • ITERABLES

    Source

    Cartesian product of input iterables, returned as vectors in lexicographic order.

    Due to the awkwardness in mixing &rest and &key parameters in lambda lists, this function does not implement the repeat argument supported in Python's version. Use picl:nfold-product instead.

    (product '(1 2) '(3 4))
    ;; #(1 3), #(1 4), #(2 3), #(2 4)

  • EXTERNAL FUNCTION

    RANGE

    • S0
    • &OPTIONAL
    • S1
    • STEP

    Source

    Works as in Python but produces an iterator (as defined by PICL) instead of a Python-esque range object

    (range 5)
    ;; 0, 1, 2, 3, 4
    (range 2 5)
    ;; 2, 3, 4
    (range -2)
    ;; 0, -1
    (range 1 7 2)
    ;; 1, 3, 5

  • EXTERNAL FUNCTION

    REPEAT

    • S0
    • &OPTIONAL
    • S1

    Source

    If a single argument is given, yields s0 repeatedly forever

    If two arguments are given, then yields s1 s0 times

    (repeat t)
    ;; t, t, etc
    (repeat 4 t)
    ;; t, t, t, t

  • EXTERNAL FUNCTION

    STARMAP

    • FN
    • ITERABLE-OF-ITERABLES

    Source

    Applies fn to the first argument of iterable-of-iterables, then the second, etc

    (starmap #'+ '(1 2) '(3 4))
    ;; 3, 7

  • EXTERNAL FUNCTION

    TAKE

    • N
    • ITERABLE

    Source

    Returns a list consisting of the first n (or fewer, if the iterator runs out) items of iterable

    (take 5 (count))
    ;; (0 1 2 3 4)
    take 30 (range 4)
    ;; (0 1 2 3)

  • EXTERNAL FUNCTION

    TAKEWHILE

    • PREDICATE
    • ITERABLE

    Source

    Yields elements of iterable for which predicate is truthy, terminating once it first returns nil

    (takewhile (lambda (x) (< 3 x) (count)))
    ;; 0, 1, 2

  • EXTERNAL FUNCTION

    TEE

    • N
    • ITERABLE

    Source

    Returns a vector of n independent copies of iterable. iterable itself should not be used after it has been passed to tee, otherwise the tees will not be properly updated

    If the base iterable is large be careful not to advance any copy too far ahead of the others, so as to avoid memory issues

    tees = (tee 2 '(1 2 3 4))
    ;; tees[0] => 1, 2, 3, 4
    ;; tees[1] => 1, 2, 3, 4

  • EXTERNAL FUNCTION

    ZIP

    • &REST
    • ITERABLES

    Source

    Returns vectors consisting of the first elements from each iterable in iterable, then the second, etc until one is consumed

    (zip '(1 2 3) '(a b c d))
    ;; #(1 a). #(2 b), #(3 c)

  • EXTERNAL FUNCTION

    ZIP-LONGEST

    • FILL-ITEM
    • &REST
    • ITERABLES

    Source

    Returns vectors consisting of the first elements from each iterable in iterable, then the second, etc until all are consumed. Once a constituent iterable has been exhausted, fill-value is used to pad the vector in its place.

    (zip nil '(1 2 3) '(a b c d))
    ;; #(1 a). #(2 b), #(3 c), #(nil d)

  • EXTERNAL GENERIC-FUNCTION

    MAKE-ITERATOR

    • ITERABLE

    Source

    Creates an iterator from iterable: an iterator is simply anything which can be passed as an argument to next