使用折叠/映射比较 SML 中的两个列表

Question

假设我有两个列表，[1,2,3]和[9,2,3]。假设我得到了第三个值，2 .如果我想找出这个值是否在两个列表中，但我只能使用 foldl/foldr/map 来做到这一点(没有让环境或 map/foldr/foldl 之外的自定义递归(，我该怎么做？这是编程课的家庭作业问题，我已经坚持了一个星期了。

Answer 1

您可以做很多事情来处理此作业：

1. 为函数编写一个存根，以便您知道自己在处理什么：

   fun isInBoth (xs, ys, z) = ...
   

   其中此函数返回布尔类型的东西。

2. 想想如果它只是一个列表中的成员身份，你会如何解决这个问题：

   (* Using built-in functions *)
   fun isInList (xs, z) = List.exists (fn x => x = z) xs
   (* Using recursion directly *)
   fun isInList ([], z) = false
     | isInList (x::xs, z) = x = z orelse isInList (xs, z)
   

3. 排除使用 map ，因为这会产生一个 'b 列表，而不是布尔值。

4. 继续使用仅一个列表的折叠来解决此问题：

   fun isInList (xs, z) = foldl (fn (x, acc) => ...) ... xs
   

   其中acc是foldl在每次递归调用时累积的值。

   第一个...必须反映列表中x值的存在是否对函数的结果产生影响，或者是否有任何以前认为的元素产生了差异(使用 acc 作为代理(。

   第二个...是一个布尔值，表示xs为空时的默认值，并且是foldl执行的递归的基本情况。

   请注意，在标准 ML 中折叠是一个急切的过程：它会遍历整个列表，直到得出元素存在的结论。因此，平均而言，List.exists是搜索单个列表的更好组合器。在惰性求值语言中，折叠可能是等效的。

5. 继续解决两个列表的问题，很简单：

   fun isInBoth (xs, ys, z) = isInList (xs, z) andalso isInList(ys, z)
   

6. (可选(考虑如何将这两个递归调用交织在一起并创建成对折叠。实际上，有一个名为 ListPair.foldl 的函数是这样工作的：

   (* Finds the largest positive integer in two lists, or 0 *)
   fun max3 (x, y, z) = Int.max (x, Int.max(y, z))
   fun maxTwoLists (xs, ys) = ListPair.foldl max3 0 (xs, ys)
   

   但它有一个烦人的副作用：

   val huh = maxTwoLists ([1,2,3], [1,2,3,4])  (* gives 3 *)
   

   因此，如果你想遍历两个列表并成对地查看它们的元素，并在另一个列表结束时继续查找一个列表，并在满足或不再满足条件时停止折叠，那么您正在处理一个既List.foldl也不ListPair.foldl都支持开箱即用的递归方案。如果这不是需要折叠的学校练习，这将是一个解决方案：

   fun isInList (xs, z) = List.exists (fn x => x = z) xs
   fun isInBoth (x::xs, y::ys, z) =
       x = z andalso isInList (y::ys, z) orelse  (* no needs to look at more xs *)
       y = z andalso isInList (x::xs, z) orelse  (* no needs to look at more ys *)
       isInBoth (xs, ys, z)                      (* keep looking in both *)
     | isInBoth ([], ys, z) = false              (* not found in xs *)
     | isInBoth (xs, [], z) = false              (* not found in ys *)
   

   将递归模式抽象为类似于ListPair.foldl的函数可能不是那么有用。

Answer 2

您可以简单地使用foldl函数中的某种形式的保证，并与and运算符结合使用，如下所示：

fun intersection l1 l2 v = (#1 (foldl (fn (x,y) => if (x = (#2 y)) then (true, (#2 y)) else y) (false, v) l1)) andalso (#1 (foldl (fn (x,y) => if (x = (#2 y)) then (true, (#2 y)) else y) (false, v) l2))

这是优雅，简单和一行(尽管可以说，出于样式目的，您可能希望它在多行中(。