Daniel's Blog

SERIES: Haskell for Lisp

Posted by Daniel Lyons Sun, 11 Nov 2007 01:35:00 GMT

One of the great pleasures of being a Haskell user is using hylomorphisms to accomplish all your work. To wit:

factorial x = foldr (*) 1 [2..x]
fibonacci = 1 : 1 : (zipWith (+) fibonacci (tail fibonacci))

Obviously this kind of obnoxious behavior would have to be ported to Lisp at some point. And it was, via the Series macro package. It’s Appendix A in CLtL.

In Lisp you’ll have to make a few concessions. You have to construct your series from other series. There are some handy ways of getting a series from a list or vector or another series. You’re limited to lazy lists using this functionality. Still, it’s fun.

To get started, install SERIES with (asdf-install:install 'series) and then import it with (require :series) and (use-package :series).

(defun fac (n)
  (collect-product (scan-range :from 2 :upto n)))

This is a pretty straight across port: [x..y] becomes (scan-range :from x :upto y). You can omit the :from and it will start with 0, omit the :upto and it will go on forever. There’s also :by which defaults to 1 for replicating the [n,m..z] syntax in Haskell. You also have :length to ensure that you only get so many (very helpful during programming because of the “P” in REPL.) And misc predicates like :above and :below are useful in certain situations. You can also use :type to change the type to ‘float if you want to produce series of floats.

collect-product does what it sounds like it would, multiplying all of the numbers together. If we didn’t have it built-in, you could replicate the functionality with (collect-fn :integer (constantly 1) #'* (scan-range ...)).

Dealing with the Fibonacci numbers is a bit more complicated:

(defvar fibs
  (scan-fn '(values :integer :integer)
           (lambda () (values 1 1))
           (lambda (x y) (values y (+ x y)))))

This works using Lisp’s multiple return values system. Basically, we’re returning two values with each function call; one of them is being passed out to be the item, and both are being fed back through the series generator. It’s not as beautiful as the Haskell but it captures the same concept, is as general (for lists) and performs some similar optimizations.