sml - 带折叠的多种输入类型

Question

我试图弄清楚如何对不同类型的输入实现折叠函数。作为示例，我将使用列表的 count 函数(不过，我有多个函数要为此实现)。 假设一个 int 列表输入(但这应该适用于任何类型的列表)，我的计数函数将是

val count = foldr (fn(x:int,y)=>y+1) 0 ;
val count = fn : int list -> int

但是，我正在尝试创建一个类型为

的计数函数

val count = fn : int list * bool list -> int

其中 int 列表是集合的全域，而 bool 确定全域的哪些值在集合中。即 (1,3,5,6),(true,false,false,true) 产生最终的一组 (1,6)，其计数为 2。我首先想到尝试的是某种形式的

val count= foldr (fn(x:(int*bool),y)=>if #2x then y+1 else y ) 0 ;

但这会导致返回类型为

val count = fn : (int * bool) list -> int

这不完全是我所需要的。从逻辑上讲，它们是相似的，但我希望将这两种类型分别分组在一个列表中。

Answer 1

1. 您可以使用 ListPair.foldl :

   fun count (xs, bs) = ListPair.foldl (fn (x, b, acc) => ...) ... (xs, bs)
   

   其中第一个 ... 是 x、b 和 acc 的某种组合，第二个 ... 是初始值。

   这假设 xs 和 bs 的长度相等，如果它们不相等，则丢弃较长列表中的剩余元素。 (您可能应该尝试证明在 xs 或 bs 较长的情况下这是否给出了正确答案。)

2. 否则，您需要通过创建一个函数将您的int list × bool list组合(又名zip)为(int × bool)列表两个列表，并将此功能与您已经执行的折叠结合使用。

   fun combine (x::xs, y::ys) = ...
     | combine (..., ...) = ...
   

   此函数相当于ListPair.zip。