Комбинаторы парсеров F #

Question

Я пытаюсь перевести пример о монадических парсерах (https://www.cs.nott.ac.uk/~gmh/pearl.pdf) в F #.

До сих пор у меня есть:

type Parser<'a> = Parser of (string -> ('a*string) list) 

let item : Parser<char> = 
    Parser (fun (s:string) -> 
       match s with 
       | "" -> [] 
       | null -> [] 
       | _ -> (s.Chars(0),s.Substring 1)::[]) 

let sat (pred : (char -> bool)) : Parser<char> = 
    parserWf 
    { 
     let! c = item 
     if pred c then return c 
    } 

let char c : Parser<char> = 
    sat (fun c' -> c'.Equals(c)) 

let rec string (str:string) : Parser<string> = 
    parserWf 
    { 
     if (str.Length > 0) 
     then 
      let! c = char (str.Chars 0) 
      let! cs = string (str.Substring 1) 
      printfn "String: %s" cs 
      return c.ToString() + cs 
     else 
      return "" 
    } 

Если удалить else return "" из метода string, то результат всегда пустой список. В Haskell функции строка объявляется:

string :: String -> Parser String 
string "" = return "" 
string (c:cs) = do {char c; string cs; return (c:cs)} 

и это прекрасно работает. Почему функция F # работает не так, как ожидалось?

Answer 1

My Haskell немного ржавый, но не тот фрагмент, который вы разместили, эквивалентный вашему F # -коду, то есть в Haskell тоже вам нужен базовый регистр для рекурсии (пустая строка)?

Если вы удалите часть else, второй для последнего вызова строки (т. Е. Тот, у которого есть только один символ слева) не получит результата от его рекурсивного вызова (передача «"), поэтому он не вернет действительный результат также. Затем он распространяется «вверх», и вы получите пустой список.