CODEWITHSUNDEEP
functional-programmingsml
Just_Alex
Just_Alex

Reputation: 558

Mutual recursion higher order

Is there a way to use mutual recursion to create a state machine using existing states.



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];

This is what I have so far, but what I would like is where the higher order function takes these generic (one doesn't know about the next) states.


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


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

Upvotes: 0

Views: 83

Answers (2)

molbdnilo
molbdnilo

Reputation: 66371

You can't do this straightforwardly due to the circularity; oneElse would have the type type of twoElse -> int list -> bool, and twoElse the type type of oneElse -> int list -> bool, so the type of oneElse would be (type of oneElse -> int list -> bool) -> int list -> bool, which expands infinitely.

However, you can solve this using The Standard Solution - add a level of indirection.

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;

Now both functions have the type Wrap -> int list -> bool, which works out.
You just need to wrap the functions when passing them, and unwrap before applying them.

Test:

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

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

Upvotes: 1

Nalin Ranjan
Nalin Ranjan

Reputation: 1782

Currently the definition of oneElse and twoElse are not mutually recursive. And to be able to establish mutuality we must have oneElse making use of twoElse and vice-versa.

Unsure of whether it will achieve what is intended or not... one way would be to define both functions following way, exhibiting 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;

Upvotes: 0

Related Questions