F # идиоматический способ преобразования текста

Миелло! Поэтому я ищу краткий, эффективный идиоматический способ в F# для разбора файла или строки. Я предпочитаю рассматривать входные данные как последовательность символов (char seq). Идея заключается в том, что каждая функция отвечает за синтаксический анализ части входных данных, возвращает преобразованный текст, связанный с неиспользуемым входным сигналом, и вызывается функцией более высокого уровня, которая связывает неиспользуемый входной сигнал со следующими функциями и использует результаты для построения составного типа. Каждая функция синтаксического анализа должна поэтому есть подписи, похожие на этот: голец далее -> чар СЛ * 'а . Если, например, функция отвечает просто за извлечение первого слова, то один из подходов будет следующим: 

let parseFirstWord (text: char seq) =
  let rec forTailRecursion t acc =
    let c = Seq.head t
    if c = 'n' then
      (t, acc)
    else
      forTailRecursion (Seq.skip 1 t) (c::acc)
  let rest, reversedWord = forTailRecursion text []
  (rest, List.reverse reversedWord)
Теперь, конечно, главная проблема с этим подходом заключается в том, что он извлекает слово в обратном порядке, и поэтому вы должны его поменять. Однако его основные преимущества заключаются в том, что он использует строго функциональные возможности и правильную хвостовую рекурсию. Можно было бы избежать реверсирования извлеченного значение при потере хвостовой рекурсии: 
let rec parseFirstWord (text: char seq) =
  let c = Seq.head t
  if c = 'n' then
    (t, [])
  else
    let rest, tail = parseFirstWord (Seq.skip 1 t)
    (rest, (c::tail))

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

let parseFirstWord (text: char seq) =
  let rec forTailRecursion t queue =
    let c = Seq.head t
    if c = 'n' then
      (t, queue)
    else
      forTailRecursion (Seq.skip 1 t) (queue.Enqueu(c))
  forTailRecursion text (new Queue<char>())

Я понятия не имею, как использовать понятия OO в F# mind you, поэтому поправки к приведенному выше коду приветствуются.

Будучи новичком в этом языке, я хотел бы руководствоваться обычными компромиссами, которые делает разработчик F#. Среди предложенных подходов и ваш собственный, который я должен считать более идиоматичным и почему? Также, в этом конкретном случае, как бы вы инкапсулировали возвращаемое значение: char seq * char seq, char seq * char list или даже char seq * Queue<char>? Или вы даже рассматриваете строку char seq * после правильного преобразования?
2 3
f# tail-recursion

2 ответа:

Я бы обязательно посмотрел на FSLex. FSYacc, FParsec . Однако если вы просто хотите обозначить a seq<char> , Вы можете использовать a выражение последовательности генерировать токены в правильном порядке. Повторно используя вашу идею рекурсивной внутренней функции и комбинируя ее с выражением последовательности, мы можем оставаться хвостовыми рекурсивными, как показано ниже, и избегать неидиоматических инструментов, таких как изменяемые структуры данных.

Я поменял разделитель char на easy отладка и сигнатура функции. Эта версия производит seq<string> (Ваши токены) как результат, который, вероятно, легче использовать, чем кортеж с текущим токеном и остальной частью текста. Если вам нужен только первый жетон, вы можете просто взять голову. Обратите внимание, что последовательность генерируется "по требованию", то есть входные данные анализируются только по мере потребления токенов через последовательность. Если вам нужен остаток входного текста рядом с каждым маркером, Вы можете дать пару в loop вместо этого, но я предполагать, что нисходящий потребитель, скорее всего, не будет (кроме того, если входной текст сам по себе является ленивой последовательностью, возможно, связанной с потоком, мы не хотим выставлять его, поскольку он должен быть повторен только в одном месте).

let parse (text : char seq) = 
    let rec loop t acc = 
        seq {
            if Seq.isEmpty t then yield acc
            else
                let c, rest = Seq.head t, Seq.skip 1 t
                if c = ' ' then 
                    yield acc
                    yield! loop rest ""
                else yield! loop rest (acc + string c)
        }
    loop text ""

parse "The FOX is mine"
val it : seq<string> = seq ["The"; "FOX"; "is"; "mine"]
Это не единственный "идиоматический" способ сделать это в F#. Каждый раз, когда нам нужно обработать последовательность, мы можем посмотреть на функции, доступные в модуле Seq. Наиболее общим из них является fold, который повторяется через последовательность один раз, накапливая состояние в каждом элементе путем выполнения заданной функции. В приведенном ниже примере accumulate есть такая функция, которая последовательно строит результирующую последовательность токенов. Поскольку Seq.fold не запускает функцию аккумулятора на пустой последовательности, нам нужны последние две строки, чтобы извлечь последний токен из внутреннего аккумулятора функции.
Эта вторая реализация сохраняет хорошие характеристики первой, т. е. хвостовую рекурсию (внутри реализации fold, Если я не ошибаюсь) и обработку входная последовательность по требованию. Он также бывает короче, хотя, вероятно, немного менее читаем. 
let parse2 (text : char seq) =
    let accumulate (res, acc) c =
        if c = ' ' then (Seq.append res (Seq.singleton acc), "")
        else (res, acc + string c)
    let (acc, last) = text |> Seq.fold accumulate (Seq.empty, "")
    Seq.append acc (Seq.singleton last)

parse2 "The FOX is mine"
val it : seq<string> = seq ["The"; "FOX"; "is"; "mine"]
3

Один из способов лексики/синтаксического анализа способом, действительно уникальным для F#, является использование активных шаблонов. Следующий упрощенный пример показывает общую идею. Он может обрабатывать строку вычисления произвольной длины, не вызывая переполнения стека. 

let rec (|CharOf|_|) set = function
    | c :: rest when Set.contains c set -> Some(c, rest)
    | ' ' :: CharOf set (c, rest) -> Some(c, rest)
    | _ -> None

let rec (|CharsOf|) set = function
    | CharOf set (c, CharsOf set (cs, rest)) -> c::cs, rest
    | rest -> [], rest

let (|StringOf|_|) set = function
    | CharsOf set (_::_ as cs, rest) -> Some(System.String(Array.ofList cs), rest)
    | _ -> None

type Token =
    | Int of int
    | Add | Sub | Mul | Div | Mod
    | Unknown

let lex: string -> _ =
    let digits = set ['0'..'9']
    let ops = Set.ofSeq  "+-*/%"

    let rec lex chars =
        seq { match chars with
              | StringOf digits (s, rest) -> yield Int(int s); yield! lex rest
              | CharOf ops (c, rest) -> 
                  let op = 
                      match c with
                      | '+' -> Add | '-' -> Sub | '*' -> Mul | '/' -> Div | '%' -> Mod
                      | _ -> failwith "invalid operator char"
                  yield op; yield! lex rest
              | [] -> ()
              | _ -> yield Unknown }

    List.ofSeq >> lex

lex "1234 + 514 / 500"
// seq [Int 1234; Add; Int 514; Div; Int 500]
2