Играюсь с монадическими парсерами, в смысле пытаюсь реализовать на F# (в теме функциональногог порграммирования недавно, сильно прошу не пинать). Сделал такой набросок:

#light

type Result<'s,'r> = seq<list<'s> * 'r>
type Parser<'s,'r> = Parser of (list<'s> -> Result<'s, 'r>)

let parserFun (Parser(f)) = f

let succeed v : Parser<'s,'r> = Parser(fun i -> seq{yield (i,v)})
let fail : Parser<'s,'r> = Parser(fun _ -> Seq.empty)

let satisfy p = Parser(fun i -> match i with
                                | h::t when p h -> seq{yield (t, h)}
                                | _             -> Seq.empty)
let symbol c = satisfy (fun s -> c = s)
                                                   
let (<|>) (p1:Parser<'s,'r>) (p2:Parser<'s,'r>) : Parser<'s,'r> = 
    Parser(fun i -> Seq.append (parserFun p1 i) (parserFun p2 i))
    
let (<*>) (p1:Parser<'s,'r>) (p2:Parser<'s,'t>) : Parser<'s,'r*'t> = 
    Parser(fun i -> 
              i |> parserFun p1 
                |> Seq.map (fun (rest1, result1) -> 
                    rest1 |> parserFun p2
                          |> Seq.map(fun (rest2,result2) -> (rest2,(result1,result2))))
                |> Seq.concat)
                
let (=>>) (p:Parser<'s,'r>) (f:'r->'t) : Parser<'s,'t> =
    Parser(fun i -> i |> parserFun p                                     
                      |> Seq.map (fun (rest, result) -> (rest, f result)))

let bindP (p:Parser<'s,'r>) (f:'r->Parser<'s,'t>) : Parser<'s,'t>= 
    Parser(fun i -> i |> parserFun p 
                      |> Seq.map (fun (rest, result) -> rest |> parserFun(f result))
                      |> Seq.concat)

let rec many (p:Parser<'s,'r>) : Parser<'s,'r list> =
    Parser(fun i -> i |> parserFun p 
                      |> Seq.map (fun (rest1, result1) -> 
                            rest1 |> parserFun (many p)
                                  |> Seq.map (fun (rest2, result2) -> (rest2, result1::result2)))
                      |> Seq.concat)
    <|> succeed []
                                                             
let many1 p : Parser<'s,'r list> = (p <*> many p) =>> (fun (a,b) -> a::b)

type ParserBuilder() =
    member b.Return(v) = succeed v
    member b.Bind(p,f) = bindP p f
    member b.Zero() = fail
                                    
let parser = ParserBuilder()

Можно ли как-то переписать функцию many, чтобы рекурсия стала хвостовой, а то она отваливается на совершенно смешных размерах входных данных?

P.S.:
Параллельно пытаюсь смотреть на реализацию таких парсеров на Haskell, так смотрю там как-то все проще получается и при этом орудуют только понятием списка. Стоило мне seq результатов заменить на list, как отжирания памяти стали просто громадными. Ну я подозреваю почему это происходит — вычисления списка-результата происходят энергично на каждом этапе, потому заменил его на seq. В Haskell видимо с этим проще из-за ленивости.