SML:从元组列表中创建一个列表，其中包含每个元组的第二个元素

Question

你好，我是SML的新手，我一直在尝试编写一个函数，该函数将一个列表(在我的情况下是列表prussia(作为参数，该列表具有两个int和一个字符串的元组，我的函数必须创建一个列表，其中包含列表中出现的所有年份，而不重复(列表中每个元组的第二个元素(。我必须创建两个函数(append_if_new需要列表的一年时间并将其添加到列表中，它有效(，而year必须为列表中的所有元组执行此操作，我尝试使用foldl，但我得到了tycon不匹配。

Pd。要做到这一点，我必须使用函数map、filter或fold，并且我可以将appendif_new函数移到year函数中。我认为错误是在fold调用中，我作为参数传递的函数不是我应该传递的函数类型，但我不确定问题出在哪里。感谢

val prussia =
[(0,1875,"G"),(2,1876,"G"),(2,1877,"G"),(1,1878,"G"),(0,1879,"G"),
(0,1880,"G"),(1,1881,"G"),(1,1882,"G"),(0,1883,"G"),(3,1884,"G"),
(0,1885,"G"),(2,1886,"G"),...] : (int * int * string) list
fun append_if_new (lista:(int*int*string)list): int list =
let 
val lista2 = []
val x = hd lista
val z = #2x
in
if (List.exists (fn y => y = z) lista2) 
then lista2
else lista2@[z]
end
fun years (lista:(int*int*string)list): int list =
List.foldl append_if_new 0 lista

Answer 1

创建一个列表，其中包含列表中出现的所有年份，不重复

(列表中每个元组的第二个元素(

您可以使用map创建一个包含重复的列表，然后过滤重复：

fun year_of (_, year, _) = year
fun member (y, xs) = List.exists (fn x => y = x) xs
fun nub [] = []
| nub (x::xs) = if member (x, xs)
then nub xs
else x :: nub xs
fun years records = nub (map year_of records)

这里nub具有O(n²(的渐近运行时间复杂度，这是不好的并且是不必要的。你也可以直接折叠列表，这样你就永远不会插入重复的内容：

fun member (y, xs) = List.exists (fn x => y = x) xs
fun years records =
let
fun insert ((_, year, _), years) =
if member (year, years)
then years
else year :: years
in
foldr insert [] records
end

但渐近运行时间是相同的，读起来稍微模糊一些。如果你想以高效的方式过滤重复项，你必须使用更高效的数据结构来管理重复项，比如基于树的集合或类似的结构。在Haskell中，这是nub和nubOrd之间的区别。

Answer 2

有两个问题：

• 折叠的初始值是错误的-由于结果应该是列表，因此初始值也必须是列表
• append_if_new函数的参数太少，错误太多

如果替换let bound定义，append_if_new将变为

fun append_if_new (lista:(int*int*string)list): int list =
if List.exists (fn y => y = #2 (hd lista)) [] 
then []
else []@[#2 (hd lista)]

由于条件总是false-你永远不会在空列表中找到任何东西-并且[] @ xs等价于[xs]，我们可以将其进一步简化为

fun append_if_new (lista:(int*int*string)list): int list =
[#2 (hd lista)]

这显然是不正确的-此函数将始终生成一个列表，该列表的唯一元素是第一个条目的年份。

示例：

- append_if_new prussia;
val it = [1875] : int list

传递给foldl的函数接受两个东西——"当前元素"one_answers"迄今为止的结果"——并将它们组合起来产生"下一个"结果
像这样：

fun add_if_new ((_,y,_), so_far) = if List.exists (fn z => y = z) so_far 
then so_far 
else y :: so_far;

测试：

- add_if_new ((1,2,3), []);
val it = [2] : int list
- add_if_new ((1,2,3), [3]);
val it = [2,3] : int list
- add_if_new ((1,2,3), [2]);
val it = [2] : int list

和：

fun years (lista: (int*int*string) list): int list =
List.foldl add_if_new [] lista

测试：

- years [(12,0, "G"), (12,1,"G"), (12,0,"G")];
val it = [1,0] : int list