F#中用Continuation编程避免堆栈溢出
2023-03-14 22:59:49 时间
当我接触的F#编程越多,我用到递归的可能性就越大,也正是因为这样,我时常会遇到堆栈溢出的问题,要想避免堆栈溢出问题,Continuation Style Program(CSP)是唯一的方法。以下我们列出普通的递归和CSP的版本代码进行对比,在这里,关键的一点,该方法不会返回,因此它不会在调用的堆栈上创建元素,同时,由于会延迟计算Continuation方法,它不需要被保存在栈元素中:
- module FunctionReturnModule =
- let l = [1..1000000]
- let rec sum l =
- match l with
- | [] -> 0
- | h::t -> h + sum t
- sum l
- module CPSModule =
- let l = [1..1000000]
- let rec sum l cont =
- match l with
- | [] -> cont 0
- | h::t ->
- let afterSum v =
- cont (h+v)
- sum t afterSum
- sum l id
好吧,接下来的问题是如何从普通递归的方法得到CSP的递归版本呢?以下是我遵循的步骤,记住:其中一些中间代码并不能通过编译。
首先看看我们原始的递归代码:
第一步:
- module FunctionReturnModule =
- let l = [1..1000000]
- let rec sum l =
- match l with
- | [] -> 0
- | h::t ->
- let r = sum t
- h + r
- sum l
第二步:处理递归函数中的sum,将cont移动到afterSum中,afterSum方法获得到参数v并将它传递给cont(h+v):
- module CPSModule =
- let l = [1..1000000]
- let rec sum l cont =
- match l with
- | [] -> cont 0
- | h::t ->
- let afterSum v =
- cont (h+v)
- sum t afterSum
- sum l id
那么,接下来让我们使用相同的方法来遍历树,下面先列出树的定义:
- type NodeType = int
- type BinaryTree =
- | Nil
- | Node of NodeType * BinaryTree * BinaryTree
最终的结果如下:
- module TreeModule =
- let rec sum tree =
- match tree with
- | Nil -> 0
- | Node(v, l, r) ->
- let sumL = sum l
- let sumR = sum r
- v + sumL + sumR
- sum deepTree
- module TreeCSPModule =
- let rec sum tree cont =
- match tree with
- | Nil -> cont 0
- | Node(v, l, r) ->
- let afterLeft lValue =
- let afterRight rValue =
- cont (v+lValue+rValue)
- sum r afterRight
- sum l afterLeft
- sum deepTree id
开始使用相同的步骤将它转换成CSP方式:
首先切入Continuation函数:
- module TreeModule =
- let rec sum tree cont =
- match tree with
- | Nil -> 0
- | Node(v, l, r) ->
- let sumL = sum l
- let sumR = sum r
- cont (v + sumL + sumR)
- sum deepTree
第一步:处理sumR,将cont方法移动到afterRight中并将它传给sum r:
- module TreeModule =
- let rec sum tree cont =
- match tree with
- | Nil -> 0
- | Node(v, l, r) ->
- let sumL = sum l
- // let sumR = sum r
- let afterRight rValue =
- cont (v + sumL + rValue)
- sum r afterRight
- sum deepTree
第二步:处理sumL:
- module TreeModule =
- let rec sum tree cont =
- match tree with
- | Nil -> 0
- | Node(v, l, r) ->
- //let sumL = sum l
- let afterLeft lValue =
- let afterRight rValue =
- cont (v + lValue + rValue)
- sum r afterRight
- sum l afterLeft
- sum deepTree
结束了,接下来让我们用下面的代码进行测试吧:
- let tree n =
- let mutable subTree = Node(1, Nil, Nil)
- for i=0 to n do
- subTree <- Node(1, subTree, Nil)
- subTree
- let deepTree = tree 1000000
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的