Using Match and Comprehensions in Scheme

« More entries

One of the blogs on functional programming I like most is Matt Might’s. In my first post I want to comment on Higher-order list operations and port its code to R5RS Scheme thanks to SRFI-42 and Alex Shinn’s matching macro libraries. The original code is written for Haskell and Racket.

The first thing I’ll need to do is to import the libraries using my favourite Scheme implementation’s specific forms. This code requires a R5RS-compatible implementation, with syntax-rules macros. For this examples I’m using Gambit Scheme compiler, with the Scheme Spheres libraries. If I’d like to use Gambit without Scheme Spheres (or any Scheme implementation without R5RS hygienic macros), I’d need a syntax-rules expander, such as Psyntax (bundled with Gambit’s distribution, supports syntax-case), Alexpander (a fast, generic implementation) or the Blackhole module system. Scheme Spheres is using Alexpander. The two aforementioned modules are necessary, but fully R5RS-compatible, so importing them in any Scheme implementation should be straightforward.

Here is how I do it with Gambit and SchemeSpheres:

Importing the necessary modules
;; In SchemeSpheres the match macro module can be found in Core
(##import-include core: match-macros)
;; In SchemeSpheres the SRFI-42 module can be found in Fabric/algorithm
(##import fabric: algorithm/comprehension)

I’m going to define a simple function and generate a list of numbers using eager list comprehensions. Generating lists of numbers with comprehensions can be very useful for code testing purposes. I use it here to generate a list of numbers from 0 to 9, but the possibilities are endless.

Declarations
;; define double for testing my procedures
(define double (lambda (x) (* 2 x)))

;; Generate a list of numbers from 0 to 9
(define numbers (list-ec (:range x 0 10) x))

The first operation I’m going to describe using match is the quintessential map procedure. Of course, this is already part of the R5RS standard. My implementation of map/match works by matching lst to two different clauses:

  1. Matching the null list produces another null list.

  2. Matching a pair produces a new pair: the function f gets applied to the first element, and the second element becomes the recursive application of the map/match definition.

Describing map with comprehensions is a rather cool one-liner. Of course, I’d need to properly understand the semantincs of SRFI-42’s eager comprehensions. Let’s dissect it:

  1. list-ec will produce a list of elements. This is the most fundamental comprehension, for obvious reasons in a Lisp library. Other possibilities are producing a vector, string or a list of appended values.

  2. The : will run through all the elements of the input lst. Using :list will allow only lists as input, but using just the : symbol will handle other types as well (vectors, strings…). The advantage of using :list is that it will produce a more optimized code. Inside :, the i will take the value of each element from lst, the list it will run through.

  3. (f i) is an expression executed over each one of the produced elements of the previous expression.

It is pretty straight-forward, once grasped the semantics of match and SRFI-42.

Map with match and comprehensions
;; Map with matching
(define (map/match f lst)
  (match lst
   ('() '())
   ((hd . tl) (cons (f hd) (map/match f tl)))))

(pp (map/match double numbers))

;; Map with comprehensions
(define (map/comprehensions f lst) (list-ec (: i lst) (f i)))

(pp (map/comprehensions double numbers))

Let’s build another essential procedure of functional languages: filter. This time, is not included in the R5RS standard, but rather part of the SRFI-1 library, which is one of the few pervasive ones across Scheme implementations. This time, match needs three clauses:

  1. Matching the null list will once again produce another null list

  2. The second clause will match against any pair (… . tl) with a head that matches the p predicate ((? p) …); then it will apply the the procedure recursively, cons‘ing the current head of the list (car lst) to it.

  3. The last clause will match against any pair (that didn’t match second’s clause b) and apply recursively without cons‘ing.

This operation is also very simple with comprehensions. It reminds of Haskell’s comprehensions: it’s a compact syntax. The key difference to map/comprehensions is that it adds the (if (p i)) expression just before the i which will output the elements without any processing at all (but just those that verify the predicate p. This is the behavior I would expect from filter.

Filter with match and comprehensions
;; Filter with matching
(define (filter/match p lst)
  (match lst
   ('() '())
   (((? p) . tl) (cons (car lst) (filter/match p tl)))
   ((hd . tl) (filter/match p tl))))

(pp (filter/match even? numbers))

;; Filter with comprehensions
(define (filter/comprehensions p lst) (list-ec (: i lst) (if (p i)) i))

(pp (filter/comprehensions even? numbers))

Another two operations that must be found in any functional programmer’s toolbox are fold and reduce (also found in SRFI-1). I will now implement fold with comprehensions and reduce with match.

Fold is a no-brainer with SRFI-42. It feels like cheating, as it is almost already defined. Just using the simplest forms yields what is expected, so I won’t spend time on it. Reduce with match is a different story. Let’s analyze its three clauses:

  1. Now matching the null list will be used for signaling an error: I don’t have elements in the list. This is because I use the base case in the second clause.

  2. The second clause (a) matches a single element and yields the element as-is. This will stop processing the list but avoids discarding the last element, which will be processed in the last clause, alongside every element of the list.

  3. The final clause will simply match a pair with (hd . tl), and then work the core of my procedure: applying the operation to the head and the rest of the list recursively. That’s the heart of reduce and fold: iterate over each element, accumulating the result.

Fold and Reduce with match
;; Folding with comprehesions
(define (fold/comprehensions f lst) (fold-ec 0 (: i lst) i f))

(pp (fold/comprehensions + numbers))

;; Reduce with matching
(define (reduce/match op lst)
  (match lst
   ('() (error "no elements in list"))
   ((a) a)
   ((hd . tl) (op hd (reduce/match op tl)))))

(pp (reduce/match + numbers))

Two important operations are zip and unzip. I’ll start by analyzing zip, which takes two lists and builds a new list of lists of elements in the same position of both input lists. Just as a zipper works (I try to visualize it, it makes it very clear). As it can be seen in the code, zip requires more machinery for it’s definition both with match and comprehensions. First, let’s tackle the match version:

  1. This time, I won’t be matching just against one list, but two. And I need to build a new list with both, so the match macro can digest it in just one form: (list lst1 lst)

  2. The first clause will match both null lists and produce just one null list that will close finish recursion. This leaves room for improvement: what about matching just one empty list?

  3. The second clause will match both lists, and inside them, their respective heads and tails. Then it’s just a matter of building a new list with both heads and continue recursion with both tails.

What about zip/comprehensions? This presents a particularity, but the implementation is, in my opinion, rather elegant. What I need to tell list-ec is, basically, to run both lists in parallel, with (:parallel …). Then I just need the extracted elements i and j to build each element of the new list with a list of these two (list i j). In both zip/match and zip/comprehensions I test the implementation with lists of numbers generated with comprehensions as well.

Zipping with match and comprehensions
;; Zipping with match
(define (zip/match lst1 lst2)
  (match (list lst1 lst2)
   (('() '()) '())
   (((hd1 . tl1) (hd2 . tl2))
    (cons (list hd1 hd2)
          (zip/match tl1 tl2)))))

(pp (zip/match (list-ec (:range i 1 5) i)
               (list-ec (:range i 4 8) i)))

;; Zipping with comprehensions
(define (zip/comprehensions lst1 lst2)
  (list-ec (:parallel
            (: i lst1)
            (: j lst2))
           (list i j)))

(pp (zip/comprehensions (list-ec (:range i 1 5) i)
                        (list-ec (:range i 4 8) i)))

Unzip is implemented using continuations, which are out of the scope of this post, but shows a new use of match. This time, the second clause will match against a pair, but the first element must itself be a list of 2 elements a, b.

Unzipping with continuations
;; Unzip with match
(define (unzip/callback lst k)
  (match lst
   ('() (k '() '()))
   (((a b) . tl)
    (unzip/callback tl (lambda (as bs)
                         (k (cons a as) (cons b bs)))))))

(pp (unzip/callback '((1 2) (3 4) (5 6))
                    (lambda (as bs) as)))

For the sake of completion, I implement also the partition algorithm, found in SRFI-1 and used for returning two values simultaneously: a list of elements that satisfy a predicate p, and a list of those that don’t. Match is used for its definition with no surprises and the same structures I’ve used in previous operations.

Zipping with match
;; Partition with match
(define (partition/values p? lst)
  (match lst
   ('()
    (values '() '()))
   ((hd . tl)
    (receive (ins outs)
             (partition/values p? tl)
             (if (p? hd)
                 (values (cons hd ins) outs)
                 (values ins (cons hd outs)))))))

(receive (a b)
         (partition/values even? numbers)
         (pp a) (pp b))

These are some basic operations implemented in terms of match or eager comprehensions, probably not the way normally implemented. Thanks to Matt Might for its great post, and I hope someone can find this useful for understading the power of match, eager comprehensions, and macros as a tool for extending the Scheme language, making it powerfully describe algorithms in expressive and terse syntax.


Did you find it useful? Please share!

Comments