Loading ...
Sorry, an error occurred while loading the content.

Complex returns from recursive functions - tail recursion?

Expand Messages
  • Robert Futrelle
    This is more a straight Lisp question, but it relates to material in the early chapters of PAIP. (Someone can direct me to a better list for this, I m sure.)
    Message 1 of 5 , Jan 29, 2006
    • 0 Attachment
      This is more a straight Lisp question, but it relates to material in
      the early chapters of PAIP. (Someone can direct me to a better list
      for this, I'm sure.)

      This function splits an even-length list into its even and odd
      (sequence) elements:

      (defun split-list (lst)
      (cond ((null lst) '(() ()))
      (t (let ((lst2 (split-list (rest (rest lst)))))
      (list (cons (first lst) (first lst2))
      (cons (second lst) (second lst2)))
      )
      )
      )
      )

      Point being, there's more to recursion than consing up a single list.

      Execution:

      1 > (split-list '(b d i o g g))
      ((B I G) (D O G))

      I assume it's not tail-recursive.
      Can it be made so using multiple-value return?

      (this is not a quiz, just a question ;-)

      - Bob Futrelle

      PS: I think there's no separate PAIP list.

      PPS: ';-)' is a closing bracket in the SMILEY programming language.
    • Steven Shaw
      ... I can say that it s not tail recursive. I couldn t spot it at first because the simple form to look for is a recursive call embedded in an argument
      Message 2 of 5 , Jan 29, 2006
      • 0 Attachment
        On 29/01/06, Robert Futrelle <futrelle@...> wrote:
        > This is more a straight Lisp question, but it relates to material in
        > the early chapters of PAIP. (Someone can direct me to a better list
        > for this, I'm sure.)
        >
        > This function splits an even-length list into its even and odd
        > (sequence) elements:
        >
        > (defun split-list (lst)
        > (cond ((null lst) '(() ()))
        > (t (let ((lst2 (split-list (rest (rest lst)))))
        > (list (cons (first lst) (first lst2))
        > (cons (second lst) (second lst2)))
        > )
        > )
        > )
        > )
        >
        > Point being, there's more to recursion than consing up a single list.
        >
        > Execution:
        >
        > 1 > (split-list '(b d i o g g))
        > ((B I G) (D O G))
        >
        > I assume it's not tail-recursive.

        I can say that it's not tail recursive. I couldn't spot it at first
        because the simple form to look for is a recursive call embedded in an
        argument position (I don't know the correct terminology), like "(cons
        lst (split-list ...". However, the problem is that the result of the
        recursive call is bound to lst2 and then there is more to do. It's
        just that the lst2 is used twice so it's an optimisation.

        > Can it be made so using multiple-value return?

        Not sure but I think not. Multiple return value is like an
        optimisation for returning a tuple (a pair in this case). Using
        mutiple return values might prevent consing of the pair and use of
        registers for both return values. It doesn't mean change the fact that
        this technique needs to do something (cons) with the results of a call
        to split-list. What do you think?

        > (this is not a quiz, just a question ;-)

        Seems like a quiz :)

        Steve.
        --
        Steven Shaw http://abstractsimplicity.co.uk/
      • Steven Shaw
        Here s version that s tail recursive though I don t think very efficient because of my use of append and list perhaps were not necessary. (defun split-list2
        Message 3 of 5 , Jan 29, 2006
        • 0 Attachment
          Here's version that's tail recursive though I don't think very
          efficient because of my use of append and list perhaps were not
          necessary.

          (defun split-list2 (list)
          (let ((a (list)) (b (list)))
          (split-list2-helper list a b)))

          (defun split-list2-helper (list firsts seconds)
          (cond ((null list) (list firsts seconds))
          (t (split-list2-helper
          (rest (rest list))
          (append firsts (list (first list)))
          (append seconds (list (second list)))))))

          Also, I forget the syntax for defining inner auxilary functions...
          flet, labels, defun??...

          Steve.
        • Peter Norvig
          How about this: (defun split-list (lst) (let ((odds nil) (evens nil)) (loop for x in lst for i from 1 do (if (oddp i) (push x odds) (push x evens))) (list
          Message 4 of 5 , Jan 29, 2006
          • 0 Attachment
            How about this:

            (defun split-list (lst)
            (let ((odds nil)
            (evens nil))
            (loop for x in lst for i from 1 do
            (if (oddp i) (push x odds) (push x evens)))
            (list (nreverse odds) (nreverse evens))))

            No problem with running out of stack space there.

            Or if you're an even bigger fan of LOOP, you can do:

            (defun split-list2 (lst)
            (loop for x in lst for i from 1
            when (oddp i)
            collect x into odds
            else
            collect x into evens
            finally (return (list odds evens))))

            -Peter

            On 1/29/06, Robert Futrelle <futrelle@...> wrote:
            > This is more a straight Lisp question, but it relates to material in
            > the early chapters of PAIP. (Someone can direct me to a better list
            > for this, I'm sure.)
            >
            > This function splits an even-length list into its even and odd
            > (sequence) elements:
            >
            > (defun split-list (lst)
            > (cond ((null lst) '(() ()))
            > (t (let ((lst2 (split-list (rest (rest lst)))))
            > (list (cons (first lst) (first lst2))
            > (cons (second lst) (second lst2)))
            > )
            > )
            > )
            > )
            >
            > Point being, there's more to recursion than consing up a single list.
            >
            > Execution:
            >
            > 1 > (split-list '(b d i o g g))
            > ((B I G) (D O G))
            >
            > I assume it's not tail-recursive.
            > Can it be made so using multiple-value return?
            >
            > (this is not a quiz, just a question ;-)
            >
            > - Bob Futrelle
            >
            > PS: I think there's no separate PAIP list.
            >
            > PPS: ';-)' is a closing bracket in the SMILEY programming language.
            >
            >
            >
            >
            >
            > Yahoo! Groups Links
            >
            >
            >
            >
            >
            >
            >
          • Steven Shaw
            ... Looks good. I could have done with nvreverse myself!
            Message 5 of 5 , Jan 29, 2006
            • 0 Attachment
              On 29/01/06, Peter Norvig <peter@...> wrote:
              > How about this:

              Looks good. I could have done with nvreverse myself!
            Your message has been successfully submitted and would be delivered to recipients shortly.