问题标签 [scott-encoding]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
2 回答
1278 浏览

haskell - 为什么我们使用折叠将数据类型编码为函数?

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

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


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

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

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

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

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

所以我的真正问题是:

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

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

0 投票
1 回答
158 浏览

haskell - 是否有任何非递归项可以折叠在斯科特编码列表上?

假设我有一个scott 编码的列表,例如:

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

0 投票
2 回答
617 浏览

haskell - 如何使用 Scott Encoding 表示嵌套类型?

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

可以使用 Scott Encoding 编码为:

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

怎么做到呢?

0 投票
4 回答
1482 浏览

haskell - 如何为 Free Monads 使用 Church 编码?

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

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

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

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

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

0 投票
3 回答
721 浏览

list - 教会编码列表的更有效的尾部

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

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

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

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

现在,问题来了tail

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

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

0 投票
2 回答
378 浏览

haskell - 为什么 rank-n 类型需要显式的 forall 量词?

当我声明这个新类型时:

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

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

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

0 投票
1 回答
60 浏览

haskell - 如何使用以连续传递样式编码的 Reader 类型

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

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

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

0 投票
2 回答
148 浏览

haskell - 如何推断 Scott 编码的 List 构造函数的类型?

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

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

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

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

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

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

0 投票
1 回答
123 浏览

javascript - 如何使用函数编码实现 Haskell 的 newtype?

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

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

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

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

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

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

感谢使用 Haskell 或 JS 的答案。