The picl Reference Manual

Table of Contents

The picl Reference Manual

This is the picl Reference Manual, version 1.0.0, generated automatically by Declt version 3.0 "Montgomery Scott" on Wed Nov 04 14:49:45 2020 GMT+0.

1 Introduction

picl

Anish Moorthy anlsh@protonmail.com

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

An (almost) complete port of Python's itertools package, complete with laziness where applicable.

This project currently lives on Github. Pull requests welcome!

Objectives and Rationale

Other libraries, such as cl-itertools and snakes, provide similar functionality

Unfortunately cl-itertools remains very incomplete, and bothcl-itertoolsand snakes rely on cl-cont meaning that they wont always play nice with certain parts of CL (apparently)

PICL provides a near-complete port of itertools, complete with laziness, without any reliance on cl-cont or other such libraries

Installation

PICL isn't in Quicklisp yet, though that should change soon. For now, you'll probably want to clone/symlink it into your .quicklisp/local-projects directory so that you can do a (ql:quickload :picl)

Documentation

All functions are annotated with markdown docstrings. Thanks to Staple you can read the documentation online or build it yourself like so

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

Just ignore any warnings you get about invalid definitions, all they mean is that you don't have PICL's dependencies loaded yet.

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 function taking no arguments and producing two values: the payload and the alive-indicator. The payload represent's the iterator's next item, and 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 to produce a function satisfying the conditions described above. 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))

