f#从自己的用户定义列表中删除 [英] f# remove from own user defined list

问题描述

我想创建一个函数，该函数删除所有出现的整数n并返回列表.我知道我想怎么做，但不知道删除它的命令.

I want to create a function that removes any occurrence of a integer n and returns the list. I know how I want to do it but do not know the command to delete it.

这是数据类型

type alist = 
    A 
  | L of int * Alist

以下是数据类型的外观:

Here's how the data type looks:

let l = L(2, L(1, L(2, L(7, L(3, L(2, A))))))

remove 2 l;;

应该返回

l = L(1, L(7, L(3, A)))

这是我到目前为止所拥有的:

Here is what I have so far:

let rec remove n l = 
    match (n, l) with
    | (n, A) -> l
    | (n, L(head,tail)) when (n = head) -> 

我不知道如何摆脱列表或元素.

I don't know how the how to get rid of a list or element.

推荐答案

您不应该考虑删除"列表；您应该考虑建立一个 new 列表，而 without 要删除的元素.我将在一分钟内告诉您如何执行此操作，但首先我想提个建议.在match表达式中，您正在模式中重新使用名称n.这是一个典型的初学者的错误，因为它最终会使您感到困惑.一旦您非常了解F#，这就是一种有效的技术，但是由于您似乎是个初学者，因此我强烈建议您不这样做.取而代之的是，在您的模式中使用与所匹配的事物的名称​​不同的名称，因为这样可以帮助您学习一些东西.让我们在模式中使用x作为int的名称来重写您的匹配表达式:

You shouldn't be thinking in terms of "deleting" the list; you should instead think in terms of building a new list, without the element you want removed. I'll show you how to do that in a minute, but first I want to make a suggestion. In your match expression, you are re-using the name n in your patterns. That's a classic beginner's mistake, because it ends up confusing you. Once you know F# pretty well, that's a valid technique, but since you appear to be a beginner, I strongly suggest not doing that. Instead, use a name in your patterns that is different from the name of the thing you're matching against, because that will help teach you something. Let's rewrite your match expression with x as the name of the int in your patterns:

let rec remove n l = 
    match (n, l) with
    | (x, A) -> l
    | (x, L(head,tail)) when (x = head) -> 

这两个模式中的每一个都在做的工作是，如果其余模式匹配，则分配名称x来表示n的值.现在我们可以更清楚地看到第一个模式根本不使用的值，因此在这种情况下最好用_表示(_是通配符"模式，表示我不在乎此位置的值).因此，您的match表达式将变为:

What each of these two patterns is doing is assigning the name x to represent the value of n if the rest of the pattern matches. Now we can more clearly see that the first pattern doesn't use the value of x at all, so it would be better to represent it by _ in that case (_ is the "wildcard" pattern, which means "I don't care about the value in this position). Thus, your match expression would become:

let rec remove n l = 
    match (n, l) with
    | (_, A) -> l
    | (x, L(head,tail)) when (x = head) -> // ... Still need to write this

现在让我们考虑一下在第二个比赛情况下我们想要做什么.在这里，我们有一个节点，恰好是我们要从列表中删除的那种节点.那么，我们如何建立一个没有节点的列表 呢?好吧，碰巧的是，我们已经有了这样的列表 ...，并且在第二种匹配情况下，我们为其分配了名称tail.因此，乍一看，我们似乎可以做到这一点:

Now let's think about what we want to do in that second match case. Here we have a node that is precisely the kind of node we want to remove from the list. So how do we go about building a list without that node in it? Well, as it happens, we already have such a list... and we've assigned it the name tail in that second match case. So at first, it might look like we could just do this:

let rec remove n l = 
    match (n, l) with
    | (_, A) -> l
    | (x, L(head,tail)) when (x = head) -> tail

这将返回一个列表，其中"head"节点被切掉.可是等等！如果尾巴本身包含一个或多个带有我们要删除的值的节点该怎么办?我们真正想从这种匹配情况返回的是tail，它通过一个函数删除，该函数将删除所有与某个值匹配的节点.但是...等等，我们现在不是在编写类似 这样的函数吗?如果我们只需在尾部调用remove并为我们完成其余工作，该怎么办?那不是很好吗?

