拥有“(a -> b) -> b”是否等同于拥有“a”?

2023-12-26

在纯函数式语言中,您可以对值执行的唯一操作就是对其应用函数。

换句话说,如果你想用 type 的值做任何有趣的事情a你需要一个具有类型的函数(例如)f :: a -> b然后应用它。如果有人递给你(flip apply) a与类型(a -> b) -> b,是一个合适的替代品吗?a?

你会怎么称呼有类型的东西(a -> b) -> b?看到它似乎是一个替代品a,我很想将其称为代理,或者来自http://www.thesaurus.com/browse/proxy http://www.thesaurus.com/browse/proxy.


卢基的回答非常好,但我要提供另一种解释forall b. (a -> b) -> b === a有几个原因:首先,因为我认为对 Co密度的概括有点过于热情。其次,因为这是一个将一堆有趣的事情联系在一起的机会。向前!

z5h的魔盒

想象一下,有人抛了一枚硬币,然后将其放入一个魔法盒中。您看不到盒子内部,但如果您选择一种类型b并向盒子传递一个类型为的函数Bool -> b,盒子会吐出一个b。如果不看盒子内部,我们能了解到什么?我们能知道硬币的状态是什么吗?我们能否了解盒子使用什么机制来产生b?事实证明,我们可以两者兼得。

我们可以将盒子定义为rank 2类型函数Box Bool where

type Box a = forall b. (a -> b) -> b

(这里,等级2类型意味着盒子制造商选择a和盒子用户选择b.)

我们把a放在盒子里,然后我们关闭盒子,创建......closure.

-- Put the a in the box.
box :: a -> Box a
box a f = f a

例如,box True。部分应用程序只是创建闭包的巧妙方法!

现在,硬币是正面还是反面?因为我,盒子用户,可以选择b,我可以选择Bool并传入一个函数Bool -> Bool。如果我选择id :: Bool -> Bool那么问题来了:盒子会吐出它所包含的值吗?答案是盒子要么吐出它包含的值,要么吐出无意义的值(像这样的底部值undefined)。换句话说,如果你得到一个答案,那么这个答案must是正确的。

-- Get the a out of the box.
unbox :: Box a -> a
unbox f = f id

因为我们无法在 Haskell 中生成任意值,所以盒子能做的唯一有意义的事情就是将给定的函数应用于它隐藏的值。这是参数多态性的结果,也称为参数化.

现在,为了表明Box a同构于a,我们需要证明关于装箱和拆箱的两件事。我们需要证明你投入了什么就能得到什么,并且你可以投入你得到的东西。

unbox . box = id
box . unbox = id

我将完成第一个任务,并将第二个任务留给读者作为练习。

  unbox . box
= {- definition of (.) -}
  \b -> unbox (box b)
= {- definition of unbox and (f a) b = f a b -}
  \b -> box b id
= {- definition of box -}
  \b -> id b
= {- definition of id -}
  \b -> b
= {- definition of id, backwards -}
  id

(如果这些证明看起来相当微不足道,那是因为 Haskell 中的所有(全部)多态函数都是自然变换,而我们在这里证明的is自然性。参数化再次为我们提供了极低价格的定理!)

作为读者的旁白和另一个练习,为什么我不能真正定义rebox with (.)?

rebox = box . unbox

为什么我必须内联定义(.)我自己就像某种穴居人吗?

rebox :: Box a -> Box a
rebox f = box (unbox f)

(提示:有哪些类型box, unbox, and (.)?)

身份与密度和米田,天哪!

现在,我们如何概括Box?卢基使用密度 http://hackage.haskell.org/package/kan-extensions-5.0.2/docs/Control-Monad-Codensity.html: both bs 由任意类型构造函数泛化,我们将调用该构造函数f。这是代码密度转换 http://comonad.com/reader/2011/free-monads-for-less/ of f a.

type CodenseBox f a = forall b. (a -> f b) -> f b

如果我们修复f ~ Identity然后我们回来Box。然而,还有另一种选择:我们可以只命中返回类型f:

type YonedaBox f a = forall b. (a -> b) -> f b

