问题标签 [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.
haskell - 为什么我们使用折叠将数据类型编码为函数?
或者具体来说,为什么我们使用 foldr 来编码列表和迭代来编码数字?
很抱歉介绍冗长,但我真的不知道如何命名我想问的事情,所以我需要先做一些说明。这很大程度上来自这篇 CAMcCann 帖子,它不能完全满足我的好奇心,而且我还将讨论 rank-n-types 和无限懒惰事物的问题。
将数据类型编码为函数的一种方法是创建一个“模式匹配”函数,该函数为每种情况接收一个参数,每个参数都是一个函数,该函数接收与该构造函数相对应的值,并且所有参数都返回相同的结果类型。
对于非递归类型,这一切都按预期进行
然而,与模式匹配的很好的类比在递归类型中被打破了。我们可能会想做类似的事情
但是我们不能在 Haskell 中编写那些递归类型定义!通常的解决方案是强制将 cons/succ 案例的回调应用于所有级别的递归,而不仅仅是第一个级别(即,编写折叠/迭代器)。在这个版本中,我们使用r
递归类型的返回类型:
虽然此版本有效,但它使定义某些功能变得更加困难。例如,如果您可以使用模式匹配,则为列表编写“tail”函数或为数字编写“predecessor”函数是微不足道的,但如果您需要使用折叠来代替,则变得很棘手。
所以我的真正问题是:
我们如何确定使用折叠的编码与假设的“模式匹配编码”一样强大?有没有办法通过模式匹配来获取任意函数定义,然后机械地将其转换为仅使用折叠的函数?(如果是这样,这也将有助于在 foldr 方面使诸如 tail 或 foldl 之类的棘手定义变得不那么神奇)
为什么 Haskell 类型系统不允许“模式匹配”编码中需要的递归类型?. 是否有理由只允许在通过定义的数据类型中使用递归类型
data
?模式匹配是直接使用递归代数数据类型的唯一方法吗?它与类型推断算法有关吗?
haskell - 是否有任何非递归项可以折叠在斯科特编码列表上?
假设我有一个scott 编码的列表,例如:
我想要一个接收此类列表并将其转换为实际列表([1,2,3]
)的函数,但此类函数不能递归。也就是说,它必须是 eta-beta 范式。有这个功能吗?
haskell - 如何使用 Scott Encoding 表示嵌套类型?
ADT 可以使用 Scott 编码来表示,方法是用元组替换乘积,用匹配器替换总和。例如:
可以使用 Scott Encoding 编码为:
但我找不到如何使用 SE 对嵌套类型进行编码:
怎么做到呢?
haskell - 如何为 Free Monads 使用 Church 编码?
我一直在使用包中的数据Free
类型。现在我正在尝试将其转换为使用但不知道如何映射函数。Control.Monad.Free
free
F
Control.Monad.Free.Church
例如,一个简单的模式匹配函数使用Free
如下所示 -
F
我可以轻松地将其转换为通过转换为/从使用的函数Free
-
但是我不知道如何在不使用toF
和的情况下完成它fromF
-
一定有一个我缺少的一般模式。你能帮我弄清楚吗?
list - 教会编码列表的更有效的尾部
这是一个有文化的haskell帖子。只需将其保存为“ChurchList.lhs”即可运行。
Church 编码列表是一种通过函数表示列表的方式。它类似于弃牌和连续传球风格。
为了说明这如何对应于一个列表,这里是一个 O(n) 同构
这些东西具有良好的性能特征。
现在,问题来了tail
。
基本上我的实现所做的是将列表分成头部和尾部。Cons 替换了头部,并将旧的头部附加到尾部。这是相当低效的。似乎教会列表在拆分方面通常效率低下。
我希望我错了。有没有tailCl
比 O(n) 更好的实现(最好是 O(1))。
haskell - 为什么 rank-n 类型需要显式的 forall 量词?
当我声明这个新类型时:
这将定义假设的 rank-2 类型ListScott :: ((a -> ListScott a -> r) -> r -> r) -> ListScott a
,编译器抱怨r
不在范围内。从我想将一流的多态函数传递给的类型签名不是很明显ListScott
吗?
为什么我需要一个明确的类型量词来r
处理这种情况?
我不是类型理论家,可能忽略了一些东西......
haskell - 如何使用以连续传递样式编码的 Reader 类型
我的印象是,每个类型的值a
都可以用newtype Id a = Id {runId :: forall r. (a -> r) -> r }
连续传递风格的 2 级多态类型来描述。所以我派生了以下类型来Reader
相应地定义:
然后我尝试构造一个这种类型的值并运行它:
如果Reader
CPS 中的编码及其类型有效,我将如何使用它?
haskell - 如何推断 Scott 编码的 List 构造函数的类型?
Scott编码列表可以定义如下:
与 ADT 版本相反的List
是类型和数据构造函数。Scott 编码通过模式匹配来确定 ADT,这实质上意味着移除了一层构造函数。这是uncons
没有隐式参数的完整操作:
这很有意义。uncons
接受一个常数、一个延续和 aList
并产生任何值。
然而,数据构造函数的类型对我来说没有多大意义:
我看到它r
有自己的范围,但这不是很有帮助。为什么都r
和List a
翻转相比uncons
?为什么 LHS 上有额外的括号?
我可能在这里混淆了类型和术语级别..
javascript - 如何使用函数编码实现 Haskell 的 newtype?
单挑:这是一个跨语言问题。
我将通过实施差异列表来演示该问题。这是 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 的答案。