SML：使用每个元组的第二个元素从元组列表创建一个列表

Question

你好，我是 SML 的新手，我一直在尝试编写一个函数，该函数将一个列表（在我的例子中是普鲁士列表）作为参数，它有两个整数和一个字符串的元组，我的函数有创建一个列表，其中包含列表中出现的所有年份而不重复（列表中每个元组的第二个元素）。我必须创建两个函数（append_if_new 需要一年的列表并将其添加到列表中，它有效）并且年份必须对列表中的所有元组执行它，我尝试使用 foldl 但是我发现 tycon 不匹配。

钯。为此，我必须使用函数 map、filter 或 fold，并且我可以将 append_if_new 功能移至年函数。我认为错误出在 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

create a list with all the years that appear in the list without repetitions

(2nd element of each tuple of the list)

您可以使用 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 and 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)]

由于条件始终为假 - 你永远不会在空列表中找到任何东西 - [] @ 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 的函数需要两个东西 - "the current element" 和 "the results so far" - 并将它们组合起来产生 "next"结果。
像这样：

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

SML：使用每个元组的第二个元素从元组列表创建一个列表

SML: Create a list from a list of tuples with the second element of each tuple

sml