Page 1 of 1

Help understanding my error

Posted: Wed Nov 07, 2012 8:09 pm
by ainsoph
I posted this on Common Lisp area because that's what I'm learning, but only after submitting it I realized this is the best place to ask questions about "learning"/homework. Sorry for the duplicate post, it won't happen again. If the moderators want to discard my first post on CL area, ok.

Hi. I'm completely new to Common Lisp and trying to learn something about functional programming . I'm using SBCL on OS X with Emacs/Slime. I'm trying to do the exercises of Paul Graham's book, ANSI Common Lisp, and there's one that it seams to be ok to me but it doesn't give the right answer. Exercise 3-5 asks for a recursive function that takes a list and returns another list of each element plus its position. So,

Code: Select all

> (pos+ '(7 5 1 4))
(7 6 3 7)
My code is bellow, and when I call the function with the same list above the answer is only (7). Can anyone tell me what I'm doing wrong?

Code: Select all

(defun pos+ (lst)
  (pos-rec lst 0 ()))

(defun pos-rec (lst i result)
  (if lst
      (progn (push (+ (car lst) i) result)
	        (pos-rec (cdr lst) (+ i 1) result)))
  result)

Re: Help understanding my error

Posted: Thu Nov 08, 2012 12:34 pm
by ramarren
First problem is that your recursion doesn't have a proper base case. Your IF doesn't have an else branch, so the result variable is returned as is, which is affected only by the first PUSH. This can actually be seen by indentation.

Second problem is that you are trying to use PUSH in the first place. There is an issue with mutability of lists (PUSH doesn't mutate a list, it sets a variable to a list with a new head), but anyway recursive code is usually supposed to be functional, that is, you are supposed to create new bindings by calling functions with new values as parameters. In this case rather that trying to modify the result list, you should pass the extended (by CONS-ing a new head) list to the recursive call.

Also note that CONS extends the list from the front. It is a common idiom in Lisp-like languages to build lists this way and reverse them at the end of computation.