0

背景：SML 初级

我的任务要求我使用 ListPair.foldr 并且只有这个函数来实现 zipWith 函数。

ListPair.foldr : ('a * 'b * 'c -> 'c) -> 'c -> 'a list * 'b list -> 'c
zipWith : ('a * 'b -> 'c) -> 'a list -> 'b list -> 'c list

ListPair.foldr 返回单个 'c 元素，而 zipWith 返回一个 'c 列表，所以我的方法自然会反复使用 ListPair.foldr 来溢出单个 'c 元素，然后我将其放入我的 'c 列表中。ListPair.foldr 采用一对列表并根据提供的函数将它们相互折叠，因此获得所需效果的唯一方法是一次从每个列表中获取一个元素，将其作为 ListPair.foldr一对列表，获取结果，并将其连接到下一轮。我还必须将函数从 ('a*'b->'c) 转换为 ('a*'b*'c->'c)。像这样：

fun zipWith f [] l2 = []
| zipWith f l1 l2 = 
let val f2 = fn (a,b,c)=> f(a,b)+c   (* converting the function *)
    val xh = [hd(l1)]      (*first element of 'a list, as a list itself *)
    val yh = [hd(l2)]      (*first element of 'b list, as a list itself *)
    val xt = tl(l1)        (*taking the tail of 'a list*)
    val yt = tl(l2)        (*taking the tail of 'b list*)
in
    ListPair.foldr f2 0 (xh, yh)::    (*perform the operation with the two heads*)
    zipWith f xt yt                   (*recursively call zipWith with the remainder*)
end;

这行得通。

- zipWith (fn (x,y)=>x+y) [1,2,3] [10,20,30];
val it = [11,22,33] : int list

但现在棘手的部分是：我不应该递归地执行此操作，也就是说，我不能在我的 zipWith 函数中调用 zipWith 。这甚至可能吗？根据我的阅读，Haskell 中的实际 zi​​pWith 函数是递归定义的；我如何以非递归方式执行此操作？

我无法想象教授会敦促我们以面向对象的方式使用 while 循环之类的方法来执行此操作（无论如何我都尝试过，我的水平还不够）。

我是在完全错误的方向吗？我应该如何处理这个问题？

-----------------已回答----------------

我实际上首先尝试了pad的解决方案：

fun zipWith f l1 l2 = 
let val f2 = fn (a,b,c)=> f(a,b)::c
in
    ListPair.foldr f2 0 l1 l2
end;

但它不起作用，因为我将它附加到 0 而不是 []。类型不正确，我无法弄清楚！

谢谢！

4

1 回答 1

4

您的方法是正确的，但不必要地复杂。函数zipWith是递归的，但您可以非递归地定义它，因为它ListPair.foldr已经具有递归性质。

为了更接近zipWith，您需要ListPair.foldr具有以下签名的专用版本

ListPair.foldr : 
   ('a * 'b * 'c list -> 'c list) -> 'c list -> 'a list * 'b list -> 'c list

这意味着您将一个空列表作为累加器传递，并在此过程中建立更大的列表。中zipWith f xs ys，f有'a * 'b -> 'c签名，所以很容易适应：

fun zipWith f xs ys =
    ListPair.foldr (fn (a, b, cs) => f(a, b)::cs) [] (xs, ys)
于 2013-01-27T20:06:49.547 回答