gpt4 book ai didi

f# - 计算表达式中的递归函数

转载 作者:行者123 更新时间:2023-12-04 17:58:47 27 4
gpt4 key购买 nike

先介绍一下背景。我目前正在学习一些关于 monadic 解析器组合器的东西。当我尝试从 this paper 传输“chainl1”函数时(第 16-17 页),我想出了这个解决方案:

let chainl1 p op = parser {
let! x = p
let rec chainl1' (acc : 'a) : Parser<'a> =
let p' = parser {
let! f = op
let! y = p
return! chainl1' (f acc y)
}
p' <|> succeed acc
return! chainl1' x
}

我用一些大的输入测试了这个函数并得到了一个 StackOverflowException。现在我想知道,是否可以重写一个递归函数,它使用一些计算表达式,以某种方式使用尾递归?

当我扩展计算表达式时,我看不出它通常是如何可能的。
let chainl1 p op =
let b = parser
b.Bind(p, (fun x ->
let rec chainl1' (acc : 'a) : Parser<'a> =
let p' =
let b = parser
b.Bind(op, (fun f ->
b.Bind(p, (fun y ->
b.ReturnFrom(chainl1' (f acc y))))))
p' <|> succeed acc
b.ReturnFrom(chainl1' x)))

最佳答案

在您的代码中,以下函数不是尾递归的,因为 - 在每次迭代中 - 它在 p' 之间做出选择或 succeed :

// Renamed a few symbols to avoid breaking SO code formatter
let rec chainl1Util (acc : 'a) : Parser<'a> =
let pOp = parser {
let! f = op
let! y = p
return! chainl1Util (f acc y) }
// This is done 'after' the call using 'return!', which means
// that the 'cahinl1Util' function isn't really tail-recursive!
pOp <|> succeed acc

根据您对解析器组合器的实现,以下重写可能有效(我不是这里的专家,但可能值得尝试一下):
let rec chainl1Util (acc : 'a) : Parser<'a> = 
// Succeeds always returning the accumulated value (?)
let pSuc = parser {
let! r = succeed acc
return Choice1Of2(r) }
// Parses the next operator (if it is available)
let pOp = parser {
let! f = op
return Choice2Of2(f) }

// The main parsing code is tail-recursive now...
parser {
// We can continue using one of the previous two options
let! cont = pOp <|> pSuc
match cont with
// In case of 'succeed acc', we call this branch and finish...
| Choice1Of2(r) -> return r
// In case of 'op', we need to read the next sub-expression..
| Choice2Of2(f) ->
let! y = p
// ..and then continue (this is tail-call now, because there are
// no operations left - e.g. this isn't used as a parameter to <|>)
return! chainl1Util (f acc y) }

一般来说,在计算表达式中编写尾递归函数的模式是有效的。这样的事情会起作用(对于以允许尾递归的方式实现的计算表达式):
let rec foo(arg) = id { 
// some computation here
return! foo(expr) }

如您所见,新版本与此模式匹配,但原始版本不匹配。

关于f# - 计算表达式中的递归函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3141669/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com