如何借助mutual recursion与高阶函数基于现有状态实现状态机

互递归解耦实现状态机方案 #

可以实现，你需要的状态解耦效果可以通过*延续传递风格（CPS）*改造高阶状态函数完成，每个状态仅处理自身匹配逻辑，下一跳状态完全通过参数传入，无需提前感知其他状态的存在。

核心实现代码 #

(* 状态1：匹配当前元素为1，匹配成功后调用传入的下一跳状态f处理剩余输入 *)
fun oneElse f xs =
    case xs of
        1::xs' => f xs'
      | [] => true
      | _ => false;

(* 状态2：匹配当前元素为2，匹配成功后调用传入的下一跳状态f处理剩余输入 *)
fun twoElse f xs =
    case xs of
        2::xs' => f xs'
      | [] => false
      | _ => false;

(* 终止状态：对应你示例中的headache占位，作为状态链的最终结束判断 *)
fun endState xs = null xs;

固定长度状态链调用（对应你期望的写法） #

(* 匹配序列规则：1 → 2 → 1 → 2 → 结束 *)
val oneTwo = oneElse (twoElse (oneElse (twoElse endState))) [1,2,1,2];
(* 执行结果为 true *)

循环互递归实现无限交替状态机 #

如果需要实现1、2无限交替的循环状态机，可以通过递归绑定构造循环的状态引用：

val rec oneState = fn xs => oneElse twoState xs
and twoState = fn xs => twoElse oneState xs;

(* 测试用例 *)
val test1 = oneState [1,2,1,2,1,2]; (* 匹配成功，返回true *)
val test2 = oneState [1,2,3]; (* 匹配失败，返回false *)

方案优势 #

所有状态逻辑完全独立，调整跳转规则时不需要修改状态本身的代码，只需要调整传入的下一跳参数即可，比如要修改为1之后跳转3状态，直接写oneElse threeState即可，无需改动oneElse的内部实现。

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