2

我过去曾涉足过 Haskell，最近又认真研究了它，我正在阅读真实世界的 Haskell。他们所展示的一些例子，我还没有理解。这样的：

myLength []     = 0
myLength (x:xs) = 1 + myLength (xs)

我不明白这是如何工作的，真正添加的 1 是什么？递归如何返回可以添加的东西？我不明白。

在这里我们有这个：

splitLines [] = []
splitLines cs =
       let (pre, suf) = break isLineTerminator cs
       in  pre : case suf of 
                   ('\r':'\n':rest) -> splitLines rest
                   ('\r':rest)      -> splitLines rest
                   ('\n':rest)      -> splitLines rest
                   _                -> []

isLineTerminator c = c == '\r' || c == '\n'

这是如何工作的，什么是 pre 真正被附加的？我不明白 case 表达式的结果是如何可以连接 pre 的。也许我只是需要有人详细解释这些功能的评估。我一定错过了一些非常重要的东西。

提前致谢！

编辑：我知道，这是复制粘贴失败。对不起。

编辑2：似乎我的困惑是这些功能实际上是/返回/我现在已经全部解决了。谢谢各位大神解答，终于成功了！我很感激！

4

5 回答 5

10

至于第一种，它是一种非常基本的递归方式。但是，它似乎缺少了一部分：

myLength [] = 0

它的工作原理是每次从列表中缩小一个元素并将一个元素添加到结果中。为了可视化，考虑调用

myLength [1,2,3]

这将评估为：

1 + myLength [2,3]
1 + 1 + myLength [3]
1 + 1 + 1 + myLength []
1 + 1 + 1 + 0

这是3。

至于第二个，好吧，您已经将下一行的字符串分成两部分：pre 和 suf。现在，suf 将以 \n、\r 或 \r\n 开头。我们想删除这些。所以我们使用模式匹配。看看 rest 变量如何本质上是 suf 变量减去初始换行符。

所以我们有pre，它是第一行，还有rest，它是文本的其余部分。因此，为了继续将其余部分拆分为行，我们递归地调用 splitLines 并将结果连接到 pre。

为了形象化，假设你有字符串“foo\nbar\r\nbaz”。

因此，调用时，结果将是：

[ pre => foo, suf => \nbar\r\nbaz, rest => bar\r\n\baz ]
foo : splitLines bar\r\nbaz

然后再次调用 splitLines，结果展开为：

[ pre => bar, suf => \r\nbaz, rest = baz ]
foo : bar : splitLines baz

然后再一次：

[ pre => baz, suf => [], rest = [] ]
foo : bar : baz

这是最终的结果。

于 2009-05-25T21:09:18.090 回答
4

我认为的定义myLength错过了列表为空的情况：

myLength [] = 0
myLength (x:xs) = 1 + myLength (xs)

使用此定义，myLength空列表的 为 0。(x:xs)模式将列表解压缩为第一个项目 ，a以及包含其余项目的列表，xs。如果列表有一项，xs则为空列表，因此结果为 1 + 0。依此类推。

当您首先查看基本情况时，递归是最容易理解的，然后查看每个级别的递归是如何建立在结果上的。（基本情况是函数不调用自身的情况。如果递归函数没有基本情况，则输出将是无限的。）

在第二个示例中，基本案例（案例陈述中的最后一个案例）也是一个空列表。所以 pre 总是会被附加到一个列表中，这将产生一个新的、更长的列表。

于 2009-05-25T20:53:24.347 回答
2

回复：myLength (x:xs) = 1 + myLength (xs)-这是定义的“一半” myLength，它说，通过模式匹配，如果参数有一个头和一个尾，那么结果比尾部的递归尾调用多一个——需要另一半说当参数无法匹配时结果为 0 x:xs，即当参数为空列表时。

在第二种情况下，不同模式匹配的可能性只是通过case.

顺便说一句，懒惰不是这里的关键问题——ML，具有急切的评估但很像 Haskell 的模式匹配，将非常相似地工作。看起来模式匹配是你真正需要复习的。

于 2009-05-25T20:53:57.433 回答
2

首先第一个例子应该是这样的（编辑：看起来你现在修复了它）：

myLength []     = 0
myLength (x:xs) = 1 + myLength (xs)

它的工作原理是这样的：假设我给它一个包含三个项目的列表，它返回一加尾巴的长度（这是一加尾巴的长度（这是一加尾巴的长度，（[]在这个点），即1），即w），即3（最终答案）。也许嵌套括号会帮助您理解它。;-)

于 2009-05-25T21:04:25.260 回答
1

看看函数的类型签名是什么是有启发性的。他们可能是：

myLength :: [a] -> Int

在myLength, 1 被添加到递归调用的结果中myLength，这是一个Int，这反过来导致一个Int。

splitLines :: [Char] -> [[Char]]

在splitLines, pre(a [Char]) 被添加到 case 语句的结果之前，从案例来看，它是递归调用的结果splitLines，即[[Char]]; 或一个空列表。在这两种情况下，前置pre(a [Char]) 将[[Char]]依次生成 a。

于 2009-05-25T21:05:25.537 回答