(iterate:iter
    (iterate:for i in-it #(1 2 3))
    (iterate:collect i))
;; (1 2 3)

(iterate:iter
    (iterate:for i in-it (picl:permutations '(1 2 3)))
    (iterate:collect i))
;; (#(1 2 3) #(1 3 2) #(2 1 3) #(2 3 1) #(3 1 2) #(3 2 1))

though you should probably :use iterate so as not to have the iterate: prefix everywhere

Missing Functionality

The only functions which are still missing are groupby and accumulate.

A note on :use

This is a new library, and so I have the liberty to tell you this: do not, and I mean do not :use this package. This library might export new symbols in the future, and I'm not going to accomodate the use of :use.

Use package local nicknames instead, and maybe even consider adding similar disclaimers in any new libraries you release.

Future Work

• Port the more-itertools recipes found at bottom of the Python itertools package
• Port the more-iterools package (this seems like a big job)

Acknowledgements

Python, its itertools package, and all those who have contributed to it.

Shinmera, for creating Staple

License

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

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 picl

Author

Anish Moorthy <anlsh@protonmail.com>

Home Page

https://anlsh.github.io/picl/

License

MIT

Description

Python Itertools in Common Lisp

Version

1.0.0

Dependencies

• defclass-std
• alexandria

Source

picl.asd (file)

Component

src (module)

3 Modules

Modules are listed depth-first from the system components tree.

3.1 picl/src

Parent

picl (system)

Location

src/

Components

• package.lisp (file)
• interface.lisp (file)
• default-iterators.lisp (file)
• utils.lisp (file)
• itertools.lisp (file)
• combinatoric.lisp (file)

4 Files

Files are sorted by type and then listed depth-first from the systems components trees.

4.1 Lisp

4.1.1 picl.asd

Location

picl.asd

Systems

picl (system)

4.1.2 picl/src/package.lisp

Parent

src (module)

Location

src/package.lisp

Packages

picl

4.1.3 picl/src/interface.lisp

Dependency

package.lisp (file)

Parent

src (module)

Location

src/interface.lisp

Exported Definitions

• make-iterator (generic function)
• make-iterator (method)
• next (function)

Internal Definitions

def-iter (macro)

4.1.4 picl/src/default-iterators.lisp

Dependency

interface.lisp (file)

Parent

src (module)

Location

src/default-iterators.lisp

Exported Definitions

• make-iterator (method)
• make-iterator (method)

4.1.5 picl/src/utils.lisp

Dependency

interface.lisp (file)

Parent

src (module)

Location

src/utils.lisp

Exported Definitions

• empty-iterator (function)
• iter-to-list (function)
• iter-to-vec (function)
• take (function)

4.1.6 picl/src/itertools.lisp

Dependency

utils.lisp (file)

Parent

src (module)

Location

src/itertools.lisp

Exported Definitions

• chain (function)
• compress (function)
• count (function)
• cycle (function)
• dropwhile (function)
• enumerate (function)
• filter (function)
• filterfalse (function)
• islice (function)
• map (function)
• range (function)
• repeat (function)
• starmap (function)
• takewhile (function)
• tee (function)
• zip (function)
• zip-longest (function)

Internal Definitions

• chain-from-iter (function)
• tee-item (function)
• zip-from-itl (function)
• zip-longest-from-itl (function)

4.1.7 picl/src/combinatoric.lisp

Dependency

utils.lisp (file)

Parent

src (module)

Location

src/combinatoric.lisp

Exported Definitions

• combinations (function)
• combinations-with-rep (function)
• nfold-product (function)
• permutations (function)
• product (function)

5 Packages

Packages are listed by definition order.

5.1 picl

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions

• chain (function)
• combinations (function)
• combinations-with-rep (function)
• compress (function)
• count (function)
• cycle (function)
• dropwhile (function)
• empty-iterator (function)
• enumerate (function)
• filter (function)
• filterfalse (function)
• islice (function)
• iter-to-list (function)
• iter-to-vec (function)
• make-iterator (generic function)
• make-iterator (method)
• make-iterator (method)
• make-iterator (method)
• map (function)
• next (function)
• nfold-product (function)
• permutations (function)
• product (function)
• range (function)
• repeat (function)
• starmap (function)
• take (function)
• takewhile (function)
• tee (function)
• zip (function)
• zip-longest (function)

Internal Definitions

• chain-from-iter (function)
• def-iter (macro)
• tee-item (function)
• zip-from-itl (function)
• zip-longest-from-itl (function)

6 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

6.1 Exported definitions

6.1.1 Functions

Function: chain &rest ITERABLES

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
“‘

Package

picl

Source

itertools.lisp (file)

Function: combinations R ITERABLE

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

“‘
(combinations 2 ’(1 2 3))
;; #(1 2), #(1 3), #(2 3)
“‘

Package

picl

Source

combinatoric.lisp (file)

Function: combinations-with-rep R ITERABLE

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)
“‘

Package

picl

Source

combinatoric.lisp (file)

Function: compress BASE-ITERABLE BOOL-ITERABLE

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
“‘

Package

picl

Source

itertools.lisp (file)

Function: count &optional START STEP

Yields the elements ‘start, start + 1*step, start + 2*step, etc

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

Package

picl

Source

itertools.lisp (file)

Function: cycle ITERABLE

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
“‘

Package

picl

Source

itertools.lisp (file)

Function: dropwhile PREDICATE ITERABLE

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
“‘

Package

picl

Source

itertools.lisp (file)

Function: empty-iterator ()

Returns an empty iterator

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

Package

picl

Source

utils.lisp (file)

Function: enumerate ITERABLE &optional CURR

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)
“‘

Package

picl

Source

itertools.lisp (file)

Function: filter PREDICATE ITERABLE

Yields elements of ‘iterable‘ for which ‘predicate‘ returns true

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

Package

picl

Source

itertools.lisp (file)

Function: filterfalse PREDICATE ITERABLE

Yields elements of ‘iterable‘ for which ‘predicate‘ returns false

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

Package

picl

Source

itertools.lisp (file)

Function: islice ITERABLE START STOP DELTA

Works like Python’s [islice](https://docs.python.org/3.8/library/itertools.html#itertools.islice)

Package

picl

Source

itertools.lisp (file)

Function: iter-to-list ITERABLE

Reads ‘iterable‘ into a list

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

Package

picl

Source

utils.lisp (file)

Function: iter-to-vec ITERABLE

Reads ‘iterable‘ into a vector

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

Package

picl

Source

utils.lisp (file)

Function: map PREDICATE &rest ITERABLES

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

“‘
(map #’+ ’(1 2) ’(3 4))
;; 4, 6
“‘

Package

picl

Source

itertools.lisp (file)

Function: next ITERATOR

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

Package

picl

Source

interface.lisp (file)

Function: nfold-product N ITERABLE

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) “‘

Package

picl

Source

combinatoric.lisp (file)

Function: permutations S0 &optional S1

‘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)
“‘

Package

picl

Source

combinatoric.lisp (file)

Function: product &rest ITERABLES

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](https://docs.python.org/3/library/itertools.html#itertools.product). Use ‘picl:nfold-product‘ instead.

“‘
(product ’(1 2) ’(3 4))
;; #(1 3), #(1 4), #(2 3), #(2 4)
“‘

Package

picl

Source

combinatoric.lisp (file)

Function: range S0 &optional S1 STEP

Works [as in Python](https://docs.python.org/3/library/stdtypes.html#typesseq-range) 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
“‘

Package

picl

Source

itertools.lisp (file)

Function: repeat S0 &optional S1

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
“‘

Package

picl

Source

itertools.lisp (file)

Function: starmap FN ITERABLE-OF-ITERABLES

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

“‘
(starmap #’+ ’(1 2) ’(3 4))
;; 3, 7
“‘

Package

picl

Source

itertools.lisp (file)

Function: take N ITERABLE

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)
“‘

Package

picl

Source

utils.lisp (file)

Function: takewhile PREDICATE ITERABLE

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

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

Package

picl

Source

itertools.lisp (file)

Function: tee N ITERABLE

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
“‘

Package

picl

Source

itertools.lisp (file)

Function: zip &rest ITERABLES

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)
“‘

Package

picl

Source

itertools.lisp (file)

Function: zip-longest FILL-ITEM &rest ITERABLES

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)
“‘

Package

picl

Source

itertools.lisp (file)

6.1.2 Generic functions

Generic Function: make-iterator ITERABLE

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

Package

picl

Source

interface.lisp (file)

Methods

Method: make-iterator (OBJ vector)

Returns an iterator which traverses elements of a vector in sequential order

Source

default-iterators.lisp (file)

Method: make-iterator (OBJ list)

Returns an iterator which traverses elements of a list in sequential order

Source

default-iterators.lisp (file)

Method: make-iterator (OBJ function)

6.2 Internal definitions

6.2.1 Macros

Macro: def-iter NAME STATE-VARS (CONSTRUCTOR-NAME CONSTRUCTOR-PARAMS &body CONSTRUCTOR-BODY) &body NEXT-BODY

An anaphoric convenience macro which can be re-implemented to change how iterators are structured. Exposes the local ‘init-state‘ macro within ‘constructor-body‘

If you don’t want to-use this macro (which I totally understand) just write constructors for your iterators returning 0-argument closures representing the ‘next‘ function and you’ll be fine. This macro just helped me get through a lot of waffling during development

Parameters
———-
‘name‘ is a synbol naming the iterator’s backing state. However it’s actually
ignored, since PICL doesn’t currently expose iterators’ backing state

‘state-vars‘ is a list of symbols naming the iterator’s state variables.

The ‘constructor-name/params/body‘ will be ‘defun‘’d to create the user-facing constructor function. In ‘constructor-body‘, the return value should be an iterator or a call to local ‘init-state‘ macro

‘next-body‘ The definition of the ‘next‘ function for this iterator, which will be run in a lexical environment consisting of the state vars

Both ‘constructor-body‘ and ‘next-body‘ are defined in the lexical environment of the ‘def-iter‘ form, and as such can access any lexical bindings not shadowed by the ‘constructor-params‘ and ‘state-vars‘ respectively

The local ‘init-state‘ macro.
—————————-
The arguments to ‘init-state‘ should be of the form ‘(statevar-symbol value-form)‘or ‘statevar-symbol‘. In the first case, the value of ‘value-form‘ will be used to initialize the state variable named by ‘symbol‘. In the second case, ‘statevar-symbol‘ is also used as the corresponding ‘value-form‘

Example
——-
What follows is a sample implementation of the ‘count‘ iterator using this macro
“‘
(def-iter ignored-backing-name (curr-val step)
(count (start step)
(init-state (curr-val start) step))
(prog1 curr-val (incf curr-val step))))
““

Package

picl

Source

interface.lisp (file)

6.2.2 Functions

Function: chain-from-iter ITL-OF-ITLS

Function had no docstring, so this one was inserted

Package

picl

Source

itertools.lisp (file)

Function: tee-item ITERABLE Q

Function had no docstring, so this one was inserted

Package

picl

Source

itertools.lisp (file)

Function: zip-from-itl ITL-OF-ITLS

Function had no docstring, so this one was inserted

Package

picl

Source

itertools.lisp (file)

Function: zip-longest-from-itl ITL-OF-ITLS &optional FILL-ITEM

Function had no docstring, so this one was inserted

Package

picl

Source

itertools.lisp (file)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types