Very simple type generator (annotates ASTs with approximate types)

main.fs

module Prog

type Node = Call of string * Node * Node
          | Str of string
          | Int of int
          | Binop of string * Node * Node

type Type = FunType of Type * Type
            | StrType
            | IntType

let ast = Call ("print",
                   Call ("something",
                     Int 10, Str "two"),
                   Binop
                     ("+", Int 10, Int 20))

let rec getType = function
  | Call (_,a,b) -> FunType (getType a, getType b)
  | Str _ -> StrType
  | Int _ -> IntType
  | Binop (op,a,b) -> getType a

let rec typeToString = function
  | FunType (a,b) -> sprintf "Func %s -> %s" (typeToString a) (typeToString b)
  | IntType -> "int"
  | StrType -> "str"

let rec printNode t n =
  printf "%s" (System.String(' ', t)) // print t spaces
  printf "(%s) " (typeToString (getType n)) // print type

  match n with
  | Call (s, a, b) -> printfn "Call %s" s; printNode (t+2) a; printNode (t+2) b; printf "\n"
  | Str a -> printfn "<str %s>" a
  | Int a -> printfn "<int %d>" a
  | Binop (op,a,b) -> printfn "Binop %s" op; printNode (t+2) a; printNode (t+2) b

printNode 0 ast
System.Console.ReadKey true |> ignore