这个对自身单位的列表理解是如何工作的?

2024-05-17

在 #haskell IRC 频道中有人问

是否有一种简洁的方法来定义一个列表,其中第 n 个条目是之前所有条目的平方和?

我认为这听起来像一个有趣的谜题,递归定义无限列表是我真正需要练习的事情之一。所以我启动了 GHCi 并开始尝试递归定义。最终,我设法到达

λ> let xs = 1 : [sum (map (^2) ys) | ys <- inits xs, not (null ys)]

这似乎产生了正确的结果:

λ> take 9 xs
[1,1,2,6,42,1806,3263442,10650056950806,113423713055421844361000442]

不幸的是,我不知道我写的代码是如何工作的。是否可以解释以中级 Haskell 用户可以理解的方式执行此代码时会发生什么?


这归结为惰性评估。让我们采用 augustss 的定义,因为它稍微简单一些,但称之为big代替xs,因为该标识符在实用程序中常用。

Haskell 仅在需要时才评估代码。如果不需要的话,那里有一个存根,基本上是一个指向函数闭包的指针,可以在需要时计算该值。

假设我想评估big !! 4。的定义!!是这样的:

[] !! _ = error "Prelude.(!!): index too large"
(x:_) !! 0 = x
(_:xs) !! n = xs !! (n-1)

的定义big is

big = 1 : [sum (map (^2) ys) | ys <- tail (inits big)]

因此,在评估索引访问时,首先要做的就是必须选择正确的函数变体。列表数据类型有两个构造函数,[] and first : rest。通话内容是big !! 4,以及第一个分支!!只是检查列表是否是[]。由于列表明确以1 : stub1,答案是否定的,并且该分支被跳过。

第二个分支想知道是否first : rest选择了形式。答案是肯定的,与first being 1 and rest这么大的理解力(stub1),其值无关紧要。但第二个论点不是0,所以这个分支也被跳过。

第三个分支也与first : last,但接受第二个参数的任何内容,因此它适用。它忽略了first, binds xs未评估的理解stub1, and n to 4。然后它递归地调用自身,第一个参数是理解,第二个参数是3。 (从技术上来说,这就是(4-1)尚未评估,但作为简化,我们假设它是。)

递归调用必须再次评估其分支。第一个分支检查第一个参数是否为空。由于到目前为止的参数是一个未评估的存根,因此需要对其进行评估。但仅够判断分支是否为空。那么让我们开始评估理解力:

stub1 = [sum (map (^2) ys) | ys <- tail (inits big)]

我们首先需要的是ys。它设置为tail (inits big). tail很简单:

tail [] = []
tail (_:xs) = xs

inits实现起来相当复杂,但重要的是它会惰性地生成结果列表,即如果你给它(x:unevaluated),它会生成[] and [x]在评估列表的其余部分之前。换句话说,如果你不超越这些,它就永远不会评估其余的。

所以,到目前为止big已知是(1 : stub1), so inits回报[] : stub2. tail与此匹配,选择其第二个分支,然后返回stub2. stub2是单位列表big在无所不在的空列表之后,它还没有生成。

然后列表理解尝试给出ys第一个元素的值stub2,所以必须对其进行评估。第二个结果是inits仍然已知,它是[1]. ys得到那个值。那么此时,big已知是1 : stub3 : stub4, where stub3 = sum (map (^2) [1]) and stub4是第一次迭代后的列表理解。

Since big现在正在进一步评估,所以stub1。现在已知的是stub3 : stub4,我们终于可以前进了!!。第一个分支不适用,因为列表不为空。第二个分支不适用,因为3 /= 0。第三分支适用,具有约束力xs to stub4 and n to 3。递归调用是stub4 !! 2.

我们需要评估一下stub4。这意味着我们进入理解的下一个迭代。我们需要第三个元素inits big. Since big目前已知是1 : stub3 : stub4,第三个元素无需进一步评估即可计算为[1, stub3]. ys与该值绑定,并且stub4评估为stub5 : stub6, where stub5 = sum (map (^2) [1, stub3]) and stub6是前两次迭代后的理解。和stub4评估后,我们现在知道big = 1 : stub3 : stub5 : stub6.

