Lisp recursion with lists

Question

I need a function that will take in a list with words and split that list into two lists if at any point the word 'FOO' is found. I have come up with a recursive solution, may not be the best, but I am having a bit of trouble. I only need to pass 1 argument, the list to be analyzed, but I do not know how to build up the second list off to the side. Any suggestions? Thanks!

;Splits a list into 2 if the word 'FOO' is present
;----------------------------------------------------------------------
;LOAD FILE: (load "C:\\split.lisp")
;USAGE: (split '(with great power foo comes great responsibility) '())
;OUTPUT: ((with great power)(comes great responsibility))

(defun split (x y)
  (cond
    ( ;IF: first element in list is nil
      (EQ (car x) nil)
        x ;RETURN the list
    )
    ( ;ELSE IF: first element is 'FOO'
      (EQ (car x) 'FOO)
        (cons (reverse y ) (cons (cdr x) nil)) 
    )
    ( ;ELSE: recursively call split but pass the rest of x and 
      ;prepend y with the head of x
      t
        (split (cdr x) (cons (car x) y))
    )
  ) ;END cond
) ;END split

*Please* indent your code properly. Just google "lisp indentation" or "lisp style guide" to learn how it's done. Your code will be much easier to read for those you're asking for help (and also for yourself, after you get used to it). Editors like Emacs do it automatically, and show matching parens. Lisp code isn't read by aligning parens, but by indentation. — danlei, Sep 03 '12 at 17:03
Sorry, I am learning. I am so used to C comments. I did run across [this post](http://stackoverflow.com/questions/6365334/lisp-commenting-convention) which describes how to comment. Reminds me of assembly comments. — , Sep 03 '12 at 17:30
No problem. Something like http://dept-info.labri.u-bordeaux.fr/~idurand/enseignement/PFS/Common/Strandh-Tutorial/indentation.html should get you started. (If you are using Emacs, just ignore the setup hints given there, and use [SLIME](http://common-lisp.net/project/slime/)). — danlei, Sep 03 '12 at 18:43

score 3 · Answer 1 · answered Sep 03 '12 at 07:48

The first test should be different.

The following is not a really good solution: it is not tail-recursive and it uses side-effects. But still...

(defun split (x)
  (cond ((null x) x)
        ((eq (first x) 'foo)
         (list nil (rest x)))
        (t (let ((l (split (rest x))))
             (push (first x) (first l))
             l))))

Above uses the PUSH macro. One of the interesting facilities of Common Lisp is that you can use places to modify. In this cases we modify the first sublist of our list to be returned. We push the first element of the list onto the first sublist.

CL-USER 12 > (split '(1 2 3 foo a b c))
((1 2 3) (A B C))

In Common Lisp one would usually write a solution in a non-recursive fashion.

In your recursive version, the typical way to reduce a function to one argument is this: Write the function with one argument and this function then calls a helper function with two arguments. The helper function can also be locally defined using LABELS.

score 2 · Answer 2 · answered Sep 27 '12 at 21:37

Here's my take on it, using nothing but lists:

(defun split (lst)
  (labels ((split-rec (lst a)
    (cond
      ((or (null lst)
           (eq (car lst) 'foo))
             (values (reverse a) (cdr lst)))
      (t (split-rec (cdr lst) (cons (car lst) a))))))

    (split-rec lst ())))

split offloads most of the work to split-rec (defined in the labels call), which recursively consumes the list of tokens, until it reaches the end of the list, or sees 'foo. At that point, it immediately takes the remainder of the list and treats that as the second list. Because the first list (a) is being built-up recursively, split-rec has to reverse it before returning it.

Here are a couple of runs through the REPL:

> (split '(with great power foo comes great responsibility))
(WITH GREAT POWER) ;
(COMES GREAT RESPONSIBILITY)

> (split '(with great power comes great responsibility))
(WITH GREAT POWER COMES GREAT RESPONSIBILITY) ;
NIL

> (split nil)
NIL ;
NIL

> (split '(with great power foo comes great foo responsibility) :on 'foo)
(COMES GREAT) ;
(WITH GREAT POWER RESPONSIBILITY)

> (split '(foo with great power comes great responsibility) :on 'foo)
NIL ;
(WITH GREAT POWER COMES GREAT RESPONSIBILITY)

Most of the edge cases that I could think up are handled, and two lists are always returned. Callers can use multiple-value-bind to get both lists out, i.e.:

(multiple-value-bind (a b)
  (split '(with great power foo comes great responsibility))
    ; do something useful with a and b
    )

momo · Answer 3 · 2012-09-03T13:28:03.730

(defun split (lst)
  (let* ((a (make-array (length lst) :initial-contents lst))
         (index (position 'foo a)))
    (cond ((null index) a)
          (t (cons (loop for i from 0 to (1- index)
                      collect (aref a i))
               (list (loop for i from (1+ index) to (1- (length a))
                        collect (aref a i))))))))

Create an array from the list so that there elements are easier to access.
Check if foo exists, if it does mark the index
Use loop to create two lists, one of the elements before foo, and another one of the elements after foo, and cons them together.

score 0 · Answer 4 · answered Sep 04 '12 at 20:03

Here I've also tried! :)

There's one thing you would want to clarify though: in corner cases like: foo is the first element of the list, should you return two lists or only the second one? If foo is the last element in the list, should you return list and nil or only the first list? If foo isn't in the list, should you return just the list, or list and nil / nil and list?

(defun split (list &key (on-symbol 'foo))
  (let (result result-head)
    (mapl
     #'(lambda (a)
         (if (eql (car a) on-symbol)
             (return-from split
               (if result
                   (values result (copy-list (cdr a)))
                   (copy-list (cdr a))))
             (if result
                 (setf (cdr result-head) (list (car a))
                       result-head (cdr result-head))
                 (setf result (list (car a))
                       result-head result)))) list) result))

(split '(1 2 3 4 5 foo a b c))
(split '(foo 1 2 3 4 5 foo a b c))
(split '(1 2 3 4 5 a b c))

Lisp recursion with lists

4 Answers4