CODEWITHSUNDEEP
lispcommon-lisp
user658096
user658096

Reputation:

Lisp recursion with lists

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

Upvotes: 2

Views: 6752

Answers (4)

jrhunt
jrhunt

Reputation: 21

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
    )

Upvotes: 2

user797257
user797257

Reputation:

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))

Upvotes: 0

momo
momo

Reputation: 1045

(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.

Upvotes: 1

Rainer Joswig
Rainer Joswig

Reputation: 139401

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.

Upvotes: 3

Related Questions