3

所以我是 sml 的新手，我试图了解它的来龙去脉。最近我尝试创建一个带有两个参数的过滤器：一个函数（返回一个布尔值）和一个针对该函数运行的值列表。过滤器的作用是返回对函数返回 true 的值列表。

代码：

fun filter f [] = []  |
   filter f (x::xs) =
      if (f x)
      then x::(filter f xs)
      else (filter f xs);

所以这行得通。但是我现在要做的只是返回一个包含真值列表和假的元组。我坚持我的条件，我真的看不到另一种方式。关于如何解决这个问题的任何想法？

代码：

fun filter2 f [] = ([],[])  |
   filter2 f (x::xs) =
      if (f x)
      then (x::(filter2 f xs), []) (* error *)
      else ([], x::(filter2 f xs)); (* error *)
4

2 回答 2

5

我认为有几种方法可以做到这一点。

重用过滤器

例如，我们可以使用归纳方法，基于您的元组将由两个元素组成的事实，第一个是满足谓词的元素列表，第二个是不满足谓词的元素列表。因此，您可以将过滤器功能重用为：

fun partition f xs = (filter f xs, filter (not o f) xs)

不过，这不是最好的方法，因为它对列表进行了两次评估，但如果列表很小，这是非常明显且非常易读的。

折叠式的

考虑这一点的另一种方法是折叠。您可能认为您正在将您的列表缩减为一个元组列表，并且随着您的进行，您根据谓词拆分您的项目。有点像这样：

fun parition f xs = 
    let
        fun split x (xs,ys) =
            if f x
            then (x::xs,ys)
            else (xs, x::ys)

        val (trueList, falseList) = List.foldl (fn (x,y) => split x y) 
                                                   ([],[]) xs
    in
        (List.rev trueList, List.rev falseList)
    end

分区

您也可以像 SML 的 List.parition 方法一样实现自己的折叠算法：

fun partition f xs = 
    let
        fun iter(xs, (trueList,falseList)) = 
            case xs of
                 [] => (List.rev trueList, List.rev falseList)
               | (x::xs') => if f x
                             then iter(xs', (x::trueList,falseList))
                             else iter(xs', (trueList,x::falseList))
    in
        iter(xs,([],[]))
    end

使用 SML 基法

最终，您可以避免所有这些并使用 SML 方法List.partition，其文档说：

隔断层

将 f 应用于 l 的每个元素 x，从左到右，并返回一个对 (pos, neg)，其中 pos 是那些 x 的列表，其中 fx 评估为真，而 neg 是那些 x 的列表，fx 评估为错误的。pos 和 neg 的元素保留了它们在 l 中所拥有的相同的相对顺序。

此方法与前面的示例一样实现。

于 2013-04-11T13:06:17.990 回答
2

因此，我将展示一个好的方法，以及一个更好的方法（IMO）。但是“更好的方法”仅供您将来学习时参考：

fun filter2 f [] = ([], [])
  | filter2 f (x::xs) = let

  fun ftuple f (x::xs) trueList falseList =  
    if (f x) 
      then ftuple f xs (x::trueList) falseList 
    else ftuple f xs trueList (x::falseList)

    | ftuple _ [] trueList falseList = (trueList, falseList)

in
  ftuple f (x::xs) [] []
end;

你的不起作用的原因是，当你调用时x::(filter2 f xs)，编译器天真地假设你正在构建一个列表，它不假设它是一个元组，它正在进入你的函数调用的范围。因此，当您认为结果类型是列表的元组时，编译器会获得隧道视野并认为结果类型是列表。在我看来，这是更好的版本，foldr如果你好奇，你应该查看这个函数，使用这种技术会更好，因为它更具可读性，更少冗长，更重要的是......更可预测和健壮：

fun filter2 f l = foldr (fn(x,xs) => if (f x) then (x::(#1(xs)), #2(xs)) else (#1(xs), x::(#2(xs)))) ([],[]) l;

第一个示例有效的原因是因为您正在存储默认的空列表，这些列表累积了符合条件或不符合条件的变量的副本。但是，您必须明确告诉 SML 编译器以确保类型规则一致。您必须绝对确保 SML 知道您的返回类型是列表元组。这个命令链中的任何错误，都会导致执行失败。因此，在使用 SML 时，请始终研究您的类型推断。至于第二个，你可以看到它是单行的，但我会让你自己研究那个，只需 googlefoldr和foldl.

于 2013-04-10T03:33:02.347 回答