parsing - Haskell解析: x++ y : z

Question

在 Haskell 中，为什么 x++ y : z 被解析为 x++ (y : z) 而不是 (x++ y) :z？

例如，[1]++ 2 : [3] 计算结果为 [1,2,3]。

(++) 和 (:) 都是右结合，优先级为 5。

Answer 1

事实上，它们右关联意味着它们可以说是“从右到左”解析的。因此，这意味着 x ⊕ y ⊕ z 被解析为 x⊕ (y ⊕ z)。因此，这意味着 x++ y : z 确实被解析为 x++ (y : z)。

有充分的理由使 (:) 和 (++) 都成为右关联。对于“cons”(:) 运算符，这意味着我们可以编写 1 : 4 : 2 : []，因为它被解析为 1 : ( 4 : (2: []))，就类型而言是正确的。如果像 ((1:4):2:[]) 一样解析它，那么 1:4 就会是错误的，因为它期望一个项目作为第一个操作数，并将这些项目的列表作为第二个操作数。我们当然仍然可以让 Haskell 解析器将其解析为列表，但这会导致大量额外的括号。

对于(++)，由于性能原因，最好从右到左解析它。 x++ y 需要以 x 大小为单位的线性时间。因此，这意味着如果我们解析 x++ (y++ z)，它将需要 |x| + |y| 步。如果我们将其解析为 (x++ y)++ z，则需要 2×|x|+|y|，因为我们第一次应用 (x++ y) 它以 x 的大小运行，但是 (x++ y)++ z 运行的大小为x++y。因此，这意味着如果我们连接 n 个大小为 m 的列表，它不会在 O(n×m) 中运行，但需要O(n²×m)。