The extensible sequences protocol requires that sequences be subtypes of the SEQUENCE class. I didn't like this at first, wanting to implement sequences directly on integers, but soon decided that wrapping things up in a class wasn't so bad - I can just write (below n) instead of n, and it suggested that I go a little further and implement intervals as sequences. Using the constructors below and interval, I can write the following:
(map 'vector 'list #(a b c d e) (below 3)) => #((A 0) (B 1) (C 2))
(map 'list '1+ (interval 20 25)) => (21 22 23 24 25)
Only a few definitions are needed to make this work:
;;; Interval sequence class (defclass interval-sequence (sequence standard-object) ((minimum :reader minimum :initform 0 :initarg :minimum) (length :reader sequence:length :initarg :length))) ;;; Constructors (defun below (n) (unless (>= n 0) (error 'type-error :datum n :expected-type '(integer 0))) (make-instance 'interval-sequence :length n)) (defun interval (min max) (unless (<= min max) (error "Interval minimum must be less than or equal to maximum")) (make-instance 'interval-sequence :minimum min :length (- max min))) ;;; Core sequence protocol (defmethod sequence:elt ((interval interval-sequence) index) (with-slots (minimum length) interval (unless minimum (error "Attempt to read from an uninitialized interval")) (when (or (< index 0) (>= index length)) (error 'type-error :datum index :expected-type `(integer 0 ,(1- length)))) (+ index minimum))) (defmethod (setf sequence:elt) (new-value (interval interval-sequence) index) (with-slots (minimum length) interval (cond ((or (< index 0) (>= index length)) (error 'type-error :datum index :expected-type `(integer 0 ,(1- length)))) ((null minimum) (setf minimum (- new-value index)) new-value) ((/= new-value (+ minimum index)) (error "Incompatible setf of interval element - expected ~A, got ~A" (+ minimum index) new-value)) (t new-value)))) (defmethod sequence:adjust-sequence ((interval interval-sequence) length &key initial-element initial-contents) (declare (ignore interval length initial-element initial-contents)) (error "Interval sequences are immutable")) (defmethod sequence:make-sequence-like ((interval interval-sequence) length &key (initial-element nil iep) (initial-contents nil icp)) (declare (ignore initial-element initial-contents)) (when (or iep icp) (error "Can't create intervals using initial-element/initial-contents.")) (make-instance 'interval-sequence :minimum nil :length length))
An odd bit above is the notion of uninitialized sequences (where length is known, but not the minimum) and the behavior of (setf elt). Intervals are considered immutable, but (setf elt) is permitted provided it would not change the sequence. It is also permitted when minimum is unset, in which case it completes initialization by setting minimum to (- newvalue index). Intended to support initialization of intervals by map, this allows a neat trick:
(map 'interval-sequence (lambda (x) (+ x 7)) (below 5)) => #<INTERVAL-SEQUENCE [7,12)>
I thought there was some chance that remove would just work in the case where the element is on an end of the interval. It doesn't. The reason is that generic remove is implementing by calling delete on a copy of the sequence. As there is no way to distinguish destructive operations on a full copy during initialization from any other time, it seems like any immutable sequence has a bit more work to do in implementing the (non-destructive) utility functions.
I've filed my implementation away here in case anyone is interested.