So stub4仍然与第一个分支不匹配!!(什么都不会,因为我们正在处理一个无限列表)。2仍然与第二个分支不匹配。我们有另一个递归调用,然后是另一个,遵循与到目前为止相同的模式。当索引最终达到 0 时,我们有:

big = 1 : stub3 : stub5 : stub7 : stub9 : stub10
stub3 = sum (map (^2) [1])
stub5 = sum (map (^2) [1, stub3])
stub7 = sum (map (^2) [1, stub3, stub5])
stub9 = sum (map (^2) [1, stub3, stub5, stub7])
stub10 = whatever remains of the list comprehension

我们当前的电话是(stub9 : stub10) !! 0,最终匹配第二个分支。x一定会stub9然后回来了。

只有现在,如果您真正尝试打印或以其他方式处理x,所有这些存根最终都会评估为实际数字。

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

这个对自身单位的列表理解是如何工作的? 的相关文章

  • F# 中的递归对象?

    这段 F 代码 let rec reformat new EventHandler fun gt b TextChanged RemoveHandler reformat b gt ScrollParser rewrite contents
  • Python:打印自定义异常时超出最大递归深度

    下面的代码抛出RuntimeError maximum recursion depth exceeded while getting the str of an object 我可以用两种不同的方式解决无限递归 但我不明白为什么每个修复都有
  • 计算/获取分层数据的“级别”

    好吧 我真的不知道这是否是正确的标题 但我不知道如何称呼它 我的问题是关于我的作业 我现在已经工作了几个小时 主题是 函数式数据结构 我有点陷入困境 我不知道如何继续 所以我需要编写一个具有以下签名的函数 data Heap e t Hea
  • 算法 - 如何有效删除列表中的重复元素?

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

    我想知道怎么写f x zip x tail x 点免费 所以我使用了pointfree程序 结果是f ap zip tail ap作为 Control Monad 的函数 我不明白点自由定义是如何工作的 如果我能从类型的角度去理解的话 希望
  • 如何向 Scotty 中间件添加基本身份验证?

    我目前正在制作 Scotty API 但找不到任何 basicAuth 实现的示例 Wai Middleware HttpAuth 具体来说 我想将基本身份验证标头 用户 通行证 添加到我的某些端点 即以 admin 开头的端点 我已经设置
  • java正则表达式查找第一个和最后一个字符

    我正在编写一个程序来递归地确定字符串是否为回文 我决定尝试使用正则表达式 但我在理解语法时遇到了一些困难 我需要做的是比较第一个和最后一个字符 看看它们是否相同 我该怎么做呢 Thanks 编辑 我发现这很有帮助 AirSource Ltd
  • 如何、为什么以及何时使用“.Internal”模块模式?

    我在上面看到了几个包裹hackage http hackage haskell org packages archive pkg list html其中包含模块名称 Internal作为他们的姓氏组成部分 例如Data ByteString
  • 'lens' 的阴谋集团依赖性解析失败

    我刚刚做了一个阴谋更新并尝试从 hackage 安装 lens 这给了我以下错误 cabal install j lens Resolving dependencies Configuring dlist 0 7 0 1
  • 是否有一个基于对象身份的、线程安全的记忆库?

    我知道记忆化似乎是堆栈溢出的 haskell 标签上的一个长期话题 但我think以前没有人问过这个问题 我知道 Haskell 有几个不同的 现成 记忆库 memo combinators 和 memotrie 包 利用涉及惰性无限数据结
  • 如何找到仅是 2、3 和 5 的幂的倍数的所有数字的列表? [复制]

    这个问题在这里已经有答案了 I am trying to generate a list of all multiples which can be represented by the form where a b and c are w
  • Haskell 中的相互递归求值器

    Update 我已经添加一个答案 https stackoverflow com questions 3524485 mutually recursive evaluator in haskell 4504200 4504200这描述了我的
  • 对元组列表进行排序的函数 - Haskell

    抱歉 这个简单的问题只是我对 haskell 非常陌生 我正在尝试编写一个函数 order 它将对另一个函数 Frequency 生成的元组列表进行排序 频率计算列表中不同元素的数量 a给出一个这样的结果 比如 gt 频率 aabbbccc
  • 反应性香蕉时间延迟

    我已经查阅了文档反应香蕉 http hackage haskell org package reactive banana 而且我找不到指定明确时间延迟的方法 举例来说 我想采取Event t a并将其所有发生的事件移至未来 1 秒 或获取
  • 带有查询参数的渲染 url

    无法找到简单问题的解决方案 答案应该是显而易见的 如何在 hamlet 模板中使用查询参数渲染 url I e ItemsR 将生成http localhost 3000 items我如何生成类似的东西http localhost 3000
  • Haskell 和 Idris 之间的区别:类型宇宙中运行时/编译时的反映

    因此 在 Idris 中 编写以下内容是完全有效的 item b Bool gt if b then Nat else List Nat item True 42 item False 1 2 3 cf https www youtube
  • Haskell 排列库函数 - 请澄清一下?

    这是代码permutationsHaskell 中的函数Data List module permutations a gt a permutations xs0 xs0 perms xs0 where perms perms t ts i
  • 地图不是接受一个函数而列表返回一个列表吗?

    map2 List a gt b gt c gt a gt b gt c map2 List f map2 List f a as bs map f a bs map2 List f as bs 这是我的讲座中的一个示例 它尝试将二元函数应
  • 如何避免编写这种类型的 Haskell 样板代码

    我经常遇到这种情况 这很烦人 假设我有一个 sum 类型 它可以保存一个实例x或一堆其他无关的事情x data Foo x X x Y Int Z String other constructors not involving x 要声明
  • 为什么 Haskell 中的点是从右向左排列的?

    如果我们有两个函数 f and g 然后在哈斯克尔h f g相当于h x f g x IE 这些函数从右到左应用于输入 有什么根本原因可以解释为什么它是从右到左 而不是从左到右吗 IE 他们为什么不做h f g相当于h x g f x 反而

