CODEWITHSUNDEEP
lispcommon-lispsmlmutual-recursion
Krishnan Ravikumar
Krishnan Ravikumar

Reputation: 295

Mutual Recursion in Common Lisp

This is the Common Lisp code:

(defun take (L)
  (if (null L) nil
     (cons (car L) (skip (cdr L)))))

(defun skip (L)
  (if (null L) nil
     (cons (car L) (take (cdr L)))))

The idea here is that, "take" will give all the odd sequence elements in the input list and "skip" will give all the even sequence elements in the input list. However, in both cases the entire list is returned.

What is the error in this code? Is this something to do with how CL handles lists, because the similar code in SML gives the desired output.

fun take(lst) = 
     if lst = nil then nil 
     else hd(lst)::skip(tl(lst))
and
    skip(lst) = 
     if lst = nil then nil 
     else hd(lst)::take(tl(lst));

Upvotes: 1

Views: 970

Answers (3)

Will Ness
Will Ness

Reputation: 71065

To expound on what Sylwester has said, your skip is wrong in both Lisp and SML. It should be

(defun take (L)         ; even-indexed elements of a list L
  (if (not (null L))
     (cons (car L) (skip (cdr L)))))

(defun skip (L)         ; odd-indexed elements of a list L
  (if (not (null L))
     (take (cdr L))))

and

fun take(lst) = 
     if lst = nil then nil 
     else hd(lst)::skip(tl(lst))
and
    skip(lst) = 
     if lst = nil then nil 
     else take(tl(lst));

Upvotes: 4

Joshua Taylor
Joshua Taylor

Reputation: 85833

It's worth pointing out that indexing in Common Lisp (like many other programming languages) starts with 0, so the even-indexed elements of a list are the first, the third, the fifth, and so on, since those have indices 0, 2, 4, etc. It's also worth noting that in Common Lisp, you can take the rest of the empty list and get back the empty list. (You can't do this in every Lisp, though. E.g., in Scheme it's an error to call cdr on something that's not a pair.) This means that you can implement even-elements and odd-elements rather easily. even-elementsjust returns a list of the first element, and the odd elements of the rest of the list. odd-elements returns the even-elements of the rest of the list:

(defun even-elements (list)
  (if (endp list) list
      (list* (first list) (odd-elements (rest list)))))

(defun odd-elements (list)
  (even-elements (rest list)))

These behave in the expected fashion:

CL-USER> (even-elements '(0 1 2 3 4 5))
(0 2 4)
CL-USER> (odd-elements '(0 1 2 3 4 5))
(1 3 5)

Of course, if you note that the call to (odd-elements x) is just a call to (even-elements (rest x)), we could have implemented even-elements as follows, and had the same result:

(defun even-elements (list)
  (if (endp list) list
      (list* (first list) (even-elements (rest (rest list))))))

Upvotes: 2

Sylwester
Sylwester

Reputation: 48745

The take and skip are identical so that is no mystery. skip should just tail call instead of cons-ing. It's the consing that makes the return here.

Upvotes: 3

Related Questions