时间戳

首页 > 解决方案 > 相互递归高阶

functional-programming - 相互递归高阶

问题描述

有没有办法使用相互递归来创建使用现有状态的状态机。



fun oneElse f xs =
    case xs of
    1::xs' => f xs'
      | [] => true
      | _ => false;
         
fun twoElse xs =
    case xs of
    2::xs' => oneElse twoElse xs'
      | []  => false
      | _ => false

val oneTwo = oneElse twoElse [1,2,1,2];

这是我到目前为止所拥有的，但我想要的是高阶函数采用这些通用（一个不知道下一个）状态的地方。


fun oneElse f xs  = ...
         
fun twoElse f xs = ...


val oneTwo = oneElse (twoElse (oneElse headache) ) xs

标签： functional-programmingsml

解决方案

由于循环性，您不能直接执行此操作；oneElse会有 typetype of twoElse -> int list -> bool和twoElsetype type of oneElse -> int list -> bool，所以 的类型oneElse会是(type of oneElse -> int list -> bool) -> int list -> bool，它会无限扩展。

但是，您可以使用标准解决方案来解决这个问题 - 添加一个间接级别。

datatype Wrap = Wrap of (Wrap -> int list -> bool)

fun oneElse (Wrap f) (1::xs) = f (Wrap oneElse) xs
  | oneElse _ [] = true
  | oneElse _ _ = false


fun twoElse (Wrap f) (2::xs) = f (Wrap twoElse) xs
  | twoElse _ _ = false;

现在这两个函数都有 type Wrap -> int list -> bool，可以解决。
您只需要在传递函数时包装它们，然后在应用它们之前解包。

测试：

- oneElse (Wrap twoElse) [1,2,1,2];
val it = true : bool

- oneElse (Wrap twoElse) [1,2,1];
val it = false : bool

推荐阅读