list - 列表差异函数

Question

任何现有的编程语言，特别是在 Lisp 或 ML 系列中，是否有一个库函数来计算“从第一个直到第二个开始”的意义上的列表差异 - 我不确定它应该被准确地称为什么 - 例如，将字符串视为字符列表，如果输入是：

abcdef
def

那么输出将是

abc

Answer 1

Common Lisp 中的代码：

CL-USER 1 > (defun fusos (s1 s2)
              (let ((pos (search s2 s1)))
                (when pos (subseq s1 0 pos))))
FUSOS

CL-USER 2 > (fusos '(a b c d e f) '(d e f))
(A B C)

Answer 2

已经有一个公认的答案，但 Common Lisp LDIFF（“列表差异”的缩写）仍然值得一提。它基于列表的结构（构成列表的 cons 单元格）而不是列表的元素，因此被“减去”的列表必须与列表的某个尾部相同的 cons 单元格。它更具体一点，但它肯定会计算列表差异。

CL-USER> (let* ((abcdef '(a b c d e f))
                (def (cdddr abcdef)))
           (ldiff abcdef def))
(A B C)

Answer 3

由于takeWhile在评论中提到并且 Haskell 具有此功能，因此您可以通过以下方式在 Haskell 中实现所需的结果：

takeWhile (flip notElem ys) xs

你的例子在哪里

takeWhile (flip notElem "def") "abcdef"

也就是说，只要元素xs不包含在列表中，您就可以从列表中获取元素ys。一旦你找到一个包含在ys（或到达xs）中的元素，你就会停下来。

在标准 ML 中，它将是：

fun take_while p [] = []
  | take_while p (x::xs) =
    if p x then x :: take_while p xs
    else []

编辑：上面，我假设规范是我们在第一个列表中停止，只要我们找到第二个列表的（任意）元素。因此使用takeWhile. 但是，从 OP 来看，我不清楚实际的规范是什么。如果从输入（第一个列表）中删除现有的后缀（第二个列表），那么解决方案当然是不同的。在 Haskell 中，不考虑效率，我们可以这样做：

removeSuffix [] ys = []
removeSuffix xs@(z:zs) ys
  | xs == ys = []
  | otherwise = z : removeSuffix zs ys