拥有“(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”? 的相关文章

  • 如何给Servant中的所有端点添加前缀?

    我在 Haskell 仆人中有一个 hello world 应用程序 这是其中的一部分 type API my items gt Get JSON MyItem lt gt my items gt Capture id Int gt Get
  • 双共体的方法是什么?

    在思考建议哪些更有用的标准课程时到这个 https stackoverflow com a 40833245 745903 class Coordinate c where createCoordinate x gt y gt c x y
  • Haskell:去掉 liftM2 中的括号

    如何去掉标有的括号 而不引入新名称 如果能分成多行就更好了 liftM2 somefunc arg1 get arg2 somefunc arg3 get arg3 您可以使用以下方法删除最后一个 但另一个显然不能在不引入新名称的情况下被删
  • 一个目录中的多个 Haskell cabal-packages

    在一个目录中包含多个 cabal 软件包的推荐方法是什么 Why 我有一个包含许多可分离模块的旧项目 由于最初它们只形成一个程序 因此将它们放在同一目录中以便于编译非常方便 而且现在仍然如此 Options 只是忍受并将所有内容 包括保存内
  • 在没有互联网连接的情况下使用 cabal 安装 Haskell 软件包

    我有一台根本无法访问互联网的机器 我使用通过随身碟从另一台机器获得的安装程序在其上安装了 Haskell 平台 现在我想安装这个包repa在我的家用机器上 无法访问互联网 我该怎么做呢 我的家用计算机运行的是 Linux Debian 我的
  • 带参数的 Python 列表过滤

    python中有没有一种方法可以在列表上调用过滤器 其中过滤函数在调用期间绑定了许多参数 例如有没有办法做这样的事情 gt gt def foo a b c return a lt b and b lt c gt gt myList 1 2
  • 如何在 Ocaml 中表示一个简单的有限状态机?

    我用 C 和 Java 编写过一些状态机 但从未用过像 Ocaml 这样的函数式语言 问题是我不知道我是否可以从对象语言版本中调整代码 因为在 Ocaml 中记录和变体比类更强大 所以 我需要一个事件驱动的有限状态机 像 UML 中的分层结
  • 如何使用 alex/haskell 执行 python 风格的缩进/缩进标记?

    我正在用 Haskell 为 Alex 中的一种小语言编写一个词法分析器 该语言被指定为具有 python 式的显着缩进 只要缩进级别发生变化 就会发出 INDENT 标记或 DEDENT 标记 在像 C 这样的传统命令式语言中 您将在词法
  • Haskell GHC:具有 N 个构造函数的模式匹配的时间复杂度是多少?

    假设我们有以下 Haskell data T T0 T1 T2 TN toInt T gt Int toInt t case t of T0 gt 0 T1 gt 1 T2 gt 2 TN gt N 这里使用什么算法来执行模式匹配 我看到两
  • 结构上强制的自由替代,没有左派分配性

    有一个不错的免费替代品 http hackage haskell org package free 4 12 4 docs Control Alternative Free html在伟大的free包 它将函子提升到左分配替代方案 也就是说
  • 在 JavaScript 中将函数映射到生成器上

    我有一个名为generateNumbers在 JavaScript 和另一个生成器中generateLargerNumbers它采用由生成的每个值generateNumbers并应用一个函数addOne对其而言 如下 function ad
  • 镜头中的观看和使用有什么区别?

    有什么区别 view MonadReader s m gt Getting a s a gt m a and use MonadState s m gt Getting a s a gt m a in 控制镜头吸气剂 https hacka
  • 当单态限制打开*时,如何解决歧义问题?

    因此 在学习 Haskell 时 我很快就遇到了可怕的单态限制 在 ghci 中 Prelude gt let f print show Prelude gt f 5
  • 您将如何在 F# 中解决这个问题? (高频传感器数据)

    我是一名机械工程研究生 我的导师刚刚要求我为我们的一个传感器项目编写一个数据可视化实用程序 由于现在是夏天 他希望我能从中获得一些乐趣 我认为这将是学习一门擅长科学计算的语言的好时机 所以我直接开始学习 F 由于我是函数式编程范例的新手 因
  • 如何在 blaze-html 中渲染 blaze-svg 标记

    我想将使用 blaze svg 生成的 svg 图直接包含在使用 blaze html 生成的 html 中 两者都基于 blaze markup 所以我希望它很容易 diagram1 Svg diagram1 try1 Html try1
  • Haskell,范围缩小到无步骤[重复]

    这个问题在这里已经有答案了 为什么在 Haskell 中工作范围不能降低到没有步骤 7 1 gt 但只工作这个 7 6 1 gt 7 6 5 4 3 2 1 Haskell 无法知道您想要执行 1 除非您给出提示 在某些情况下 您可能需要一
  • 算法 - 如何有效删除列表中的重复元素?

    有一个list L 它包含以下元素任意类型each 如何有效删除此类列表中的所有重复元素 必须保留订单 只需要一个算法 因此不允许导入任何外部库 相关问题 在Python中 从列表中删除重复项以使所有元素都是唯一的最快算法是什么在维持秩序的
  • 如何、为什么以及何时使用“.Internal”模块模式?

    我在上面看到了几个包裹hackage http hackage haskell org packages archive pkg list html其中包含模块名称 Internal作为他们的姓氏组成部分 例如Data ByteString
  • 谁能解释一下 GHC 对 IO 的定义吗?

    标题非常自我描述 但有一个部分引起了我的注意 newtype IO a IO State RealWorld gt State RealWorld a 剥离newtype 我们得到 State RealWorld gt State Real
  • 如何将只缓存某些内容的字段添加到ADT?

    我经常需要向 ADT 添加字段 仅记住一些冗余信息 但我还没有完全弄清楚如何又好又高效地做到这一点 说明问题的最好方法是举个例子 假设我们正在使用无类型 lambda 项 type VSym String data Lambda Var V

随机推荐

  • 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