f#从自己的用户定义列表中删除

Question

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

这是数据类型

type alist = 
    A 
  | L of int * Alist

以下是数据类型的外观:

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)))

这是我到目前为止:

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

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

Answer 1

你不应该考虑"删除"清单; 你应该考虑建立一个新的列表,而不是你想要删除的元素.我会在一分钟内告诉你如何做到这一点,但首先我想提出一个建议.在match表达式中,您将重复使用n模式中的名称.这是一个经典的初学者的错误,因为它最终让你感到困惑.一旦你很了解F#,这是一种有效的技术,但由于你似乎是一个初学者,我强烈建议不要这样做.相反,在您的模式中使用与您要匹配的东西的名称不同的名称,因为这将有助于教您一些东西.让我们用您的模式中x的名称重写您的匹配表达式int:

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

这两种模式的作用是分配名称x来表示n模式的其余部分是否匹配的值.现在我们可以更清楚地看到第一个模式根本不使用它的值x,所以_在这种情况下表示它会更好(_是"通配符"模式,这意味着"我不关心在这个位置的价值).因此,你的match表达将成为:

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

现在让我们考虑一下我们想要在第二场比赛中做些什么.这里我们有一个节点,它正是我们想要从列表中删除的节点类型.那么我们如何构建一个没有该节点的列表呢？好吧,事实上,我们已经有了这样一个列表 ......我们已经tail在第二个匹配案例中为它指定了名称.所以起初看起来我们可能会这样做:

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

这将返回一个列表,其中"head"节点被切断.可是等等!如果尾部本身包含一个或多个具有我们想要删除的值的节点怎么办？我们真的想从这个匹配情况返回的是tail,通过一个函数来传递一个函数,该函数将删除所有匹配某个值的节点.但是......等一下......不是我们写一个函数一样,现在的权利？如果我们可以只是打电话remove给尾巴并让它为我们完成剩下的工作怎么办？那不是很好吗？

好吧,事实证明我们可以!要从tail列表中删除其余不需要的值,您只需要调用remove它!像这样:

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

但是我们还没有完成,因为你的match陈述中还有一种可能性.如果您使用的是良好的F#开发环境(我建议使用带有Ionide插件的Visual Studio Code),您应该会在关键字下看到绿色波浪下划线,如果将鼠标悬停在它上面,您应该会看到有关不完整匹配表达式的警告.那是因为有一种情况我们没有考虑到:情况是一个节点不是,但其值不等于.换句话说,这个匹配案例:matchlAheadn

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

好吧,对于初学者来说,让我们稍微简化这个匹配案例吧.如果我们将它放入完整的匹配表达式中,我们应该看到when防护实际上是不必要的.匹配案例按顺序从上到下进行检查.这意味着,如果我们到了第三场比赛的情况下,我们已经知道那x必须不等于head; 否则第二场比赛将被选中!您可能无法看到原因,所以让我们将匹配大小写放入我们的匹配表达式并查看它:

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表达式必须为真 - 因为如果它是假的,那么这意味着它x等于head,所以我们将减少第二个匹配情况,而不是第三个.

因此,我们实际上可以去除的when,从第三场比赛的情况下,现在看起来像这样后卫:

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已从其中删除.(如果你不理解最后一句话,请花一点时间试着想象一下这个.)那么我们怎么做呢？嗯,最简单的方法如下:

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

哪个可以简化为:

L(head, remove n tail)

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

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 de Saint-Exupéry最着名的是写小王子,但他也是一名飞行员,有着名的设计:

Il semble que la perfection soit notinte non quand il n'y arienàajouter,mais quand il n'y a plusrienàreranrancher.

在英语中,那是:

似乎没有更多的东西可以实现完美,但是没有什么可以去除的.

那么我们可以从这个功能中删除什么来削减绝对必需品呢？好吧,让我们再看看最后一场比赛的情况:

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

看起来我们不使用x此匹配情况中的任何位置的值,因此我们实际上不需要在此匹配情况下为int指定名称.我们可以在_这里使用通配符.一旦我们这样做,我们的功能看起来像:

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)

在这一点上,你可能会认为我们真的完成了,因为我们确实使用x了第二个匹配情况中的值,所以我们无法摆脱它.或者......我们可以吗？让我们更仔细地看一下第二场比赛案例:

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

现在.的价值x在这里是一样的价值n,因为这场比赛的情况下实际上是分配的值n的名称x凭借x在第一个元组位置之中.对？因此,在when后卫中,我们可以真正换出x了n在x = head检查.这是合法的:您在匹配案例中执行的检查不必仅包括匹配模式中出现的名称.它们可以是您的函数可以访问的任何名称.因此,换x出n并获得匹配大小写是完全有效的:

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

而现在我们看到,我们没有使用的价值x在本场比赛的情况下要么,就像在第三场比赛的情况下.所以让我们摆脱它:

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

现在让我们把这个匹配案例放回到我们的函数中,看一下整个函数:

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,并从匹配模式中删除,则结果如下:

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)

试试吧.您会看到此函数也会编译,并且仍然完全按照您的要求执行.

在这一点上,我们确实正在做.从这个函数中取走任何其他东西都会破坏它:要么它不会编译,要么它不会返回正确的值.对你来说这可能不会立即显而易见,但随着你对F#技能的提高,你将学会了解一个功能何时被削减到其基本要素,并且这个功能已经完成了.

所以你去了:经过大量的调整,我们得到的remove功能不仅仅是工作,而是优雅地工作.这是最简单的你可以做这个功能,并且有一定的美感.如果你能够看到并欣赏这种美丽,那种功能的美妙之处就是它应该做到的,而不是更多,你将成为一名熟练的F#程序员!

PS实际上我们可以对这个函数做一次重写,因为它实际上可能更好.就目前而言,这个函数并不总是尾递归,这意味着如果你在一个非常大的列表上调用它,你可能会得到一个StackOverflowException.但是,如果你还没有达到研究尾递归的程度,那么试图解释如何解决这个问题就像混淆你而不是帮助你更好地理解事物.因此,我故意选择使用这个简洁优雅的函数版本,而不是"正确"执行尾递归的版本.因为进行这种改进会产生一种实际上更复杂,更难理解的功能.一旦你对F#更有经验,那么值得重新审视这个问题并询问"我如何使这个函数尾递归？".但就目前而言,我们这里的非尾递归版本是您应该学习的版本.一旦您了解了如何自己编写此函数,并且可以在用户定义的列表数据结构上编写其他列表操作函数,那么您将拥有完成最后一次改进所需的知识.

我希望这有帮助.请在我的解释中留下评论询问我你不理解的任何事情.