从SML列表中删除元素 [英] Removing elements from list in sml

问题描述

我是SML的入门者.我发现以下代码似乎有效；但是，我不明白它是如何工作的.

I am a begginer in SML. I have found the following code which seems to work; however, I cannot understand how it works.

   fun delete(x,[]) = []
     | delete(x,y::l) = if x=y then delete(x,l) else y::delete(x,l);

   fun remove_dup [] = []
     | remove_dup (x::l) = x::remove_dup(delete(x,l));

此代码可删除任何形式的列表中的重复项.

This code removes duplicates in a list of any kind.

我尝试使用更基本的语法来复制它

I have tried to replicate it using more basic syntax as

 fun remove (vec: int list)=
       if null vec
       then []
       else remove(hd vec::1) = hd vec::remove(delete2(tl vec, 1)) 

但是我不能做更多的事情.

but I cannot do more.

有人可以帮助我吗?

推荐答案

...以下似乎有效的代码；但是，我不明白它是如何工作的.

... the following code which seems to work; however, I cannot understand how it works.

fun delete(x,[]) = []
  | delete(x,y::l) = if x=y then delete(x,l) else y::delete(x,l);

fun remove_dup [] = []
  | remove_dup (x::l) = x::remove_dup(delete(x,l));

我尝试使用更基本的语法来复制它...

I have tried to replicate it using more basic syntax ...

这似乎是明智的选择.

正如molbdnilo在评论中指出的那样， hd 和 tl 并不是更基本.

As molbdnilo points out in a comment, hd and tl are not more basic.

我可能会这样格式化 delete :

fun delete (x, []) = []
  | delete (x, y :: rest) =
      if x = y
      then delete (x, rest)       (* delete y *)
      else y :: delete (x, rest)  (* keep y *)

了解此功能的一种方法是解释其功能:

One way to understand this function is to explain what it does:

• 需要一个元组的(x，...)，其中 x 是单个元素，第二部分是此类元素的列表.这里使用模式匹配，因此列表的形状为 [] (空列表)或 y :: rest (具有至少一个元素的列表 y 和元素的其余列表 rest ).

• It takes one tuple of (x, ...) where x is a single element and the second part is a list of that kind of element. Pattern matching is used here, and so the list either takes shape of [] (the empty list) or y :: rest (the list with at least one element y and the remaining list of elements rest).

当列表为空(与模式 [] 匹配)时，结果也为空:只需返回即可从空列表中删除 x 值 [] .请注意，在 delete(x，[])= [] 中，两个 [] 的实际含义略有不同:第一个(在 = )是一个模式，第二个( = 的右侧)是一个值，一个实际的空列表.

When the list is empty (matches the pattern []), the result is also empty: Deleting x from the empty list is done by simply returning the value []. Notice that in delete (x, []) = [], the two []s actually mean something slightly different: The first (on the left-hand side of =) is a pattern, and the second (on the right-hand side of =) is a value, an actual empty list.

当列表不为空时，表示它由至少一个元素 y 和一个尾部 rest 组成.当至少有一个元素 y 时，表示至少有一个要删除的候选对象.如果 x = y ，则删除"将被删除.包括返回一个与输入列表非常相似的列表，除了 y 未在任何地方提及.因此，在 then 分支中，没有提及 y ，而是仅提及 delete(x，rest)，这意味着:

When the list is not empty, it means that it consists of at least one element, y, and a tail, rest. When there is at least one element, y, it means there is at least one candidate for deletion. If x = y, then the "deletion" consists of returning a list much like the input list, except with y not mentioned anywhere. So in the then branch, there is no mention of y, but instead only delete (x, rest) which means:

结果是从列表的其余部分删除 x 所得到的任何结果.

The result is whatever is gained from deleting x from the rest of the list.

这里还要注意，可以对模式 y :: ys 和值 y :: delete(x，其余)进行类似的区分.这里的 :: 是非空列表的值构造函数，它用于在持久保留 y 的位置创建新的列表值.但是该列表的末尾可能删除了 x 的副本.

Note also here that a similar distinction can be made about the pattern y :: ys and the value y :: delete (x, rest). Here :: is the value constructor for non-empty lists, and it is used to create a new list value where y persists. But the tail of that list may have copies of x deleted.

了解此功能的另一种方法是手动运行它.

Another way to understand this function is by running it by hand.

想象一下像 delete(3，[1,3,3,7])之类的呼叫；我将对每行进行一次重写，这对应于计算的减少:

Imagine a call like delete (3, [1,3,3,7]); I will make one rewrite per line, which corresponds to a reduction of the computation:

(*  1 *)   delete (3, [1,3,3,7])
(*  2 *) ~> if 3 = 1 then delete (3, [3,3,7]) else 1 :: delete (3, [3,3,7])
(*  3 *) ~> 1 :: delete (3, [3,3,7])
(*  4 *) ~> 1 :: (if 3 = 3 then delete (3, [3,7]) else 3 :: delete (3, [3,7]))
(*  5 *) ~> 1 :: delete (3, [3,7])
(*  6 *) ~> 1 :: (if 3 = 3 then delete (3, [7]) else 3 :: delete (3, [7]))
(*  7 *) ~> 1 :: delete (3, [7])
(*  8 *) ~> 1 :: (if 3 = 7 then delete (3, []) else 7 :: delete (3, []))
(*  9 *) ~> 1 :: 7 :: delete (3, [])
(* 10 *) ~> 1 :: 7 :: []

1. 这是初始函数调用.

1. This is the initial function call.

