sml - 将值过滤到两个列表中

Question

所以我是 sml 的新手，正在尝试了解它的来龙去脉。最近我尝试创建一个过滤器，它接受两个参数:一个函数(返回一个 bool 值)和一个针对该函数运行的值列表。过滤器的作用是返回值列表，这些值对函数返回 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 *)

Answer 1

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

重复使用过滤器

例如，我们可以根据您的元组将由两个元素组成这一事实来使用归纳方法，第一个是满足谓词的元素列表，第二个是不满足谓词的元素列表。因此，您可以将您的过滤器函数重用为:

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其文件说:

partition f l

applies f to each element x of l, from left to right, and returns a pair (pos, neg) where pos is the list of those x for which f x evaluated to true, and neg is the list of those for which f x evaluated to false. The elements of pos and neg retain the same relative order they possessed in l.

这个方法和前面的例子一样实现。