Page 1 of 1
Function won't recurse?!!
Posted: Sat Mar 22, 2014 2:47 pm
by macrolyte
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.
Re: Function won't recurse?!!
Posted: Sat Mar 22, 2014 3:43 pm
by macrolyte
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.
Re: Function won't recurse?!!
Posted: Sat Mar 22, 2014 4:49 pm
by macrolyte
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!
Re: Function won't recurse?!!
Posted: Sat Mar 22, 2014 5:50 pm
by sylwester
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)))
Re: Function won't recurse?!!
Posted: Sat Mar 22, 2014 6:39 pm
by macrolyte
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.