This will return a list with the "head" node chopped off. But wait! What if the tail itself contained one or more nodes with the value we want removed? What we'd really like to return from this match case is tail, passed through a function that would remove all the nodes that match a certain value. But... wait a minute... aren't we writing a function like that right now? What if we could just call remove on the tail and have it do the rest of the work for us; wouldn't that be nice?

好吧，事实证明我们可以！要从tail列表中删除其余不需要的值，您要做的就是在其上调用remove！像这样:

Well, it turns out that we can! All you have to do to remove the rest of the unwanted values from the tail list is to call remove on it! Like so:

let rec remove n l = 
    match (n, l) with
    | (_, A) -> l
    | (x, L(head,tail)) when (x = head) -> remove n tail

但是我们还没有完成，因为您的match语句还有另一种可能性.如果您使用的是良好的F#开发环境(我建议将 Visual Studio代码与

But we're not quite done yet, because there's one more possibility in your match statement. If you are using a good F# development environment (I recommend Visual Studio Code with the Ionide plugin), you should see a green wavy underline under the match keyword, and if you hover over it you should see a warning about an incomplete match expression. That's because there's one case we haven't accounted for: the case where l is a node that isn't A, but whose head value isn't equal to n. In other words, this match case:

    | (x, L(head,tail)) when (x <> head) -> // What do we do here?

好吧，对于初学者来说，让我们简化一下这场比赛.如果将其放入完全匹配表达式中，应该看到when保护实际上是不必要的.区分大小写的顺序是从上到下，依次是 .这意味着，如果我们转到第三个匹配项，我们已经知道 x一定不能等于head；否则，将选择第二个匹配项！您可能还无法了解为什么，所以让我们将匹配用例放入我们的匹配表达式中，然后进行查看:

Well, for starters, let's simplify this match case a bit. If we put it into the complete match expression, we should see that the when guard is actually unnecessary. Match cases are checked from top to bottom, in order. Which means that if we get to the third match case, we already know that x must not be equal to head; otherwise the second match case would have been chosen! You may not be able to see why just yet, so let's put that match case into our match expression and take a look at it:

let rec remove n l = 
    match (n, l) with
    | (_, A) -> l
    | (x, L(head,tail)) when (x = head) -> remove n tail
    | (x, L(head,tail)) when (x <> head) -> // What do we do here?

现在更加明显的是，这与之前的比赛情况完全相同，但使用了相反的when卫队.这意味着如果我们遇到第三个匹配项，则when表达式必须为true －因为如果它为false，则意味着x等于head，依此类推.我们本来应该是 second 匹配项，而不是第三个.

Now it's more obvious that this exactly like the previous match case, but with the opposite when guard. Which means that if we ever reach the third match case, the when expression must be true -- because if it was false, then that means that x is equal to head and so we would have gone down the second match case, not the third.

因此，我们实际上可以从第三个比赛情况中删除后卫when，现在看起来像这样:

Therefore, we can actually remove the when guard from the third match case, which will now look like this:

let rec remove n l = 
    match (n, l) with
    | (_, A) -> l
    | (x, L(head,tail)) when (x = head) -> remove n tail
    | (x, L(head,tail)) -> // What do we do here?

这里可以做更多的简化，但是现在该看看我们要返回什么结果了.在这里，我们不想跳过列表的第一个节点，但是我们仍然想从尾部删除n.实际上，作为此函数的结果，我们想要的是一个列表节点，该列表节点与我们当前的列表节点包含相同的head，但是其尾部已删除了n. (如果您不明白最后一句话，请花一分钟时间，然后尝试将其记在脑海中.)那么，我们该如何做呢?好吧，最简单的方法如下:

There's more simplification that can be done here, but it's time to look at what result we want to return. Here, we do NOT want to skip the first node of the list, but we'd still like to remove n from the tail. In fact, what we want as a result of this function is a list node containing the same head as our current list node, but with a tail that has had n removed from it. (If you don't understand that last sentence, take a minute and try to picture this in your head.) So how do we do this? Well, the simplest way is as follows:

let newTail = remove n tail
L(head, newTail)

可以简化为:

