jmbr / incf-cl

(incf cl) utilities
===================
Juan M. Bello Rivas <jmbr@superadditive.com>
November 2009

image:/images/lisp.png[Lisp logo by Conrad Barski]

Overview
--------

This is a collection of helpful functions and macros for Common Lisp.

Some of the available features are:

1. List manipulation functions similar to those in Haskell's prelude.

2. List comprehensions.

3. Doctest suite for automatic verification of examples in docstrings.

4. Nesting functions similar to those available in Mathematica.

Download
--------

You can download a tarball from http://github.com/jmbr/incf-cl/tree or
clone the Git repository by issuing the following command:

-------------------------------------------------
  $ git clone git://github.com/jmbr/incf-cl.git
-------------------------------------------------

License
-------

This library is released under the X11 license.

Portability
-----------

This code has been tested under

1. SBCL 1.0.32
2. Armed Bear Common Lisp 0.18.0-dev
3. ECL 9.11.1

Installation
------------

The easiest way to install (incf-cl) is to use ASDF-INSTALL if you
have it on your system:

----------------------------------------------
  (asdf:operate 'asdf:load-op :asdf-install)
  (asdf-install:install :incf-cl)
----------------------------------------------

Note that you need http://common-lisp.net/project/stefil/[Stefil] if
you want to run the test suite.

If you don't have ASDF-INSTALL just download the latest tarball as
explained above and follow the standard package installation procedure
for your Lisp implementation.

Usage
-----

Loading the library
~~~~~~~~~~~~~~~~~~~

To start using the library write:

--------------------------------------------------
  CL-USER> (asdf:operate 'asdf:load-op :incf-cl)
  NIL
  CL-USER> (use-package :incf-cl)
  T
--------------------------------------------------

Features
~~~~~~~~

Ranges
^^^^^^

The function RANGE is similar to Matlab's vector notation.  Some use
cases are:

-----------------------------------------------------------------------
  CL-USER> (range 1 10)
  (1 2 3 4 5 6 7 8 9 10)
  CL-USER> (range 0 1/4 1)
  (0 1/4 1/2 3/4 1)
-----------------------------------------------------------------------

List comprehensions
^^^^^^^^^^^^^^^^^^^

List comprehensions are a programming language construct that closely
mimics the way you declare a set in mathematics and sometimes are more
succinct and readable than using a composition of MAPCAR, DELETE-IF or
an ad hoc imperative loop.

Here are two examples on how to use the LC (short for List
Comprehension) macro:

-----------------------------------------------------------------------
  CL-USER> (lc (sin x) (<- x (range 0 .25 (/ pi 2))))
  (0.0 0.24740396 0.47942555 0.6816388 0.84147096 0.9489846 0.997495)
  CL-USER> (lc (cons x y) (<- x (range 0 2)) (<- y (range 0 2))
               (= (+ x y) 2))
  ((0 . 2) (1 . 1) (2 . 0))
-----------------------------------------------------------------------

Doctests
^^^^^^^^

The DOCTEST function makes sure the examples given in every exported
function in a package are correct.  It scans each function's
documentation string looking for pieces of text resembling REPL
sessions, then it evaluates them and checks their values against the
expected ones.

Suppose you have the package TEST, defined as follows:

--------------------------------------------------------------
  (defpackage :test
    (:use :common-lisp :incf-cl)
    (:export :factorial))

  (in-package :test)

  (defun factorial (n &optional (acc 1))
    "Returns the factorial of N, where N is an integer >= 0.

    Examples:

    TEST> (lc (factorial n) (<- n (range 1 5)))
    (1 2 6 24 120)

    TEST> (factorial 450/15)
    265252859812191058636308480000000

    TEST> (signals-p arithmetic-error (factorial -1))
    T

    TEST> (signals-p type-error (factorial 30.1))
    T

    TEST> (factorial 0)
    1"
    (declare (type integer n))

    (cond
      ((minusp n) (error 'arithmetic-error))
      ((/= n (floor n)) (error 'type-error)))

    (if (= n 0)
        acc
        (factorial (1- n) (* n acc))))
--------------------------------------------------------------

and you want to make sure the examples given in FACTORIAL's doc
strings work as expected:

----------------------------
  CL-USER> (doctest :test)
  .....T
----------------------------

So now you know everything was correct.

Prelude
^^^^^^^

There are a some list manipulation functions compatible with Haskell's
Prelude (although often Lispified, see their docstrings).  Currently,
the following are implemented:

* BREAK*
* CYCLE (and its destructive version NCYCLE).
* DROP
* DROP-WHILE
* FLIP
* GROUP
* INSERT
* INTERSPERSE (and its destructive version NINTERSPERSE).
* PARTITION
* REPLICATE
* SCAN* (using the key parameters :INITIAL-VALUE and :FROM-END it works as
  scanl, scanl1, scanr, or scanr1)
* SPAN
* SPLIT-AT
* TAKE
* TAKE-WHILE
* UNZIP

Since Common Lisp doesn't guarantee tail call elimination, these
functions are written iteratively instead of recursively to avoid
stack overflows.

You can read the online documentation for each function (using
DESCRIBE or C-c C-d d in SLIME) and also
http://undergraduate.csse.uwa.edu.au/units/230.301/lectureNotes/tourofprelude.html[A
tour of the Haskell's prelude] to see more use cases.

Nesting
^^^^^^^

The function NEST-LIST returns the results of applying a certain
function F to a list of initial values.  This may go on up to a
certain number of applications or until a given function is true.

NEST works as NEST-LIST but it only returns the last result, not the
whole list.

Some examples:

---------------------------------------------------------
  CL-USER> (nest-list (lambda (x) `(sin ,x)) 'z :max 3)
  (Z (SIN Z) (SIN (SIN Z)) (SIN (SIN (SIN Z))))

  CL-USER> (nest-list #'+ '(1 1) :max 10)
  (1 1 2 3 5 8 13 21 34 55 89 144)

  CL-USER> (nest #'+ '(1 1) :max 10)
  144

  CL-USER> (nest-list (lambda (x) (mod (* 2 x) 19))
                      2
                      :test (lambda (x) (/= x 1)))
  (2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1)
---------------------------------------------------------

A closely related function is FIXED-POINT which returns the fixed
point of a function F starting with a given initial value.  Whether a
fixed point has been reached or not is determined by a test
function (EQL by default).

For example, the square root of 2 using Newton's method can be
computed as:

-----------------------------------------------------------------------
  CL-USER> (fixed-point (lambda (x)
                          (float (- x (/ (- (expt x 2) 2) (* 2 x)))))
                        1)
  1.4142135
-----------------------------------------------------------------------

Unfolds
^^^^^^^

There's an implementation of UNFOLD and UNFOLD-RIGHT as specified in
http://srfi.schemers.org/srfi-1/srfi-1.html#unfold[SRFI 1: List
library]

Here's an example of UNFOLD:

--------------------------------------------------------------------------
  (defun euler (f x0 y0 interval h)
    "Computes an approximate solution of the initial value problem:

      y' = f(x, y), x in interval;  y(x0) = y0

    using Euler's explicit method.  Interval is a list of two elements
    representing a closed interval.  The function returns a list of
    points and the values of the approximate solution at those points.

    For example,

    EULER> (euler (lambda (x y)
                    (declare (ignore y))
                    (- (sin x)))
                  0 1 (list 0 (/ pi 2)) 0.5)
    ((0 1) (0.5 1.0) (1.0 0.7602872) (1.5 0.33955175))"
    (assert (<= (first interval) (second interval)))
    (unfold (lambda (x) (> (first x) (second interval)))
            #'identity
            (lambda (pair)
              (destructuring-bind (x y) pair
                (list (+ x h) (+ y (* h (funcall f x y))))))
            (list x0 y0)))
-------------------------------------------------------------------------

Functions
^^^^^^^^^

The function $ returns the composition of several functions.  The
following example illustrates its use:

----------------------------------------------
  CL-USER> (funcall ($ (lambda (x) (* x x))
                       (lambda (x) (+ x 2)))
                    2)
  16
----------------------------------------------

Hash table utilities
^^^^^^^^^^^^^^^^^^^^

If you want to traverse a hash table, DOHASH can iterate over it with
semantics similar to those of DOLIST:

-------------------------------------------------------
  CL-USER> (dohash (key value *hash-table*)
             (format t "~a => ~d~%" key value))
  three => 3
  two => 2
  one => 1
  NIL
  CL-USER> (let ((product 1))
             (dohash (key value *hash-table* product)
               (setf product (* product value))))
  6
-------------------------------------------------------

Strings
^^^^^^^

The function STRING-JOIN glues together a list of strings placing a
given separator between each string.  By default, the separator is a
space.

------------------------------------------------------
  CL-USER> (string-join (list "Hello" "world"))
  "Hello world"
  CL-USER> (string-join (list "Hello" "world") ", ")
  "Hello, world"
------------------------------------------------------

Links
-----

http://kyle-burton.livejournal.com/8219.html[Playing with List Comprehensions in CL]

http://i-need-closures.blogspot.com/2008/01/programming-collective-intelligence-in.html['Programming Collective 
Intelligence' in Common Lisp, Chapter 5 - Optimizations]

Feedback
--------

Please send your suggestions, patches, and bug reports to
jmbr at superadditive dot com