使用ListPair.foldr在SML中实现zipWith [英] Using ListPair.foldr to implement zipWith in SML

问题描述

背景：SML的初学者级别

我的任务需要我使用ListPair.foldr，并且只有此函数才能实现zipWith函数。

  ListPair.foldr：（'a *'b *'c  - >'c） - > 'c  - > 'list *'b list  - > 'c 
 zipWith：（'a *'b  - >'c） - > '列表 - > 'b列表 - > '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 = [] 
 | zip with f l1 l2 = 
 let val f2 = fn（a，b，c）=> f（a，b）+ c（*转换函数*）
 val xh = [hd（l1）]（*列表的第一个元素，作为列表本身*）
 val yh = [* b列表的第一个元素，作为列表本身*）
 val xt = tl（l1）（*以列表*的尾部）
 val yt = 
 ListPair.foldr f2 0（xh，yh）::（*用两个头执行操作*）
 zipWith ftxt（*递归调用zipWith和余数*）
 end; 
  

这是有效的。

 （fn（x，y）=> x + y）[1,2,3] [10,20,30]; 
 val it = [11,22,33]：int list 
  

但现在棘手部分：我不应该这样做递归，也就是说，我不能在我的zipWith函数中调用zipWith。
这甚至可能吗？从我读到的，Haskell中的实际zipWith函数是递归定义的;我怎么做非递归呢？

我无法想象教授催促我们用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而不是[]。

谢谢！

解决方案

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

为了更接近 zipWith ，您需要一个特殊版本的 ListPair.foldr 以下签名

  ListPair.foldr：
（'a *'b *'c list  - >'c list） - > 'c list  - > '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）
  

Background: Beginner level at SML

My assignment requires me to use ListPair.foldr and only this function to implement the zipWith function.

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

ListPair.foldr returns a single 'c element, while zipWith returns a 'c list, so naturally my approach would use ListPair.foldr repeatedly to spill out individual 'c elements which I then put in my 'c list. ListPair.foldr takes a pair of lists and folds them over each other according to the supplied function, so the only way to get the desired effect would be to take one element from each list at a time, feed it to ListPair.foldr as a pair of lists, take the result, and concatenate it to the next round. I'd also have to convert the function from ('a*'b->'c) to ('a*'b*'c->'c). Like so:

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;

This works.

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

But now the tricky part: I'm not supposed to do this recursively, that is, I can't call zipWith within my zipWith function. Is this even possible? From what I read, the actual zipWith function in Haskell is defined recursively; how do I do this non-recursively?

I can't imagine the professor urging us to do this in an object-oriented way with while loops and such (I tried anyway, my level is not adequate for even that).

Am I in the completely wrong direction? How should I approach this question?

-----------------Answered----------------

I actually tried pad's solution at first:

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

But it didn't work because I was appending it to 0 instead of []. The types didn't work out and I couldn't figure it out!

Thank you!

解决方案

Your approach is correct but unnecessarily complex. Function zipWith is recursive but you can define it non-recursively because ListPair.foldr already has recursive nature.

To get closer to zipWith, you need a specialized version of ListPair.foldr with the following signature

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

It means you pass an empty list as an accumulator and build up bigger lists along the way. In zipWith f xs ys, f has 'a * 'b -> 'c signature, so it is very easy to adapt:

fun zipWith f xs ys =
    ListPair.foldr (fn (a, b, cs) => f(a, b)::cs) [] (xs, ys)

这篇关于使用ListPair.foldr在SML中实现zipWith的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！