L(head, remove n tail)

所以match函数现在看起来像这样:

So the match function looks like this now:

let rec remove n l = 
    match (n, l) with
    | (_, A) -> l
    | (x, L(head,tail)) when (x = head) -> remove n tail
    | (x, L(head,tail)) -> L(head, remove n tail)

信不信由你，我们完成了！好吧，几乎:我们现在有一个工作功能，但是实际上比需要的要复杂. Antoine deSaint-Exupéry以写小王子而闻名，但他还是一位飞行员，在设计方面有著名的名言:

Believe it or not, we're done! Well, almost: we have a working function now, but it's actually more complicated than it needs to be. Antoine de Saint-Exupéry is most well-known for writing The Little Prince, but he was also an aviator, who has a famous quote about design:

无法完美地完成所有任务，却无法重新执行.

Il semble que la perfection soit atteinte non quand il n'y a plus rien à ajouter, mais quand il n'y a plus rien à retrancher.

用英语，那就是

似乎没有什么要添加的东西了，而是有什么要删除的东西了.

It seems that perfection is attained not when there is nothing more to add, but when there is nothing more to remove.

那么我们可以从该功能中删除以将其缩减为绝对必要的内容吗?好吧，让我们再次来看最后一个匹配的案例:

So what can we remove from this function to pare it down to the absolute essentials? Well, let's start by looking at that last match case again:

    | (x, L(head,tail)) -> L(head, remove n tail)

在这种情况下，我们似乎没有在任何地方使用x的值，因此在这种情况下，我们实际上不需要为int分配名称.我们只能在此处使用通配符_.完成后，我们的函数将如下所示:

It looks like we don't use the value of x anywhere in this match case, so we don't actually need to assign a name to the int in this match case. We can just use the wildcard _ here. Once we do, our function looks like:

let rec remove n l = 
    match (n, l) with
    | (_, A) -> l
    | (x, L(head,tail)) when (x = head) -> remove n tail
    | (_, L(head,tail)) -> L(head, remove n tail)

在这一点上，您可能认为我们已经完成了，因为在第二个匹配情况下，我们 do 使用了x的值，因此我们无法摆脱它.或者...可以吗?让我们更仔细地看看第二个比赛案例:

And at this point, you might think that we're really done, because we do use the value of x in the second match case, so we can't get rid of it. Or... can we? Let's look at the second match case more closely:

    | (x, L(head,tail)) when (x = head) -> remove n tail

现在.此处x的值与n的值相同，因为这种区分大小写实际上是通过x将n的值分配给x的名称处于第一个元组位置.正确的?因此，在when防护中，我们可以在x = head检查中实际上将x换为n.这是合法的:在区分大小写的情况下进行的检查不必仅包括出现在匹配模式中的名称.它们可以是您的函数可以访问的任意名称.因此，将x换出为n并使匹配情况看起来像这样是完全有效的:

Now. The value of x here is the same as the value of n, because this match case is actually assigning the value of n to the name x by virtue of x being in the first tuple position. Right? So in the when guard, we could actually swap out x for n in the x = head check. This is legal: the checks that you do in a match case do NOT have to include only names that have appeared in the match pattern. They can be any names that your function has access to. So it's perfectly valid to swap x out for n and get the match case to look like this:

    | (x, L(head,tail)) when (n = head) -> remove n tail

现在我们看到在这种情况下 都没有使用x 的值，就像在第三种情况下一样.因此，让我们摆脱它:

And now we see that we're not using the value of x in this match case either, just like in the third match case. So let's get rid of it:

    | (_, L(head,tail)) when (n = head) -> remove n tail

现在，让我们将此匹配用例放回我们的函数中，并从整体上看一下该函数:

Now let's put this match case back into our function and take a look at the function as a whole:

let rec remove n l = 
    match (n, l) with
    | (_, A) -> l
    | (_, L(head,tail)) when (n = head) -> remove n tail
    | (_, L(head,tail)) -> L(head, remove n tail)

