如何将记录三元组附加到 sml 中的列表

Question

fun same_string(s1 : string, s2 : string) =
  s1 = s2
         
fun all_except_option(str, []) = NONE
  | all_except_option(str, x::xs) =
    case same_string(x, str) of
        true  => SOME xs
      | false => 
          let 
            fun build_list(x::xs, str) =
              case all_except_option(str, xs) of
                 NONE => NONE
               | SOME y => SOME(x::y)
          in
            build_list(x::xs, str)
          end

fun get_substitutions2(xss, str) =
  let 
    fun sub([], acc) = acc
      | sub(ys::yss, acc) =
        case all_except_option(str, ys) of
            NONE   => sub(yss, acc)
          | SOME y => sub(yss, y@acc)
  in
    sub(xss, [])
  end

fun similar_names(xss, []) = Empty
  | similar_names(xss, r : {first:string, middle:string, last:string}) = 
    let 
      fun helper (x::xs, acc) =
        case x of
            [] => acc
          | {first=a, middle=b, last=c} => helper(xs, {x, b, c} @ acc)
    in
      case get_substitutions2(xss,a) of
          NONE   => NONE
        | SOME y => helper(y, [])     
    end

- foo.sml:32.45 Error: syntax error: inserting  VAL
- foo.sml:33.5-33.7 Error: syntax error: replacing  IN with  EQUALOP
- foo.sml:38.5 Error: syntax error found at END

我在使用最后一个功能时遇到问题

similar_names

。我不知道如何将记录三元组追加或删除到列表中。该函数应该接受一个字符串列表列表和一个记录三元组。它使用 get_substitutions2 遍历以记录的名字作为字符串的字符串列表 list，使用 all_ except_option 在字符串列表 list 中查找与名字匹配的字符串。

similar_names

应输出一个记录三重列表，如下所示：

- val similar_names = fn : string list list * {first:string, last:string, middle:string}
-> {first:string, last:string, middle:string} list

示例输入（来自OP的评论）：

similar_names(
  [["Fred", "Fredrick"], 
   ["Elizabeth", "Betty"],
   ["Freddie", "Fred", "F"]], 
  {first="Fred", middle="W", last="Smith"}
)

预期输出：

[{first="Fred", last="Smith", middle="W"}, 
 {first="Fredrick", last="Smith", middle="W"}, 
 {first="Freddie", last="Smith", middle="W"}, 
 {first="F", last="Smith", middle="W"}]

Answer 1

在 SML 中有两种方法可以将内容添加到列表中。我们可以使用

@

连接两个列表，也可以使用

::

将元素添加到列表的开头。

关于运行时复杂性的旁白。前者的运行时复杂性与第一个列表的长度成线性关系。第二个总是以恒定时间运行。因此，通常不鼓励在递归调用的函数中使用

@

，因为它产生的函数随数据大小的扩展非常差。

您的代码通常显示出过于复杂的思想。编写计算机程序的关键之一是分解问题并找到其基本组件，使它们工作，然后将其重新组合在一起。

如果我们看看您需要完成什么，您会得到一个列表列表，它本质上形成了一个等价字典。然后，您将获得一个包含名字、中间名和姓氏的姓名“三元组”列表。我们需要将每个名称映射到具有相同名字的名称列表。

第一个任务是针对给定名称，找到所有等效项。

fun listEquivs(equivDict, name : string) =
  List.concat (List.filter (fn names => List.exists (fn n => n = name) names) equivDict);

我们根据是否包含我们要查找的名称来过滤等效名称列表的列表。然后，我们将该列表“扁平化”为一个列表，而不是列表的列表。

检查您的数据中的

"Fred"

可以得出：

["Fred", "Fredrick", "Freddie", "Fred", "F"]

几乎。但是我们出现了两次

"Fred"

，您清楚地看到并试图解决。我们不采用你的方法，而是分解问题。您基本上只需要一个unique元素的列表。这实际上会更好地解决问题，因为它将处理any等效名称的重复。

作为第一步，我们可以获得等效名称的排序列表。

List.sort String.compare (listEquivs(similarNames, "Fred"))

退货：

["F", "Fred", "Fred", "Freddie", "Fredrick"]

现在，找到一个只有唯一名称的列表。幸运的是，在排序列表中查找唯一值非常简单。

fun unique([]) = []
  | unique([x]) = [x]
  | unique(a::(tl as b::_)) = 
    if a = b then unique(tl)
    else a::unique(tl);

现在：

unique(List.sort String.compare (listEquivs(similarNames, "Fred")));

给我们：

["F", "Fred", "Freddie", "Fredrick"]

完成此操作后，我们现在可以编写一个简单的函数：

fun equivalentNames(names, equivDict) = 
  List.concat (List.map 
    (fn {first=f, middle=m, last=l} =>
       let 
         val equivs = unique(List.sort String.compare (listEquivs(similarNames, f)))
       in
         List.map (fn e => {first=e, middle=m, last=l}) equivs
       end)
    names);

现在：

equivalentNames([{first="Fred", middle="W", last="Smith"}], similarNames);

产量：

[{first = "F",        last = "Smith", middle = "W"}, 
 {first = "Fred",     last = "Smith", middle = "W"}, 
 {first = "Freddie",  last = "Smith", middle = "W"}, 
 {first = "Fredrick", last = "Smith", middle = "W"}]

使用的较小功能：

• List.filter

• List.exists

• List.concat

• List.map

• List.sort

• String.compare

了解它们是如何工作的，您就可以使用它们更轻松地编写程序。

作为一个例子，地图的简单实现。

fun map _ [] = []
  | map f (x::xs) = f x :: map f xs

将任何函数映射到空列表上都会给我们一个空列表。这构成了递归的基本情况。否则，我们将应用函数

f

的结果附加到通过将

f

映射到列表尾部而形成的列表的前面。

例如

map (fn x => x + 1) [1, 2, 3, 4]
(1 + 1) :: map (fn x => x + 1) [2, 3, 4]
(1 + 1) :: (2 + 1) :: map (fn x => x + 1) [3, 4]
(1 + 1) :: (2 + 1) :: (3 + 1) :: map (fn x => x + 1) [4]
(1 + 1) :: (2 + 1) :: (3 + 1) :: (4 + 1) :: map (fn x => x + 1) []
(1 + 1) :: (2 + 1) :: (3 + 1) :: (4 + 1) :: []
[2, 3, 4, 5]