因为输入列表为非空，所以我们跳过了第一个模式匹配，并将值(3，[1,3,3,7])拟合到模式(x，y ::休息):您可以通过设置 x = 3 ， y = 1 和 rest = [3,3,7] .之后，我们用完整的函数体替换 delete(3，[1,3,3,7])，用替换的变量替换 if ... .

Because the input list is non-empty, we skip the first pattern match and we fit the value (3, [1,3,3,7]) onto the pattern (x, y :: rest): You can do that easily by setting x = 3, y = 1 and rest = [3,3,7]. After we do that, we replace delete (3, [1,3,3,7]) with the full function body, if ... with the variables replaced.

因为 3 = 1 为假，所以选择了 else 分支，因此整个表达式将替换为 else中的子部分分支， 1 ::删除(3，[3,3,7]).

Since 3 = 1 is false, the else branch is picked, so the entire expression is replaced with the sub-part in the else branch, 1 :: delete (3, [3,3,7]).

一些有趣的事情在这里发生:

Some interesting things happen here:

1. 由于(* 3 *)包含 1 ::: delete(3，[3,3,7])，您将获得两个半计算结果:在一方面，您想构造列表 1 :: ... ，另一方面，您不知道尾部 delete(3，[3,3,7])，因为尚未计算出来.
2. 因此，在计算 1 :: ... 之前，必须计算 delete(3，[3,3,7]).这导致仅替换尾部，因此 1::(如果3 = 3 ...).除了嵌套表达式之外，减少量几乎相同，除了...

1. Since (* 3 *) contains 1 :: delete (3, [3,3,7]), you have two half-computed results: On the one hand you want to construct the list 1 :: ..., and on the other hand, you don't know the tail delete (3, [3,3,7]) yet, since it hasn't been computed.
2. So before you can compute 1 :: ..., you have to compute delete (3, [3,3,7]). This causes for a substitution of only the tail, so 1 :: (if 3 = 3 ...). Besides nesting the expressions, the reduction is pretty much the same, except...

因为 3 = 3 为真，所以选择了 then 分支，这只会导致值 delete(3，[3，7])，其中没有 y :: ... 部分，因为 y = 3 ，并且我们要删除 3 ，做 3 :: ... 显然是错误的事情.

Since 3 = 3 is true, the then branch is picked, and this results in only the value delete (3, [3,7]) with no y :: ... part, since y = 3 and we're deleting 3s, doing 3 :: ... would clearly be a wrong thing to do.

以这种方式重复(无论是否包含 y )，直到(* 9 *)，其中 1 :: 7 ::删除(3，[])要求从空白列表中删除 3 .这是第一次触发 delete(x，[])= [] 的第一种情况，递归停止.

Things repeat this way (either including y or not) until (* 9 *) where 1 :: 7 :: delete (3, []) is asking for 3 to be deleted from the empty list. For the first time, this triggers the first case of delete (x, []) = [] and the recursion stops.

您可以使用 remove_dup 做类似的事情；就是手动运行.

You can do a similar thing with remove_dup; running by hand, that is.

您可能会发现它不是很简单，因为它包含两个递归函数，一个调用另一个函数，然后直接提供其输入.无论您如何扭转和旋转此功能，都会有些困难.

And you might find out that it isn't very trivial because it contains two recursive functions, one calling the other one and feeding its input directly. No matter how you twist and turn this function, it is going to be a little difficult.

有一些方法可以使它看起来更简单:

There are some ways to make it look a little easier:

fun remove_dup [] = []
  | remove_dup (x :: rest) =
      let val rest_without_x = delete (x, rest)
      in x :: remove_dup(rest_without_x)
      end

，您也许至少可以发现这一点

and you may be able to at least spot that

1. remove_dup [] = [] :从空列表中删除重复项很容易.
2. 当至少有一个元素 x 时，通过执行 delete(x，休息).我将此列表称为 rest_without_x ，然后输入到 remove_dup .
3. 由于我们仅删除了 x 的 duplicates ，因此我们希望将其包含一次，而我们选择的一次出现的 x 恰好是我们遇到的第一个.

1. remove_dup [] = []: Removing duplicates from the empty list is easy.
2. When there is at least one element, x, remove all occurrences of x from rest by doing delete (x, rest). This list, which I called rest_without_x, is then fed to remove_dup.
3. Since we only remove duplicates of x, we want to include it once, and the one occurrence of x we pick is incidentally the first one we encounter.

如果要像上面的示例一样手动运行此代码，则可能要运行原始的紧凑代码，因为该函数主体仅跨越一行.它可能看起来像:

If you want to run this by hand like in the example above, you probably want to run the original, compact one, though, since the function body only spans a single line. It could look like:

   remove_dup [1,1,1,2,2,3,1,2,3]
~> 1 :: remove_dup(delete(1, [1,1,2,2,3,1,2,3]))
~> 1 :: remove_dup([2,2,3,2,3])
~> 1 :: 2 :: remove_dup(delete(2, [2,3,2,3]))
~> ...

请注意，在解析 remove_dup(...)之前，我先解析了内部表达式 delete(1，...)，因为其参数尚未解析.(这是严格的评估语义的结果；某些函数式编程语言使您可以在未完全评估其参数的情况下调用一个函数！)

Notice that I resolve the inner expression delete(1, ...) before I can resolve remove_dup(...) since its argument was not yet resolved. (This is a consequence of strict evaluation semantics; some functional programming languages let you call a function without having fully evaluated its arguments!)

尝试自己完成其余的事情.

Try and complete the rest yourself.

这篇关于从SML列表中删除元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！