问题标签 [scott-encoding]

或者具体来说，为什么我们使用 foldr 来编码列表和迭代来编码数字？

很抱歉介绍冗长，但我真的不知道如何命名我想问的事情，所以我需要先做一些说明。这很大程度上来自这篇 CAMcCann 帖子，它不能完全满足我的好奇心，而且我还将讨论 rank-n-types 和无限懒惰事物的问题。

将数据类型编码为函数的一种方法是创建一个“模式匹配”函数，该函数为每种情况接收一个参数，每个参数都是一个函数，该函数接收与该构造函数相对应的值，并且所有参数都返回相同的结果类型。

对于非递归类型，这一切都按预期进行

然而，与模式匹配的很好的类比在递归类型中被打破了。我们可能会想做类似的事情

但是我们不能在 Haskell 中编写那些递归类型定义！通常的解决方案是强制将 cons/succ 案例的回调应用于所有级别的递归，而不仅仅是第一个级别（即，编写折叠/迭代器）。在这个版本中，我们使用r递归类型的返回类型：

虽然此版本有效，但它使定义某些功能变得更加困难。例如，如果您可以使用模式匹配，则为列表编写“tail”函数或为数字编写“predecessor”函数是微不足道的，但如果您需要使用折叠来代替，则变得很棘手。

所以我的真正问题是：

1. 我们如何确定使用折叠的编码与假设的“模式匹配编码”一样强大？有没有办法通过模式匹配来获取任意函数定义，然后机械地将其转换为仅使用折叠的函数？（如果是这样，这也将有助于在 foldr 方面使诸如 tail 或 foldl 之类的棘手定义变得不那么神奇）

2. 为什么 Haskell 类型系统不允许“模式匹配”编码中需要的递归类型？. 是否有理由只允许在通过定义的数据类型中使用递归类型data？模式匹配是直接使用递归代数数据类型的唯一方法吗？它与类型推断算法有关吗？

假设我有一个scott 编码的列表，例如：

我想要一个接收此类列表并将其转换为实际列表（[1,2,3]）的函数，但此类函数不能递归。也就是说，它必须是 eta-beta 范式。有这个功能吗？

ADT 可以使用 Scott 编码来表示，方法是用元组替换乘积，用匹配器替换总和。例如：

可以使用 Scott Encoding 编码为：

但我找不到如何使用 SE 对嵌套类型进行编码：

怎么做到呢？

我一直在使用包中的数据Free类型。现在我正在尝试将其转换为使用但不知道如何映射函数。Control.Monad.FreefreeFControl.Monad.Free.Church

例如，一个简单的模式匹配函数使用Free如下所示 -

F我可以轻松地将其转换为通过转换为/从使用的函数Free-

但是我不知道如何在不使用toF和的情况下完成它fromF-

一定有一个我缺少的一般模式。你能帮我弄清楚吗？

这是一个有文化的haskell帖子。只需将其保存为“ChurchList.lhs”即可运行。

Church 编码列表是一种通过函数表示列表的方式。它类似于弃牌和连续传球风格。

为了说明这如何对应于一个列表，这里是一个 O(n) 同构

这些东西具有良好的性能特征。

现在，问题来了tail。

基本上我的实现所做的是将列表分成头部和尾部。Cons 替换了头部，并将旧的头部附加到尾部。这是相当低效的。似乎教会列表在拆分方面通常效率低下。

我希望我错了。有没有tailCl比 O(n) 更好的实现（最好是 O(1)）。

当我声明这个新类型时：

这将定义假设的 rank-2 类型ListScott :: ((a -> ListScott a -> r) -> r -> r) -> ListScott a，编译器抱怨r不在范围内。从我想将一流的多态函数传递给的类型签名不是很明显ListScott吗？

为什么我需要一个明确的类型量词来r处理这种情况？

我不是类型理论家，可能忽略了一些东西......

我的印象是，每个类型的值a都可以用newtype Id a = Id {runId :: forall r. (a -> r) -> r }连续传递风格的 2 级多态类型来描述。所以我派生了以下类型来Reader相应地定义：

然后我尝试构造一个这种类型的值并运行它：

如果ReaderCPS 中的编码及其类型有效，我将如何使用它？

Scott编码列表可以定义如下：

与 ADT 版本相反的List是类型和数据构造函数。Scott 编码通过模式匹配来确定 ADT，这实质上意味着移除了一层构造函数。这是uncons没有隐式参数的完整操作：

这很有意义。uncons接受一个常数、一个延续和 aList并产生任何值。

然而，数据构造函数的类型对我来说没有多大意义：

我看到它r有自己的范围，但这不是很有帮助。为什么都r和List a翻转相比uncons？为什么 LHS 上有额外的括号？

我可能在这里混淆了类型和术语级别..

单挑：这是一个跨语言问题。

我将通过实施差异列表来演示该问题。这是 Scott 编码的List，它提供了基本类型。我将它与动态类型验证器一起使用，因此我需要一个包装器来关联类型List a（在下面的示例中进行了简化）：

thunk(() => ...)行中的表达式A创建一个隐式 thunk，即（除了===）您可以将其视为 thunk 延迟的表达式。在这种情况下，它具有类型Last a。

这在没有 ADT 的热切语言中几乎是标准的。接下来我想提供一个差异列表提供的高效append和操作。snoc在这一点上，事情变得一团糟。在 Haskell 中，这种类型是用newtype包装器声明的，但我不知道如何使用 Scott 编码来实现它。所以我坚持使用正常的编码：

好吧，这是可行的，但是像 monoid 实例这样简单的事情的实现相当复杂。必须进行模式匹配（cons(...)并cons_(...)在行中B）以获得部分应用的List.append（List a -> List a）是多余的。并且不必要地复杂化。

也许它就像完全放弃 Scott 编码一样简单，但我不想在类型级别上List a -> List a丢失类型抽象。DList a希望有更多经验的人可以指出正确的方法。

感谢使用 Haskell 或 JS 的答案。