The picl Reference Manual

Table of Contents

The picl Reference Manual

This is the picl Reference Manual, version 1.0.1, generated automatically by Declt version 3.0 "Montgomery Scott" on Mon Apr 19 17:22:59 2021 GMT+0.

1 Introduction

picl

Anish Moorthy 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)

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.1

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

• always (function)
• apply (function)
• empty-iterator (function)
• iter-to-list (function)
• iter-to-vec (function)
• never (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

• always (function)
• apply (function)
• 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)
• never (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: always ITERABLE

Truthy iff every element of the argument is truthy

“‘
(always ’(1 2 3))
;; t
(always ’(nil))
;; nil
(always nil)
t
“‘

Package

picl

Source

utils.lisp (file)

Function: apply FN &rest ARGS

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

“‘
(picl:apply #’+ 1 #(2 3))
;; 6
“‘

Package

picl

Source

utils.lisp (file)

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: never ITERABLE

Truthy iff every element of the argument is nil

“‘
(never ’(1 2 3))
;; nil
(never ’(nil))
;; t
(never nil)
t
“‘

Package

picl

Source

utils.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