Function won't recurse?!!

Discussion of Common Lisp
Post Reply
macrolyte
Posts: 40
Joined: Sat Jan 25, 2014 8:56 pm
Location: The wilderness of North America

Function won't recurse?!!

Post by macrolyte » Sat Mar 22, 2014 2:47 pm

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?!!

Post by macrolyte » Sat Mar 22, 2014 3:43 pm

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?!!

Post by macrolyte » Sat Mar 22, 2014 4:49 pm

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!

sylwester
Posts: 133
Joined: Mon Jul 11, 2011 2:53 pm

Re: Function won't recurse?!!

Post by sylwester » Sat Mar 22, 2014 5:50 pm

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

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

Re: Function won't recurse?!!

Post by macrolyte » Sat Mar 22, 2014 6:39 pm

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! 8-)
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.

Post Reply