SML映射过滤器？

Question

如果我有这个代码：

fun coord_select (x : int, cs : (int*int) list) =
         List.filter (fn (first, _) => first = x ) cs

测试输入给出了这个：

coord_select (2, [(2,2),(2,3),(3,3),(4,3)])
: val it = [(2,2),(2,3)] : (int * int) list

现在，如果我没有将所需的第一个坐标作为 int 而是作为几个所需的第一个坐标的列表（例如 [3,4]），即我想要所有坐标元组怎么办从 3 和 4 开始？简单的方法就是围绕它创建一个递归包装器，它遍历列表并将值作为 coord_select 的第一个变量插入。但我想比这种蛮力更好地理解嵌套的东西。所以我想到了这个：

fun coord_match (fs : int list, cs :(int*int) list) =
         map (coord_select (f, cs)) fs

但这实际上行不通，因为正如所指出的那样，map 中的 coord_select 实际上是在尝试 return 一个列表——而 map 知道首先将 fs 的成员插入 f 吗？ Common Lisp 确实有一种方法可以使运行中的函数保持不变，即 ' 运算符。但这同样无济于事，因为 map 不知道 fs 提供的是哪个变量。对于输入，例如，我有这些坐标：

[(2,2),(2,3),(3,3),(4,3)]

我有这个 x 坐标列表来匹配上面的列表

[3,4]

同样，我可以围绕它放置一个递归包装器，但我正在寻求更大的 fold 系列中更优雅的嵌套解决方案。

Answer 1

what if I don't give the desired first coordinate as an int but as a list of several required first coordinates such as [3,4], i.e., I want all coordinate tuples that start with 3 and 4

听起来你想要所有以 3 或 4 开头的坐标元组，因为坐标不能同时为 3 和 4.

鉴于此，您可以这样写 coord_select：

fun member (x, xs) =
    List.exists (fn x2 => x = x2) xs

fun coord_select (xs, coords) =
    List.filter (fn (x, _) => member (x, xs)) coords

the greater fold family

这个家族叫做catamorphisms，属于map、filter、exists和foldl。由于 foldl 是其中最通用的，因此在技术上可以完全使用折叠来编写上面的代码：

fun coord_select (xs, coords) =
    foldr (fn ((x, y), acc1) =>
      if foldl (fn (x2, acc2) => acc2 orelse x = x2) false xs
      then (x, y) :: acc1
      else acc1) [] coords

但显而易见的是，显式折叠的可读性不高。

如果有一个专门的组合器可以完成某项工作，您宁愿将其折叠起来。如果它不存在，从稍微不太专业的组合器创建它可以提高可读性。折叠尽可能接近手动递归，因此向 reader 提供的关于我们正在尝试哪种递归的信息很少。

出于这个原因，我还从 exists 制作了 member，因为 exists 要求我指定一个谓词，而我的谓词是 "equality with x"；所以我觉得 exists 也会给 coord_select 函数增加混乱。

您可以通过阅读 Meijer、Fokkinga、Paterson 的 Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire (1991) 了解有关函数式编程中的列表变形的更多信息。

SML映射过滤器？

SML map a filter?

sml

fold