2

我需要一个函数，该函数将接收一个包含单词的列表，并将该列表拆分为两个列表，如果在任何时候找到单词“FOO”。我想出了一个递归解决方案，可能不是最好的，但我遇到了一些麻烦。我只需要传递 1 个参数，即要分析的列表，但我不知道如何构建第二个列表。有什么建议么？谢谢！

;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
4

4 回答 4

3

第一次测试应该不同。

以下不是一个非常好的解决方案：它不是尾递归的并且它使用副作用。但是还是...

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

以上使用PUSH宏。Common Lisp 的有趣功能之一是您可以使用位置进行修改。在这种情况下，我们修改要返回的列表的第一个子列表。我们将列表的第一个元素推送到第一个子列表中。

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

在 Common Lisp 中，人们通常会以非递归方式编写解决方案。

在您的递归版本中，将函数简化为一个参数的典型方法是：用一个参数编写函数，然后该函数调用一个带有两个参数的辅助函数。辅助函数也可以使用本地定义LABELS。

于 2012-09-03T07:48:51.013 回答
2

这是我的看法，只使用列表：

(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将大部分工作卸载到split-rec（在labels调用中定义），它递归地使用令牌列表，直到它到达列表的末尾，或者看到 'foo. 此时，它立即获取列表的其余部分并将其视为第二个列表。因为第一个列表 (a) 是递归构建的，所以 split-rec 必须在返回之前反转它。

以下是 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)

我能想到的大多数边缘情况都得到了处理，并且总是返回两个列表。来电者可以使用multiple-value-bind来获取两个列表，即：

(multiple-value-bind (a b)
  (split '(with great power foo comes great responsibility))
    ; do something useful with a and b
    )
于 2012-09-27T21:37:20.197 回答
1 
(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))))))))
  • 从列表中创建一个数组，以便更容易访问其中的元素。
  • 检查 foo 是否存在，如果它确实标记了索引
  • 使用循环创建两个列表，一个是 foo 之前的元素，另一个是 foo 之后的元素，并将它们组合在一起。
于 2012-09-03T13:19:07.797 回答
0

这里我也试过！:)

不过，您需要澄清一件事：在极端情况下，例如：foo是列表的第一个元素，您应该返回两个列表还是只返回第二个？如果foo是列表中的最后一个元素，您应该返回列表nil还是只返回第一个列表？如果foo不在列表中，您应该只返回列表，还是列表和nil/nil和列表？

(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))
于 2012-09-04T20:03:46.483 回答