嗯.你会看看吗?第一个元组项目在比赛案例的每个单点中都有我不在乎".但是，该函数仍在编译时不发出有关不完全匹配模式的警告，并且仍在运行并产生正确的值. (尝试！)那么这告诉我们什么?它告诉我们，我们实际上不需要在与匹配的值中包含n ，因为在匹配模式中我们永远不需要它.我们需要when后卫，而不是比赛模式本身！因此，如果我们实际上从与之匹配的值和匹配模式中删除 n，则结果如下:

Huh. Would you look at that? The first tuple item has "I don't care" in every single spot in the match case. And yet, the function still compiles without warning about incomplete match patterns, and still runs and produces the correct values. (Try it!) So what does this tell us? It tells us that we don't actually need to have n in the value we're matching against, because we never need it in the match patterns. We need it in the when guards, but not in the match patterns themselves! So if we actually remove n from the value we're matching against, and from the match patterns, here's the result:

let rec remove n l = 
    match l with
    | A -> l
    | L(head,tail) when (n = head) -> remove n tail
    | L(head,tail) -> L(head, remove n tail)

尝试一下.您会看到该函数也可以编译，并且仍然完全按照您希望的方式进行操作.

Try it. You'll see that this function also compiles, and still does exactly what you want it to do.

至此，我们真的完成了.从此函数中删除其他任何内容都会破坏它:要么不会编译，要么不会返回正确的值.对于您来说，这可能不是立即显而易见的，但是随着您对F#的掌握程度的提高，您将学到何时将某个功能精简到其基本要领，而这个功能已经有了.

At this point, we really are done. Taking away anything else from this function would break it: either it wouldn't compile, or else it wouldn't return the right value. This may not be immediately obvious to you, but as your skill with F# grows, you'll learn to get a feel for when a function has been pared down to its bare essentials, and this one has.

然后就可以了:经过大量的调整之后，我们获得了remove函数，它不仅可以正常工作，而且可以优雅地工作 .这是最简单的可以实现此功能的方法，并且有一定的美感.如果您能够看到并欣赏这种美，一个功能完全可以实现的美，那么您将成为成为熟练的F#程序员的好方法！

And so there you go: after a lot of tweaking, we've gotten the remove function not just working, but working elegantly. This is the simplest you can possibly make this function, and there's a certain beauty in that. If you can see and appreciate that beauty, the beauty of a function that does exactly what it should and no more, you'll be well on your way to becoming a skilled F# programmer!

P.S.实际上，我们可以对此功能进行另一次重写，因为它实际上可能会更好.就目前而言，此函数并不总是尾部递归的，这意味着，如果在非常大的列表上调用它，则可能会得到StackOverflowException.但是，如果您还没有达到研究尾递归的目的，那么尝试解释如何解决此问题将使您感到困惑，而不是帮助您更好地理解事情.因此，我故意选择以该函数的精简版本结尾，而不是适当"执行尾递归的版本.因为进行那个改进将产生实际上更复杂且难以理解的功能.一旦您对F#很有经验，就值得重新讨论这个问题，并询问如何使此函数进行尾递归?".但是就目前而言，我们在这里拥有的非尾递归版本是您应该学习的版本.一旦了解了如何自行编写此函数，并可以在用户定义的列表数据结构上编写其他列表操作函数，您将具备进行最后改进的知识.

P.S. There is actually one more rewrite that we could do on this function, because it actually could be better. As it stands, this function is not always tail-recursive, which means that if you called it on a really large list, you could get a StackOverflowException. But if you haven't reached the point of studying tail recursion yet, then trying to explain how to fix this problem would be like to confuse you rather than help you understand things better. So I've deliberately chosen to end with this pared-down, elegant version of the function, rather than the version that does tail recursion "properly". Because making that improvement would produce a function that was actually more complicated and harder to understand. Once you're more experienced with F#, it'll be worth revisiting this question and asking "How do I make this function tail-recursive?". But for now, the non-tail-recursive version that we have here is the one that you should study. Once you understand how to write this function on your own, and can write other list-manipulation functions on your user-defined list data structure, then you'll have the knowledge needed to make that last improvement.

我希望这会有所帮助.请留下评论，问我您在解释中不了解的任何内容.

I hope this helps. Please leave a comment asking me about anything you don't understand in my explanation.

这篇关于f#从自己的用户定义列表中删除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！