Function won't recurse?!!

Discussion of Common Lisp

Function won't recurse?!!

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

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

Postby 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!
macrolyte
 
Posts: 40
Joined: Sat Jan 25, 2014 8:56 pm
Location: The wilderness of North America

Re: Function won't recurse?!!

Postby 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
sylwester
 
Posts: 83
Joined: Mon Jul 11, 2011 2:53 pm

Re: Function won't recurse?!!

Postby 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.
macrolyte
 
Posts: 40
Joined: Sat Jan 25, 2014 8:56 pm
Location: The wilderness of North America


Return to Common Lisp

Who is online

Users browsing this forum: Google [Bot] and 4 guests