Tail-recursive programs in F#

Question

Hi I am trying to do this exercise but can't quite figure it out. I am given the following code in F#

type A<’a> = | D of ’a * bool
             | E of A<’a> * A<’a>

let rec g acc x = match x with
             | E(y,z) -> g (g acc z) y
             | D(a,true) -> a::acc
             | _ -> acc;;

let h x = g [] x;;

The exercise is now to argue if g is a tail-recursive function or not and to provide declarations of continuation-based, tail-recursive variants of both g and h. Hope someone can help!

score 0 · Answer 1 · answered May 23 '20 at 20:24

g is not tail recursive since it first needs to resolve the internal g call within the outer g, basically using the stack until the internal call is resolved.

Applying CPS this could be rewritten as

let rec g acc x cont = 
  match x with
    | E(y,z) -> g acc z (fun acc->g acc y id)
    | D(a,true) -> a::acc |> cont
    | _ -> acc |> cont

and called like

let h x = g [] x id

Continuations are passing as a parameter of the function what next you want to resolve. For example in the case of nodes type E, we solve z and then ask to solve as a continuation y. The continuation is solved in the terminal cases D.

The id is the identity function basically for the last call since we do not need to do anything.

Tail-recursive programs in F#

1 Answers1