State与CPS Monad尾递归对比及Haskell解析器效率优化咨询

问题1：三种实现哪种内存效率最高？ #

三种实现都需要构造与输入'a'数量等长的结果列表，这部分是不可避免的O(n)堆开销，仅对比额外运行时开销：

• 严格State Monad版本额外开销最低，内存效率最高：它的Core已经优化掉了所有不必要的装箱元组分配，直接操作拆箱元组传递结果，仅有的额外开销是非尾递归带来的线性栈占用，在输入长度未触发栈溢出的场景下表现最优。
• CPS版本额外开销次之：虽然是尾递归没有栈溢出风险，但每递归一步都会在堆上分配一个新的续体闭包，产生线性的额外堆开销，仅适合处理超长输入避免栈崩溃的场景。
• 朴素递归版本内存效率最低：不仅有和严格State版本一样的线性栈占用，Core中还保留了不必要的装箱元组分配步骤，额外堆开销也更高，长输入下最先触发栈溢出。

问题2：如何通过GHC Core输出快速判断代码是否符合尾递归优化要求？ #

你只需要查看被Rec { ... end Rec }包裹的递归函数定义，检查递归调用的位置即可：

• 若递归调用是分支的最终返回值（整个分支的表达式就是递归调用本身，外层没有case、构造器、其他函数包裹），就符合尾递归优化要求，GHC会将其编译为迭代循环，无栈开销。比如CPS版本匹配到'a'的分支，直接返回parser_cps_parser_cps' rest_a5Sa (...)，就是典型的尾递归。
• 若递归调用出现在case的 scrutinee位置（比如朴素版本和严格State版本里的case $wparser_xxx rest of ...）、作为构造器参数、作为其他函数的参数，就说明递归调用返回后还要做额外处理，不属于尾递归，无法享受尾递归优化，会产生线性栈开销。

内容的提问来源于stack exchange，提问作者Qqwy