CODEWITHSUNDEEP
f#f#-3.0
reach4thelasers
reach4thelasers

Reputation: 26899

Matching Patterns of Objects in F#

I have zero experience with F#. I started reading F# for C# Developers this weekend.

I had a problem recently (C# Code) where I had to search a list of .NET objects for subsets of objects that matched a certain pattern.

I described it as "regex style matching for objects" in the question. And I did get a great solution that I was happy with, and which seems to perform quite well.

But my recent interest in F# lead me to wonder whether functional programming might have an even better solution.

How would you solve this problem in F#?

Regex Style Pattern Matching in .NET Object Lists

Upvotes: 1

Views: 367

Answers (3)

kaefer
kaefer

Reputation: 5741

Building on the other answers: Start by implementing a parser combinator allowing composition of the type Parser<'a list>. Add parsers for the minimal grammar required by 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 []

Finally create a function which will run the parser repeatedly until the input list is exhausted.

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])]

Upvotes: 2

Tomas Petricek
Tomas Petricek

Reputation: 243041

One interesting functional concept that might be useful here is parser combinators. The idea is that you use composable functions that describe how to read some input and then compose parsers for complex patterns from a couple of primitives.

Parsers normally work over strings, but there is no reason why you couldn't use the same method to read a sequence of chromosomes.

With parser combinators, you would rewrite the "regex" as a composition of F# functions. Something like:

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

This would give you a function that takes a list of chromosome objects and returns the parsed result - the subset of the list. The idea is that functions like zeroOrMore build parsers that detect certain patterns and you compose functions to build a parser - you get a function that you can just run on the input to parse it.

Explaining parser combinators is a bit too long for a SO answer, but it would probably be the most idiomatic F# approach to solving the problem.

Upvotes: 4

Guy Coder
Guy Coder

Reputation: 24976

This is a comment posted as an answer because it is to long for a comment.

Since it seems that Regular Expressions are working for your problem and that you might suspect that F# pattern matching or active patterns might be a better solution I will add some understanding.

The input R+B{3}D+ as I see it is a formal grammar, and as such will require a parser and evaluation engine, or the creation of something like a finite state machine. Since you know already that .Net Regex can solve this problem, why go through all of the trouble to recreate this with F#. Even using F# pattern matching and active patterns will not be easier than using RegEx.

Thus the problem is basically to convert the C# code to F# code and make use of RegEx. So you are asking us to translate your C# to F# and that is not a valid SO question.

EDIT

As Mark Seemann noted in a comment the only input we have is R+B{3}D+. So if your actual grammar is more complicated than what RegEx can handle then there might be a better solution in F#.

Hopefully this helps you understand what you are asking.

Upvotes: 2

Related Questions