Challenge problem for IC

istep.ml

type expr =
  | Int of int
  | Plus of expr * expr

let rec step (e : expr) : expr option =
  match e with
    | Int i -> None
    | Plus (Int i, Int j) ->
	Some (Int (i+j))
    | Plus (Int i, e) ->
	let Some e' = step e in
	  Some (Plus (Int i, e'))
    | Plus (e1, e2) ->
	let Some e1' = step e1 in
	  Some (Plus (e1', e2))

(* Reference implementation of run *)
let rec run (e : expr) : expr list =
  match e with
    | Int i -> [e]
    | _ ->
	let Some e' = step e in
	  run e' @ [e]

(* Tail recursive implementation *)
let run_tr (e : expr) : expr list =
  let rec loop (e : expr) (a : expr list) : expr list =
    match e with
      | Int i -> e :: a
      | _ ->
	  let Some e' = step e in
	    loop e' (e :: a)
  in
    loop e []

(* Smart(?) implementation *)
(* Needs better data struct than list to be smart *)

let rec run' (e : expr) : expr list =
  match e with
    | Int i -> [e]
    | Plus (Int i, Int j) ->
	let Some e' = step e in
	  [e'; e]
    | Plus (e1, e2) ->
	let (i::e1s, e2s) = (run' e1, run' e2) in
	let _::ys = List.map (fun e -> Plus (e, e2)) (i::e1s) in
	let z::_ as zs = List.map (fun e -> Plus (i, e)) e2s in
	let Some s = step z in
	  s :: zs @ ys