Haskell语法糖的剥离函数

Question

我想知道如果没有任何语法糖，以下函数会是什么样子：

tails1 :: [a] -> [[a]]
tails1 [] = [[]]
tails1 xs@(x:xs') = xs:tails1 xs'

我最关心的是@操作符的用法，我尝试了下面的方法，但显然不是正确的方法

tails1 ((:) x ((:) xs' [])) = xs:tails1 xs'

Answer 1

因为 tails1 [] 条目在前，我们不需要确保脱糖的 tails1 xs@(x:xs') 只匹配非空列表，因为它们保证是非空的。因此，写 xs@(x:xs') 的唯一效果是让我们可以访问 xs 和 tail xs，因此该行可以重写为：

tails1 xs = xs : tails1 (tail xs)

Answer 2

首先你需要了解列表数据类型。以下是列表数据构造函数：

[] :: [a]
(:) :: a -> [a] -> [a]

其中：

[] 创建一个空列表
(:) 接受一个 a ，一个 a 的列表和 returns 一个 a 的列表，并添加了新元素

假设您有一个列表 [1,2,3,4]。这可以写成 (:) 1 ((:) 2 ((:) 3 ((:) 4 []))) 在表达式 x:xs' 中，x 保持 1 并且 xs' 将保持 (:) 2 ((:) 3 ((:) 4 []))。换句话说，: 获取一个元素和一个列表，并将该元素附加到列表中。

您的示例的等效表达式是：

tails1 ((:) x xs') = ((:)x xs'):tails1 xs'

其中 x 包含列表的第一个元素，xs' 包含列表的其余部分。 xs' 不能容纳多个元素。在您的示例 tails1 ((:) x ((:) xs' [])) = xs:tails1 xs' 中，xs' 应该包含除第一个元素和 [] 之外的所有内容。（在我的考试中它应该是 2:3:4 这不是一个有效的列表，因为没有以 [] 结束）。

Answer 3

在其他回答中，我们看到了两个建议：

tailsA (x:xs') = (x:xs'):tailsA xs
tailsB xs = xs:tailsB (tail xs)

前者指称语义正确，操作语义错误。原来的tails只有一次调用(:)；因此，人们可能会担心，与 tails 的原始定义相比，足够愚蠢的编译器会在运行 tailsA 时分配额外的 cons 单元。后者也有正确的外延，只有一次调用(:)，但插入了一个全新的函数tail，原来没有出现；这种转变似乎需要一些程序员的洞察力来执行。下面，我将展示如何以一种不需要程序员洞察力（因此可以由编译器执行）并且没有额外分配风险的方式将原始定义转换为没有 at 模式的定义。

tailsC xs = case xs of
    x:xs' -> xs:tailsC xs'

这里特别有趣：原始方程式的右侧逐字显示为 case 语句的右侧。（tailsA 或 tailsB 都不包含原始方程式的右侧作为子项。）这种特殊情况转换建议的 at 模式的一般翻译并不完全正确（因为 xs 匹配任何值，而 xs@(x:xs') 仅匹配非空列表）；将 Haskell 样式的模式转换为 GHC 核心样式的 case 语句（仅仔细检查单个变量，并且其模式都只包含一个构造函数）的完整处理超出了 Whosebug 答案的范围。已经有几篇研究论文讨论了如何正确、高效地执行此操作并生成快速代码；另见相关问题 Algorithm for type checking ML-like pattern matching? and basically all of the results in the Google Scholar search for compiling pattern matching.

但基本思想是 name@pattern 恰好在 pattern 匹配时匹配（绑定所有相同的名称 pattern 对所有相同的值），但另外绑定 name 到完整值。

Haskell语法糖的剥离函数

Haskell stripping function of syntactic sugar

haskell

syntactic-sugar