(我已经用这个名字放弃了游戏,但我们会回来讨论这个。)我们还可以修复f ~ Identity在这里恢复Box,但我们让盒子用户传入一个普通函数而不是 Kleisli 箭头。要了解what我们正在概括,让我们再看看它的定义box:

box a f = f a

嗯,这只是flip ($),不是吗?事实证明,我们的另外两个盒子是通过泛化构建的($): CodenseBox是一个部分应用的、翻转的一元绑定,YonedaBox是部分应用的flip fmap。 (这也解释了为什么Codensity f is a Monad and Yoneda f is a Functor for any的选择f:创建一个的唯一方法是分别关闭绑定或 fmap。)此外,这两个深奥的范畴论概念实际上是许多程序员熟悉的概念的概括:CPS 变换!

换句话说,YonedaBox是米田嵌入和正确抽象的box/unbox法律为YonedaBox是米田引理的证明!

TL;DR:

forall b. (a -> b) -> b === a是米田引理的一个实例。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

拥有“(a -> b) -> b”是否等同于拥有“a”? 的相关文章

  • duckmap 到底有什么作用?

    From 文档 https docs perl6 org routine duckmap duckmap将会应用 block每个元素上并返回一个新列表 其中包含块的已定义返回值 对于未定义的返回值 duckmap如果该元素实现了 将尝试下降
  • 为什么 mod 在表达式中给出的结果与在函数调用中给出的结果不同?

    假设有人想要计算函数 f x y x mod 3 y mod 3 mod 2 那么 如果再展开f 1 0 手动 可以得到 1 mod 3 0 mod 3 mod 2 1 然而 如果使用内联函数 结果是 let f x y x mod 3 y
  • 我为什么要学习 Lisp? [关闭]

    就目前情况而言 这个问题不太适合我们的问答形式 我们希望答案得到事实 参考资料或专业知识的支持 但这个问题可能会引发辩论 争论 民意调查或扩展讨论 如果您觉得这个问题可以改进并可能重新开放 访问帮助中心 help reopen questi
  • F# 中的动态编程

    实现解决问题的动态规划算法的最优雅的方法是什么子问题重叠的问题 http en wikipedia org wiki Overlapping subproblem 在命令式编程中 人们通常会创建一个按问题大小索引的数组 至少在一维 然后算法
  • 有没有好的 Clojure 基准测试?

    Edit Clojure 基准测试已达到基准游戏 http benchmarksgame alioth debian org u64q clojure html 我已经制作了这个问题社区维基并邀请其他人保持更新 有人知道 Clojure 性
  • Haskell Fibonacci 达到最大指定数?

    我有一个已启动并正在运行的 Haskell 函数 但它做错了事情 它应该输出最多指定最大数量的斐波那契数列 像这样 fibonacciSequence 86 1 1 2 3 5 8 13 21 33 54 我的代码当前输出斐波那契数列中的前
  • 你将如何在 Haskell 中(重新)实现迭代?

    iterate a gt a gt a gt a 你可能知道 iterate是一个接受函数和起始值的函数 然后它将函数应用于起始值 然后将相同的函数应用于最后的结果 依此类推 Prelude gt take 5 iterate 2 2 2
  • 如何在 Octave 中使用具有自定义功能的地图?

    假设我有一个集合A A 0 6 100 我有一个功能fib n function retval fib n g1 1 5 5 2 g2 1 5 5 2 retval 1 5 5 g1 n g2 n endfunction 我希望能够申请fi
  • 如何从具有函数依赖关系的类型类中获取和使用依赖类型?

    如何从具有函数依赖关系的类型类中获取和使用依赖类型 为了澄清并给出我最近的尝试的一个例子 从我正在编写的实际代码中最小化 class Identifiable a b a gt b where if you know a you know
  • 为什么我不能声明推断类型?

    我有以下内容 runcount Eq a Num b gt a gt b runcount runcountacc 0 runcountacc Eq a Num b gt b gt a gt b runcountacc n runcount
  • 并行 Haskell - GHC GC 火花

    我有一个正在尝试并行化的程序 带有可运行代码的完整粘贴here http lpaste net 101528 我进行了分析 发现大部分时间都花在findNearest这本质上是一个简单的foldr超过一个大Data Map findNear
  • 基于函数签名的模式匹配

    在 F 中 您可以对函数签名进行模式匹配 我想用一个函数来装饰多个函数 该函数测量函数的执行情况并调用 statsd 我当前的功能是 let WrapFunctionWithPrefix metrics Metric Client IRec
  • 返回带有参数的函数的函数

    创建一个应返回包含原始函数参数的函数时 我应该如何处理 例如考虑这个函数 a lt function value function x x value 我希望它返回我在结果函数的参数中指定的值 如下所示 b lt a 3 gt b gt f
  • 这个实例有什么问题:ArrowApply Automaton?

    我希望 Automaton 有实例 ArrowApply 但 Control Arrow Transformer Automaton 没有 我认为下面的代码会表现良好 data Automaton b c Auto runAuto b gt
  • Java泛型 - 实现像map这样的高阶函数

    我决定用 Java 编写一些常见的高阶函数 map filter reduce 等 这些函数通过泛型实现类型安全 但我在一个特定函数中遇到通配符匹配问题 为了完整起见 函子接口是这样的 The interface containing th
  • 如何使用 rxpy/rxjs 延迟事件发射?

    我有两个事件流 一个来自电感环路 另一个来自网络摄像机 汽车将驶过环路 然后撞上相机 如果事件彼此相差在 N 毫秒内 汽车总是会首先进入循环 我想将它们组合起来 但我也希望每个流中不匹配的事件 硬件可能会失败 全部合并到单个流中 像这样的事
  • 为什么对本地列表求和比用“GHC -O2”对教会编码列表求和慢?

    为了测试教会编码的列表如何针对用户定义的列表和本机列表执行 我准备了 3 个基准测试 用户定义的列表 data List a Cons a List a Nil deriving Show lenumTil n go n Nil where
  • Haskell 五个独特的 Wordle 单词

    为了好玩 我正在尝试解决 Matt Parker 在他的 Haskell 频道 Standup Maths in Haskell 频道的链接视频中谈到的与 Wordle 相关的问题 基本上 找到 5 个没有任何共同字母的 5 个字母单词 因
  • monadicIO 的工作原理

    我有以下代码 fastShuffle a gt IO a fastShuffle a
  • 告诉阴谋集团主模块在哪里

    我有一个具有以下结构的项目 foo cabal src Foo Main hs foo cabal 的一部分如下所示 executable foo main is Foo Main hs hs source dirs src Main hs

