Соответствующие шаблоны объектов в F #

Question

У меня нет опыта с F #. В эти выходные я начал читать F# for C# Developers.

У меня была проблема недавно (код C#), где мне пришлось искать список объектов .NET для подмножеств объектов, которые соответствовали определенному шаблону.

Я описал его как «соответствие стиля регулярного выражения для объектов» в вопросе. И я получил отличное решение, которым я был доволен, и который, кажется, работает достаточно хорошо.

Но мой недавний интерес к F # заставляет меня задаться вопросом, может ли функциональное программирование иметь еще лучшее решение.

Как бы решить эту проблему в F #?

Regex Style Pattern Matching in .NET Object Lists

Answer 1

Это коментарий в ответ, потому что это долго для комментария.

Поскольку кажется, что регулярные выражения работают на вашу проблему и что вы можете подозревать, что F # pattern matching или active patterns может быть лучшим решением. Я добавлю некоторое понимание.

Ввод R+B{3}D+, как я вижу, это formal grammar, и для этого потребуется механизм анализа и оценки, или создание чего-то вроде конечного автомата. Поскольку вы уже знаете, что .Net Regex может решить эту проблему, зачем решать все проблемы, чтобы воссоздать это с помощью F #. Даже использование сочетаний шаблонов F # и активных шаблонов не будет проще, чем использование RegEx.

Таким образом, проблема заключается в том, чтобы преобразовать код C# в код F # и использовать RegEx. Итак, вы просите нас перевести ваш C# на F #, и это не действительный вопрос SO.

EDIT

Как отметил Марк Seemann в комментарии единственный вход у нас есть R+B{3}D+. Поэтому, если ваша фактическая грамматика сложнее, чем то, что может обрабатывать RegEx, тогда может быть лучшим решением в F #.

Надеюсь, это поможет вам понять, что вы просите.

Answer 2

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

Парсеры обычно работают над строками, но нет причин, по которым вы не могли бы использовать один и тот же метод для чтения последовательности хромосом.

С комбинаторными комбинаторами вы должны переписать «регулярное выражение» как состав функций F #. Что-то вроде:

sequence [ 
    zeroOrMore (chromosomeType R) 
    repeat 3 (chromosomeType B) 
    zeroOrMore (chromosomeType D) ] 

Это даст вам функцию, которая принимает список объектов хромосомных и возвращает проанализированный результат - подмножество списка. Идея состоит в том, что такие функции, как zeroOrMore, создают парсеры, которые обнаруживают определенные шаблоны, и вы составляете функции для создания синтаксического анализатора - вы получаете функцию, которую вы можете просто запустить на входе для ее анализа.

Объяснение комбинаторных комбинаторов слишком длинное для ответа SO, но, вероятно, это будет самый идиоматический подход F # для решения проблемы.

Answer 3

Основываясь на других ответах: Начните с реализации комбинатора парсера, позволяющего составить состав типа Parser<'a list>. Добавьте парсеры для минимальной грамматики, требуемой R+B{3}D+.

type Result<'T> = Success of 'T | Failure 
type Parser<'T> = Parser of ('T -> Result<'T * 'T>) 

module ListParser = 
    let (.>>.) (Parser f1) (Parser f2) = 
     Parser <| fun input -> 
      match f1 input with 
      | Failure -> Failure 
      | Success(value1, rest1) -> 
       match f2 rest1 with 
       | Failure -> Failure 
       | Success(value2, rest2) -> 
        Success(value1 @ value2, rest2) 

    let oneOrMore what = 
     let rec aux gotOne acc = function 
     | x::xs when what = x -> aux true (x::acc) xs 
     | xss when gotOne -> Success(List.rev acc, xss) 
     | _ -> Failure 
     Parser <| aux false [] 

    let exactly what n = 
     let rec aux i acc = function 
     | xss when i = 0 -> Success(List.rev acc, xss) 
     | x::xs when what = x -> aux (i - 1) (x::acc) xs 
     | _ -> Failure 
     Parser <| aux n [] 

Наконец, создайте функцию, которая будет запускать парсер несколько раз, пока не будет исчерпан список ввода.

open ListParser 
let runForall (Parser f) xss = 
    let rec aux n acc xss = 
     match xss, f xss with 
     | [], _ -> List.rev acc 
     | _::xs, Failure -> aux (n + 1) acc xs 
     | _, Success(value, rest) -> 
      aux (n + List.length value) ((n + 1, value)::acc) rest 
    aux 0 [] xss 

type ChromosomeType = R | B | D 

[D;R;R;B;B;B;D;D;B;R;R;B;B;B;D;D;R;R;B;B;B;D;D] 
|> runForall (oneOrMore R .>>. exactly B 3 .>>. oneOrMore D) 
// val it : (int * ChromosomeType list) list = 
// [(2, [R; R; B; B; B; D; D]); (10, [R; R; B; B; B; D; D]); 
// (17, [R; R; B; B; B; D; D])]