type Re = Eps | Chr of char | Alt of Re*Re | Seq of Re*Re | Star of Re

let rec nullable =
    function
    | Eps | Star _ -> true
    | Chr c -> false
    | Alt(a,b) -> nullable a || nullable b
    | Seq(a,b) -> nullable a && nullable b

let rec step (c:char) : Re -> list<Re> =
    function
    | Eps -> []
    | Chr c' -> if c=c' then [Eps] else []
    | Alt(a,b) -> List.append (step c a) (step c b)
    | Seq(a,b) -> let steppeda = step c a |> List.map (fun a2 -> Seq(a2,b))
                  let steppedb = if nullable a then step c b else []
                  List.append steppeda steppedb
    | Star a -> step c a |> List.map (fun a2 -> Seq(a2, Star a))

open System.Numerics

let stepState state c =
    state |> List.collect (fun (re,n) -> step c re |> List.map (fun re' -> (re',n)))
          |> List.groupBy fst |> List.map (fun (re,ns) -> (re,Seq.sumBy snd ns))

let parse re = Seq.fold stepState [re, BigInteger(1)]
let count re = parse re >> List.filter (fst >> nullable) >> List.sumBy snd


let n = 200
let str = String.replicate n "a"

let a = Chr 'a'
let sa = Star(a)

let re1 = Seq(sa, sa)
assert (count re1 str = BigInteger(n+1))

let re2 = Seq(sa, Seq(sa, sa))
assert (count re2 str = BigInteger((n+2)*(n+1)/2))

let re3 = Seq(sa, Seq(sa, Seq(sa, sa)))
assert (count re2 str = BigInteger((n+3)*(n+2)*(n+1)/6))

let re4 = Star(Seq(a,sa))
assert (count re4 str = pown (BigInteger 2) (n-1))

let re5 = Star(Alt(a, Seq(a, a)))
let rec fib n a b = if n=0 then a else fib (n-1) b (a+b)
assert (count re5 str = fib n (BigInteger 1) (BigInteger 1))