随机推荐

  • Boost Python:在函数中通过引用传递变量时出错

    我想了解为什么以下函数在 python 中不起作用 include
  • 将 Haskell 程序作为 C 源代码分发

    假设我有一个 Haskell 程序或库 我想让非 Haskell 人员 可能是 C 程序员 访问它 我可以使用 GHC 将其编译为 C 然后将其作为 C 源代码分发吗 如果可能的话 有人可以提供一个最小的例子吗 例如 Makefile 是否
  • 最好的积极维护的 Java XMPP 库? [关闭]

    Closed 这个问题不符合堆栈溢出指南 help closed questions 目前不接受答案 我见过几个 Java 的 XMPP 库 在过去几年中似乎很少有更新活动 当前最好的 XMPP 库是什么 支持 基本聊天 传输层安全 MUC
  • 间歇性 ODBC 连接失败

    我们正在开发一个内部 32 位应用程序 该应用程序连接到 SQL Server 测试环境为SQL Server 2008 R2 上线环境为SQL Server 2014 SP2 使用以下 ODBC 字符串建立与数据库的连接 Driver S
  • 使用 SciPy 最小化估计逆 Hessian 矩阵

    我正在使用 SciPy 的 最小化 函数来最小化函数 该函数返回最优值以及估计的雅可比矩阵和海森矩阵 如下 fun 675 09792378630596 hess inv lt 8x8 LbfgsInvHessProduct with dt
  • Jackson 为具有多态类型的一个字段定制反序列化器

    Update 我尝试在杰克逊源代码中进行调试并在方法中发现 deserialize JsonParser jp DeserializationContext ctxt of SettableBeanProperty java 当 的时候 v
  • 将带有回调的函数变成 Python 生成器?

    Scipy 最小化函数 仅用作示例 可以选择在每个步骤添加回调函数 所以我可以做类似的事情 def my callback x print x scipy optimize fmin func x0 callback my callback
  • Hibernate JPA:即使根本没有更改,更新查询(仅更新版本)也会被触发

    假设 我们有一个 User 一个用户可以有多个子级 现在 当我插入一个孩子时 我打电话user addChild 这样位于 JVM 中的用户对象就会被更新 尽管实际上用户的数据库记录没有任何变化 因为它是 OneToMany 当我检查SQL
  • 为什么用gcc和std=c99编译时找不到getaddrinfo

    我有以下我试图编译的代码 当我尝试使用 std c99 时 它失败并出现有关 struct addrinfo 类型的隐式声明 和 函数 getaddrinfo 的隐式声明 的警告 它适用于 std gnu99 include
  • 熊猫绘图,正值一种颜色,负值另一种颜色

    我有一个 pandas 数据框 在其中绘制 12 列中的两列 一列作为 x 轴 一列作为 y 轴 x 轴只是一个时间序列 y 轴的值是大约 5000 到 5000 之间的随机整数 有没有办法只使用这两列来制作散点图 其中 y 的正值是某种颜
  • 删除虚假逗号

    一位白痴客户正在生成 csv 文件 但其中一个字段 描述字段 有时有多余的逗号 是否有一个整洁的正则表达式来查找这些不良记录并用其他内容替换多余的逗号 SED 命令行就可以了 Example A B C This is a descript
  • 如何在 puppeteer 中获取所有 xhr 调用?

    我在用puppeteer加载网页 const browser await puppeteer launch headless true const page await browser newPage await page setReque
  • Jpa 事务 javax.persistence.RollbackException:事务标记为 rollbackOnly

    我有一个应用程序通过 jpa 对各种数据库表进行大量写入 这些写入之一可能会导致乐观锁异常 如果抛出一个 也没什么大不了的 我希望提交事务的其余部分 我通过以下方式查看了 Spring 事务的无回滚功能
  • Redis 中高效的索引类型操作

    我正在尝试在 Redis 中创建一组索引 用于执行 AND 操作 像这样 inx 头发颜色 金发 set key1 key2 key3 inx 眼睛颜色 蓝色 设置 key1 key2 我可以使用sinter找到所有金发蓝眼睛的钥匙 我有这
  • RSA_private_加密总是失败

    我正在学习在我的程序中使用 OpenSSL 库 在代码中 我生成一个私钥 并立即使用该密钥加密消息 但总是失败 请帮助我 private key RSA generate key RSA KEY LENGTH RSA 3 NULL NULL
  • 如何更改 SwitchCompat 的轨道颜色

    我尝试使用以下链接来更改 SwitchCompat 的颜色 如何更改 SwitchCompat 的颜色 https stackoverflow com questions 26714864 how to change the color o
  • 如果不存在图像则显示默认图像

    我在 Centos 5 上运行 Apache 我想实现重写规则 当用户尝试访问文件夹中的图像时 var site com html image products 该规则应该检查图像是否存在 如果不存在 我想要 var site com ht
  • 如何为 WinForms 应用程序创建 MSIX 包?

    我正在尝试转移到 MSIX 来安装我们的应用程序 该应用程序目前通过 ClickOnce 安装部署给我们的客户 如果有更新 则需要在启动时进行更新 它是一个 Net Framework 4 7 2 WinForms 应用程序 我有点不知道如
  • 如何使用 Kaminari (或 will_paginate)gem 对数组的哈希值进行分页

    我现在已经设法找到解决方法 现在 索引操作在调用页面之前有一个 订单 子句 然后按日期对餐食进行排序和分组 接下来是 hackey 位 total pages 和 pages 在视图中用于提供分页链接 因为内置帮助器不适用于 meals 返
  • 拥有“(a -> b) -> b”是否等同于拥有“a”?

    在纯函数式语言中 您可以对值执行的唯一操作就是对其应用函数 换句话说 如果你想用 type 的值做任何有趣的事情a你需要一个具有类型的函数 例如 f a gt b然后应用它 如果有人递给你 flip apply a与类型 a gt b gt