让 cons 既具体又抽象地使用

Question

我在做这个

reverseP x = pour x []
  where pour []    ans = ans
        pour (h:t) ans = pour t (h:ans)

其中参数累加器优于粗糙且昂贵的版本

reverse [] = []
reverse (h:t) = reverse t ++ [h]

但后来我想看看我是否可以用 let 重做 reverseP 作为练习。我终于让它工作了

reverseP2 x =
  let
    (t:ts) = x
    pour [] ans = ans
    pour (t:ts) ans = pour ts (t:ans)
  in pour x []

但我不知道它为什么起作用。期望继续 Haskell 编写我不理解的工作代码是不现实的，所以我想我最好找出它为什么有效。令我困惑的是，我已将传入的 x 分配给缺点（这被认为是元组吗？）(t:ts)，但随后我以“抽象”方式使用 (t:ts) 作为两行后 pour 的参数。由于它有效，递归确实必须正确地分解列表，即第一行中定义的 cons (t:ts) 被正确地拆开。同样令人困惑的是上面的 let 形式如何允许 pour 在模式匹配方式中被定义两次。我尝试与守卫一起将其保持为只有一个 pour，但随后 (t:ts) 没有正确分解——部分原因让我感到惊讶，这会起作用。那么，相同的缺点 (t:ts) 如何既具体又抽象，pour 如何在 let 中递归并进行模式匹配？另外，reverseP2 可以被认为是尾递归吗？

Answer 1

难怪您对 reverseP2 感到困惑。 x 上的模式匹配是多余的，因为 t 和 ts 没有在 let 块中使用。在let块中是使用的t和ts变量是定义的more local变量在（部分）函数定义 pour (t:ts) ans 中。这些 t 和 ts shadow 其他同名变量。

事实上，模式匹配表达式(t:ts) = x完全是多余的。您可以将 reverseP2 简化为：

reverseP2 x =
  let
    pour []     ans = ans
    pour (t:ts) ans = pour ts (t:ans)
  in pour x []

希望这能更清楚地表明它只是使用了另一种语法，但定义与 reverseP 相同。不是在函数定义的开头给出 return 值，而是在 let/in 的 in 块中给出 return 值，而不是定义辅助变量和函数在 where 部分中，您在 let 部分中定义它们。

Answer 2

让我们尝试在打开警告的情况下进行编译：

Prelude> :set -Wall
Prelude> :{
Prelude| reverseP2 x =
Prelude|   let
Prelude|     (t:ts) = x
Prelude|     pour [] ans = ans
Prelude|     pour (t:ts) ans = pour ts (t:ans)
Prelude|   in pour x []
Prelude| :}

<interactive>:7:11: warning: [-Wname-shadowing]
    This binding for `t' shadows the existing binding
      bound at <interactive>:5:6

<interactive>:7:13: warning: [-Wname-shadowing]
    This binding for `ts' shadows the existing binding
      bound at <interactive>:5:8

这条消息在说什么？它说 t 和 ts 的第二个定义是 shadowing 第一个。也就是说，两个 t 和两个 ts 指的不是同一个值——第一个 t:ts 是 x，而第二个 t:ts指的是pour的一个参数。这令人困惑！因此，让我们重命名其中一个：

reverseP2 x =
  let
    (t:ts) = x
    pour [] ans = ans
    pour (a:as) ans = pour as (a:ans)
  in pour x []

事实上，这表明您甚至不需要 t 和 ts，所以让我们摆脱它们：

reverseP2 x =
  let
    pour [] ans = ans
    pour (a:as) ans = pour as (a:ans)
  in pour x []

最后，当我在做的时候，我应该注意对于较长的定义，例如 pour，使用 where 块而不是 let 被认为是惯用的]:

reverseP2 x = pour x []
  where
    pour [] ans = ans
    pour (a:as) ans = pour as (a:ans)

I've assigned the incoming x to the cons (Is this considered a tuple?) (t:ts) …

不，这根本不是一个元组；这是一个列表。如果它是一个元组，它需要有 (a, (a, (a,a))) 或类似的类型；但作为列表，它的类型为 [a].

Also confusing is how the let form above allows pour to be defined twice in the pattern matching way.

但不是定义了两次！您只有一个 pour 的定义，它取决于输入，如下所示：如果输入是空列表，则 pour returns ans，否则为 returns pour as (a:ans).

Also, could reverseP2 be considered tail-recursive?

~~我相信如此~~ 但一般来说尾递归在 Haskell 中被认为是不重要的（参见例如开始于 here 的讨论）。

编辑： 正如@DanienWagner 在评论中指出的那样，reverseP2 根本不是递归的！ pour 是尾递归的。

让 cons 既具体又抽象地使用

let cons used both concretely and abstractly

haskell

let