Mutual recursion higher order

Question

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

I would start with writing down the types of these functions and see where that goes. — molbdnilo
– molbdnilo, Commented Sep 27, 2021 at 10:32

molbdnilo · Accepted Answer · 2021-09-27 13:14:32Z

1

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

edited Sep 27, 2021 at 13:14

answered Sep 27, 2021 at 11:33

molbdnilo

67.1k3 gold badges46 silver badges90 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Nalin Ranjan · Accepted Answer · 2021-09-27 06:46:26Z

0

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;

answered Sep 27, 2021 at 6:46

Nalin Ranjan

1,8022 gold badges11 silver badges10 bronze badges

Collectives™ on Stack Overflow

Mutual recursion higher order

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related