algorithm - 测试一个列表是否是另一个列表的子列表而不测试元素之间的相等性

Question

我想知道是否可以编写一个函数式程序(如在 Haskell 或 OCaml 中)，它接受两个列表并确定第一个是否是第二个的子列表，具有程序不能调用列表元素之间的相等性的属性.

更一般地说，是否存在适用于任意类型元素列表的程序？也就是说，(在 Haskell 术语中)类型不必受 Eq、Ord 或别的东西。

我问这个的原因是，在处理任意类型的元素列表时，这些元素有时不支持标准相等性(如整数、字符串等)。但是，测试子列表会很有帮助。

我一直想不出满足这个条件的实现。是否可以创建一个？

Answer 1

没有相等性，关系 is_sublist 是无意义的:[x] `is_sublist` [y] 应该为真当且仅当 x = 是。相反，如果这样的函数 is_sublist 存在，它将定义一个相等函数为 eq x y = [x] `is_sublist` [y] 。