haskell - 简单列表创建中的评估顺序是什么？

Question

如何评估 1:(2:(3:[]))？

在到达 [1,2,3] 之前采取哪些重写步骤？

是吗

   1:(2:([3])
   1:([2,3])
   [1,2,3]

还是别的什么？上面描述的方法是唯一的方法吗？或者还有其他方法吗？

Answer 1

Haskell 在这里没有任何实际计算的内容，因为 : 是列表的构造函数。当您编写类似 [1, 2, 3] 的内容时，编译器首先将其脱糖为 1 : 2 : 3 : [] 和 这是它在内存中的表示。这就像询问 Just 1 的评估顺序是什么。没有评估顺序，因为它已经处于“最评估”形式，也称为正常形式。

对于列表，正常形式是在空列表前面组合在一起的元素。如果有帮助，您可以将列表定义为

data [a] = [] | a : [a]

或者另一种选择

data List a = Empty | Cons a (List a)

当你进行模式匹配时

f (x:xs) = ...

这相当于进行模式匹配

f (Cons x xs) = ...

唯一真正的区别是使用的名称。

<小时/>

所以我想你问题的答案是你的评估是向后的，你不会从 1:2:3:[] 到 [1, 2, 3 ]，您会从 [1, 2, 3] 转到 1:2:3:[]，尽管此步骤发生在脱糖过程中。至于列表推导式，使用 >> 和 >>= 等一元函数将它们脱糖为映射和过滤器。当您看到类似 [1..10] 的内容时，它实际上使用 Enum 实例作为其元素，并脱糖为 fromEnumTo 和类似的功能。所有这些函数都适用于 : 和 [] 级别的列表，因此它们只是使用列表类型的构造函数，就像使用任何其他数据类型一样.

<小时/>

作为证据，如果我有代码

module Foo where

x :: [Int]
x = [1, 2, 3]

我用ghc -c Foo.hs -ddump-ds编译它，我会得到

Foo.x :: [GHC.Types.Int]
[LclIdX]
Foo.x =
  GHC.Types.:
    @ GHC.Types.Int
    (GHC.Types.I# 1)
    (GHC.Types.:
       @ GHC.Types.Int
       (GHC.Types.I# 2)
       (GHC.Types.:
          @ GHC.Types.Int (GHC.Types.I# 3) (GHC.Types.[] @ GHC.Types.Int)))

其中有很多额外的元数据，所以让我们删除所有额外的类型注释、模块名称和其他噪音:

Foo.x :: [Int]
Foo.x = GHC.Types.: 1 (GHC.Types.: 2 (GHC.Types.: 3 []))

或者甚至更多删除

x :: [Int]
x = : 1 (: 2 (: 3 []))

请注意，在核心中(GHC 将 Haskell 源代码编译为所用的 3 种中间语言之一)，我们不需要以前缀形式围绕运算符使用括号。但很容易看出，一旦所有内容都被脱糖，它就简单地表示为一个组合在一起的列表。

但是等等!我以为you said that the parens weren't needed ？当它采用中缀形式时确实如此，但现在 : 被用作前缀函数。很容易看出，使用前缀时，需要括号，特别是如果将 : 替换为 Cons 并将 [] 替换为 Empty :

x = Cons 1 (Cons 2 (Cons 3 Empty))

因为以下内容不会进行类型检查。它使它看起来像 Cons 需要 6 个参数!

x = Cons 1 Cons 2 Cons 3 Empty