CODEWITHSUNDEEP
lispcommon-lisp
Jiang Xiang
Jiang Xiang

Reputation: 3256

Implementing length recursively for arbitrary sequences, not just lists

I am new to Lisp and want to implement the function length with recursion. I have written the following code only to find that it can only work for lists but not for strings.

(defun mylen (l)
  (if (eq (cdr l) nil)
    1
    (+ 1 (mylen (cdr l)))))

I wonder is it possible for me to write only one function that can both work for lists and strings?

Upvotes: 0

Views: 1996

Answers (4)

Joshua Taylor
Joshua Taylor

Reputation: 85853

Use sequence functions for arbitrary sequences

First, note that Common Lisp's length works on any sequence, not just lists (and not just strings, &c.). So you don't actually need to write this at all. There are some other functions that operate over sequences in general, such as map. In general, it's not all that easy to write generic code that if efficient on both lists and vectors. Implementations often implement functions that take arbitrary sequences by checking what kind of sequence has been provided first, and then using a specialized version. It's to your advantage to use those functions when they are available. You can have a look in the 17.3 Sequences Dictionary from the HyperSpec for more functions that operate on arbitrary sequences.

You could use map and implement a sequence-length like this:

(defun sequence-length (sequence &aux (length 0))
  (map nil (lambda (x)
             (declare (ignore x))
             (incf length))
       sequence)
  length)

The sequence-length above just highlights that map works on each. A more idiomatic solution would use another function that works on sequences in general, reduce, as Rainer Joswig points out (this code is based on the code in his answer, but uses constantly to create a function that ignores its arguments and returns 1):

(defun sequence-length (sequence)
  (reduce '+ sequence :key (constantly 1)))

CL-USER> (sequence-length '(1 2 3))
3
CL-USER> (sequence-length "foobar")
6

Another alternative would be to use count-if As in

(count-if (constantly t) sequence)

which counts the number of items for which (constantly t) returns true, which is all of them.

Writing your own sequence functions

The kind of recursion that you're implementing, though, does depend on lists built of cons cells that you make it easy to handle the first part of a list and then the rest of the list. There aren't functions that do that for sequences in general, because getting the rest of a vector usually means taking a copy of it. Usually, if something like this is needed, the function takes a start and end index, and recurses on those, rather than on the sequence. E.g.,

(defun list-elements (sequence start end)
  (if (= start end)
      '()
      (cons (elt sequence start)
            (list-elements sequence (1+ start) end))))

CL-USER> (list-elements "abcdefghijklmnop" 3 7)
(#\d #\e #\f #\g)

Most implementations of reduce are simply going to check whether the sequence is a list or a vector, and then dispatch to a specialized version that handles these in the most appropriate way. For instance, if you look at SBCL's implementation of reduce (start around line 1242), you'll see implementations of four macros of some sort:

  1. mumble-reduce
  2. mumble-reduce-from-end
  3. list-reduce
  4. list-reduce-from-end

and one sequence traverser:

  • reduce

You'll need to know more about the defining forms in SBCL to know how those are all used, but they do demonstrate that implementing generic sequence functions is a bit of work.

An inefficient first element/rest of sequence, for completeness

After saying all that, I will point out that you can use subseq, which works on arbitrary sequences, to do this kind of recursion on both vectors and lists, but it really won't be efficient. For instance, here's a trivial reverse-into-list function.

(defun reverse-into-list (sequence &optional (result '()))
  (if (eql 0 (length sequence))
      result
      (reverse-into-list (subseq sequence 1) 
                         (cons (elt sequence 0) result))))

CL-USER> (reverse-into-list "hello")
(#\o #\l #\l #\e #\h)
CL-USER> (reverse-into-list '(1 2 3))
(3 2 1)

That used length to determine when to stop, but you could write a more efficient version that first checks whether it's a list, and if it is, checks whether it's empty or not (constant time), and if it's not a list, just calls length (which should also be constant time).

Upvotes: 4

Rainer Joswig
Rainer Joswig

Reputation: 139261

Just to add to the answer of Joshua: not map, use reduce:

(reduce #'+ sequence :key (constantly 1))

To compute the length of strings is kind of useless in Lisp, since every vector stores the length as an attribute - there is no end marker like in C. Thus the length of a vector - and a string is a vector - does not need to be computed in Lisp.

Upvotes: 3

Lars Brinkhoff
Lars Brinkhoff

Reputation: 14305

It's possible to extract the "rest" from a sequence and only cons a small amount if it's a vector: 

(defun sequence-rest (seq)
  (if (listp seq)
      (rest seq)
      ;; A full version would also care about element-type etc.
      (make-array (1- (length seq)) :displaced-to seq
                  :displaced-index-offset 1)))

(defun mylen (seq)
  (if (zerop (length seq))
    1
    (+ 1 (mylen (sequence-rest seq)))))

Upvotes: 1

Rörd
Rörd

Reputation: 6681

Your Lisp implementation's standard library length function probably works on strings and other vectors by accessing some internal attribute. But if you want to calculate the length of vectors recursively anyway, your best bet would probably be to coerce them to lists. Vectors just are not inherently recursive data structures the way that lists are.

By the way, your current implementation is buggy for lists, too. It will fail (i.e. return 1 instead of 0) for empty lists. You can make it work correctly for empty lists by simplifying it.

Upvotes: 1

Related Questions