随机推荐

  • 在 .Net 应用程序中使用 Active Directory Web 服务

    我正在尝试构建一个 Net 应用程序来询问 Active Directory 编辑 我需要使用 Web 服务来执行此操作 因为我将使用需要使用 Web 服务的第三方工作流工具从 Sharepoint 工作流与 AD 进行通信 根据我的研究
  • 如何定义 nullptr 以支持 C++03 和 C++11? [复制]

    这个问题在这里已经有答案了 可能的重复 将 nullptr 向后移植 到 C C 0x 之前的程序 https stackoverflow com questions 8747005 backporting nullptr to c pre
  • 我可以在 firebase android 中加载另一个用户个人资料图像吗?

    如果我有其他用户的电子邮件但我以其他用户身份登录 我是否可以加载其他用户的个人资料图像 如果您使用 Firebase Storage 那么从技术上讲是的 它只是一个您可以从中检索任何文件的文件系统 如果不伪造您的应用程序 获取 api 密钥
  • 文件夹.文件的相对路径

    我有一个 Excel 文件 在同一文件夹中还有一个包含我想要包含的 CSV 文件的文件夹 使用 来自文件夹 查询 第一步将给出以下查询 Folder Files D OneDrive Documents Health Concept2 现在
  • 获取所有查询字符串对并初始化字典的最佳方法

    我想将所有键 值对存储在我的查询字符串中 www example com a 2 b 3 c 34 进入字典 有没有一种快速的方法可以做到这一点 而无需手动循环所有项目 Try HttpUtility ParseQueryString 它给
  • 应用程序实例是否始终在任何活动之前创建?

    在 Android 中 您可以通过扩展 Application 类并在 Manifest 中声明名称来提供您自己的 Application 类实现 我的问题是 这个实现是否总是在初始活动之前创建 或者活动可以在应用程序实例有时间创建之前启动
  • Logrotate - nginx 日志不在 docker 容器内旋转

    我有一个运行 nginx 的 docker 容器 它正在将日志写入 var log nginxLogrotate 安装在 docker 容器中 并且 nginx 的 logrotate 配置文件已正确设置 尽管如此 logrotate 仍不
  • SVN运行上下文错误:现有连接被远程主机强制关闭

    我在 Debian Wheezy 构建服务器上创建了一个 SVN 存储库 如下所示本教程 http www networkworld com article 2224093 opensource subnet use subversion
  • jquery 调整窗口大小以适合内容

    我有一个简单的弹出窗口显示300x300px图片 我将窗口的大小设置为350x350px 但根据浏览器的不同 我要么得到滚动条 要么得到额外的空白 是否有一些 jQuery 函数可以调整浏览器窗口的大小以适应内容 而无需任何滚动条或空白 无
  • 与 OLE 服务器或 ActiveX 控件通信

    MS Access 2010 Win 7 常规形式我没有故意放置任何 ActiveX 或 OLE 东西 甚至不确定它们是什么 但无论如何 每当我在特定形式的代码中放入某些内容时 它都会说 您作为事件属性设置输入的表达式 XXXXX 产生了以
  • Angular 2将数组传递给路由器queryString

    我想传递一个数组ids 1 2 3 像这样的路由器查询字符串 http some url ids 1 ids 2 ids 3 但是当我尝试使用 const queryParams ids 1 2 3 this router navigate
  • 使用Spring批处理从HDFS读取文件

    我必须编写一个 Spring 批处理 它将从 HDFS 读取文件并更新 MySQL DB 中的数据 HDFS 中的源文件包含一些 CSV 格式的报告数据 有人能给我举一个从 HDFS 读取文件的例子吗 Thanks The FlatFile
  • 如何将 WPF UIElement 从可视化树移动到固定页面?

    我的 MVVM 应用程序使用屏幕上的视觉对象将屏幕内容渲染到打印文档 我的视图有一个ContentControl使用DataTemplate资源来确定要显示的内容 但是当我尝试将该内容添加到FixedPage对象 我得到一个Argument
  • 如何在c#中生成8字节GUID值? [复制]

    这个问题在这里已经有答案了 可能的重复 如何从 GUID 生成 8 字节唯一 ID https stackoverflow com questions 5678177 how to generate 8 bytes unique id fr
  • flutter:动画过渡到命名路线

    当我使用Navigator pushNamed context someRoute 有一个最小的动画 从屏幕底部沿着新路线滑动 在 Android 上 在 iOS 上可能看起来不同 如何向此过渡添加自定义动画 I found 本文 http
  • Firebug 控制台窗口范围。为什么“这个”不总是一样的?

    Firebug 控制台范围 为什么 这个 不总是一样的 难道不应该一直是 窗口 吗 的价值this控制台中的值将与this在当前正在执行的代码中 考虑 function outer this is window var x n 12 var
  • 用颤动画布在形状上切一个洞

    如何使用颤动画布在形状上 切一个洞 我有一组相当复杂的形状 看起来像现实世界的物体 该物体上有一个圆角矩形形状的孔 我真的很想从形状中减去 RRect 但我找不到任何有关如何执行此操作的信息 canvas clipRRect myRRect
  • scala 返回列表中的第一个 Some

    我有一个清单l List T1 目前我正在执行以下操作 myfun T1 gt Option T2 val x Option T2 l map myfun l flatten find gt true The myfun函数返回 None
  • php - 我应该加密电子邮件地址吗?

    当用户注册时 我应该将他们的电子邮件按原样存储在数据库中还是对其进行哈希处理 我希望稍后能够解密 那么我应该使用 md5 吗 谢谢你 No md5 is 单向哈希函数 http en wikipedia org wiki Cryptogra
  • 这个对自身单位的列表理解是如何工作的?

    在 haskell IRC 频道中有人问 是否有一种简洁的方法来定义一个列表 其中第 n 个条目是之前所有条目的平方和 我认为这听起来像一个有趣的谜题 递归定义无限列表是我真正需要练习的事情之一 所以我启动了 GHCi 并开始尝试递归定义