为什么这个 Haskell 程序中没有使用尾部调用优化?

2024-02-13

以下程序会破坏堆栈:

__find_first_occurrence :: (Eq b) => b -> [b] -> Int -> Int
__find_first_occurrence e [] i = -1
__find_first_occurrence e (x:xs) i
    | e == x = i
    | otherwise = __find_first_occurrence e xs (i + 1)

find_first_occurrence :: (Eq a) => a -> [a] -> Int
find_first_occurrence elem list =   
    __find_first_occurrence elem list 0

main = do
    let n = 1000000
    let idx = find_first_occurrence n [1..n]
    putStrLn (show idx)

失败与

堆栈空间溢出:当前大小 8388608 字节。使用`+RTS -Ksize -RTS' 来增加它。

但是,据我了解,可能的递归调用__find_first_occurrence是最后评估的东西__find_first_occurrence,因此尾调用优化应该是可能的。


使用了尾调用优化,但是(i+1)表达式会被重击,最后对它们求值会导致堆栈溢出。

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

为什么这个 Haskell 程序中没有使用尾部调用优化? 的相关文章

  • 持久 selectList 导致错误“无法将类型‘BaseBackend backend0’与‘SqlBackend’匹配”

    我遇到以下编译错误 Couldn t match type BaseBackend backend0 with SqlBackend arising from a use of runSqlite The type variable bac
  • 以下两个 lambda 函数的空间复杂度

    我正在阅读以下内容 https en wikibooks org wiki Haskell Graph reduction https en wikibooks org wiki Haskell Graph reduction 其内容如下
  • 递归方法比交互式方法慢 10 倍 [关闭]

    这个问题不太可能对任何未来的访客有帮助 它只与一个较小的地理区域 一个特定的时间点或一个非常狭窄的情况相关 通常不适用于全世界的互联网受众 为了帮助使这个问题更广泛地适用 访问帮助中心 help reopen questions 代码已尽可
  • 使用一次递归调用实现递归

    给定一个函数如下 f n f n 1 f n 3 f n 4 f 0 1 f 1 2 f 2 3 f 3 4 我知道使用递归来实现它 并在一个函数内进行三个递归调用 但我想在函数内仅使用一次递归调用来完成此操作 怎样才能做到呢 要实现使用
  • Haskell 中的尾递归字符串分割

    我正在考虑分割字符串的问题s在一个字符处c 这表示为 break c s 其中 Haskell 库定义break c 足够接近 br br s h t if c h then s else let h t br t in h h t 假设我
  • 有没有更好的方法将 UTC 时间转换为大纪元时间?

    我想将文件的修改时间设置为从 exif 数据获取的时间 为了从 exif 获取时间 我发现 Graphics Exif getTag Exif gt String gt IO Maybe String 要设置文件修改时间 我发现 Syste
  • 你能识别 Haskell 程序中的无限列表吗? [复制]

    这个问题在这里已经有答案了 可能的重复 如何判断列表是否是无限的 https stackoverflow com questions 7371730 how to tell if a list is infinite 在Haskell中 你
  • : 中缀运算符在 Haskell 中的作用是什么?

    我正在阅读Haskell 简要介绍 http www haskell org tutorial index html 这不是那么温和 并且它反复使用 操作符而不直接解释它的作用 那么 它到底有什么作用呢 是 前置 运算符 x xs 返回一个
  • 洪水填充优化:尝试使用队列

    我正在尝试创建一种填充方法 该方法采用用户指定的初始坐标 检查字符 然后根据需要更改它 这样做之后 它会检查相邻的方块并重复该过程 经过一番研究 我遇到了洪水填充算法并尝试了该算法 它可以工作 但无法满足我对 250 x 250 个字符的数
  • 我该如何实现这个折叠功能呢?

    给出了两种数据类型 颜色 和 植物 data Color Red Pink White Blue Purple Green Yellow deriving Show Eq data Plant Leaf Blossom Color Stal
  • Haskell 标准库是什么?

    GHC专用库可以称为标准库吗 或者只有 Haskell 2010 报告中的那些才算数 许多 GHC 库可以通过 Haskell 报告中的函数来实现 可能与 C 绑定相结合 但其他语言依赖于 GHC 特定的扩展 因为语言报告中定义的当前 Ha
  • 管道:多个流消费者

    我编写了一个程序来计算语料库中 NGram 的频率 我已经有一个函数 它消耗一串令牌并生成一个订单的 NGram ngram Monad m gt Int gt Conduit t m t trigrams ngram 3 countFre
  • 递归修剪对象中所有元素的更好方法?

    如果我有一个像这样的物体 const obj field subfield innerObj a asdasd asdas innerArr s ssad innerArrObj b adsad 我想出了这样的东西 const trimFi
  • 如何打乱列表?

    如何从一组数字 1 2 3 直到我击中x 我的计划是重新调整列表 1 2 3 并把它砍在x chopAt 3 2 3 1 2 3 chopAt 3 2 1 3 2 1 3 chopAt 3 3 1 2 3 chopAt chopAt x y
  • 归并排序中的递归:两次递归调用

    private void mergesort int low int high line 1 if low lt high line 2 int middle low high 2 line 3 mergesort low middle l
  • 类型级别集结合律的证明

    我试图证明类型级函数Union https hackage haskell org package type level sets 0 8 5 0 docs Data Type Set html t Union是关联的 但我不确定应该如何完
  • 来自 JSON 的 Angular 8 动态表单

    我正在尝试从 JSON 模式递归生成动态表单 但我正在努力解决找不到表单控件的问题 这是代码示例 我收到这个错误 错误错误 找不到名称为 createdAt 的控件 我尝试了不同的方法 但仍然存在问题 我知道我错过了一些东西 所以请帮忙 任
  • 迭代打印列表中的每个整数

    假设我有一个整数列表l 1 2 我想打印到stdout Doing print l产生 1 2 假设我想打印不带大括号的列表 map print l产生 No instance for Show IO arising from a use
  • 关于“没有绑定的类型签名”的错误

    我在 Haskell 中遇到 ASCII 问题 fromEnum Char gt Int toEnum Int gt Char offset Int offset fromEnum A fromEnum a toUpper Char gt
  • 如何在 javascript 正则表达式中匹配平衡分隔符?

    我原以为这个问题是不可能的 据我所知 Javascript 的正则表达式既没有递归插值 也没有漂亮的 NET 平衡组功能 但问题就在那里 如问题 12 所示正则表达式 alf nu http regex alf nu 匹配平衡对 lt an

随机推荐