## Function won't recurse?!!

Discussion of Common Lisp

### Function won't recurse?!!

This has been driving me crazy for the last hour and a half. I know that I'm probably going to kick myself in the head when I know the answer, but here:

Code: Select all
`(defun dotted-pair(lst)                                                                        ; lst:= a list  (labels ((dp (i lst)                                                                                      (if (or (eq lst nil) (not (eq (mod (list-length lst) 2) 0)))                                       nil                                                                                            (append (list (cons (first lst) i)) (dp (1+ i)(rest lst))))))                     (dp 1 lst)))   `

The function returns the head of the list, then stops:

Code: Select all
`(dotted-pair ())         ; => nil(dotted-pair '(a b c)    ; => nil(dotted-pair '(v x y z)  ; => ((V.1))`

I also wanted to know if there was a better way of constructing the list that would be better than my method, but for right now I'd settle for an answer to this. I know it's something simple, I just can't see it. Danke.
macrolyte

Posts: 40
Joined: Sat Jan 25, 2014 8:56 pm
Location: The wilderness of North America

### Re: Function won't recurse?!!

I've found the problem, the predicate in the if is getting tested again!

Code: Select all
`             (if (or (eq lst nil) (not (eq (mod (list-length lst) 2) 0))) ;; culprit! test performed on each recursion.`

I just need to restructure my code. I'll post the corrected code as soon as I get done.
macrolyte

Posts: 40
Joined: Sat Jan 25, 2014 8:56 pm
Location: The wilderness of North America

### Re: Function won't recurse?!!

And now:

Code: Select all
`(defun dotted-list(lst)                                                                          (if (or (eq lst nil) (not (eq (mod (list-length lst) 2) 0)))                                       nil                                                                                            (labels ((dp (i lst)                                                                                      (if (eq lst nil)                                 ; check for nil again or suffer stack overflow                     nil                                                                                            (append (list (cons (first lst) i)) (dp (1+ i)(rest lst))))))        (dp 1 lst)))) (dotted-list '(a b c d))  ; => ((A . 1) (B . 2) (C . 3) (D . 4))`

So back to the question I wanted to ask originally, is there a better way of doing this(eg. iteratively, et al)? I only ask since I see using this data structure(?) a lot. Thanks!
macrolyte

Posts: 40
Joined: Sat Jan 25, 2014 8:56 pm
Location: The wilderness of North America

### Re: Function won't recurse?!!

A tail recursive solution (but it still needs help with TCO from the implementation not to blow the stack)
Since all the structure is made within the function it's safe to do du destructive reverse.

Code: Select all
`(defun dotted-list (lst)  (labels ((aux (lst i acc)        (if lst       (aux (cdr lst) (1+ i) (cons (cons (car lst) i) acc))       (nreverse acc))))    (aux lst 1 '())))`

Since CL is not guaranteed to be tail recursive, something like this is probably the best solution:

Code: Select all
`(defun dotted-list (lst)   (loop for e in lst         for n from 1         collect (cons e n)))`
I'm the author of two useless languages that uses BF as target machine.
Currently I'm planning a Scheme compiler :p
sylwester

Posts: 83
Joined: Mon Jul 11, 2011 2:53 pm

### Re: Function won't recurse?!!

sylwester wrote:A tail recursive solution (but it still needs help with TCO from the implementation not to blow the stack)
Since all the structure is made within the function it's safe to do du destructive reverse.

Code: Select all
`(defun dotted-list (lst)  (labels ((aux (lst i acc)        (if lst       (aux (cdr lst) (1+ i) (cons (cons (car lst) i) acc))       (nreverse acc))))    (aux lst 1 '())))`

It's Saturday night where I am, and you're gonna make me read the HyperSpec on nreverse now? Okay!

sylwester wrote:Since CL is not guaranteed to be tail recursive, something like this is probably the best solution:

Code: Select all
`(defun dotted-list (lst)   (loop for e in lst         for n from 1         collect (cons e n)))`

Kind of what I thought, sigh... Still, I prefer my new diet of parentheses to just drinking coffee. Seriously though, I have to eat something. Ciao.
macrolyte

Posts: 40
Joined: Sat Jan 25, 2014 8:56 pm
Location: The wilderness of North America