互递归高阶

Question

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



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

Answer 1

目前oneElse和twoElse的定义不相互递归。为了能够建立mutuality，我们必须oneElse利用twoElse，反之亦然。

不确定它是否会达到预期目的...一种方法是按照以下方式定义两个函数，显示 mutual recursion:

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

Answer 2

由于循环，你不能直接这样做； oneElse 的类型为 type of twoElse -> int list -> bool，twoElse 的类型为 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;

现在这两个函数的类型都是 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

互递归高阶

Mutual recursion higher order

functional-programming

sml