Contextual data processing in F #

Question

I recently finished a project in which I created line lists, and I was wondering how to do this.

The line generation was context sensitive to determine if it was acceptable (it was a sequence of games in the game, so you had to know what the last game was)

The way I did this was with a function that was passed by the context parameter and the term, and if it was acceptable, it would recursively continue if it were not completed (since no further line could be acceptable.) The function also received the "length" parameter to make sure that it is completed in the end.

basically it generates every possible line accepted by the language (of a certain length).

Now I got it to work, even pretty good and clean, but I was wondering if there is a better way to do this. In particular, will the "state machine" monad work well in creating context-sensitive grammar? or something like that at least? The problem seems to be simple in running something like parsec, are there any other structures that are effective at manipulating languages?

Any thoughts would be appreciated.

Answer 1

I thought this problem looked interesting, so I tried several different ways to implement it. The code below looks the most promising. I think it solves the problem as described, although I was not sure about some of the details.

, - , , . , "", .

type sym = Xa | Xb | Xc          // The terminal symbols 
type word = sym list             // A string of terminals

type gen = int -> sym list seq   // Generate words up to the given length

/// Passes the previous symbol to a generator, after checking the length.
let (+>) : sym  -> (sym -> gen) -> gen = 
    fun x g l -> if l<=0 then Seq.empty 
                         else seq { for xs in g x (l-1) -> x :: xs }

let nil _ = seq { yield [] }                    // Generate just the empty word            
let (|||) xs ys l = Seq.append (xs l) (ys l)    // Union of two generators
let notAccepted _ = Seq.empty                   // Don't generate anything

let tryAll g = Xa +> g ||| Xb +> g ||| Xc +> g  // Run g starting with any sym

// Generators for non-terminals.  Each takes the previous symbol as an argument,
// and generates a (possibly empty) sequence of lists of symbols.
let rec gR = function Xa ->  Xb +> gS ||| Xc +> gR  ||| nil  
                    | Xc ->  Xb +> gS                        | _ -> notAccepted
    and gS = function Xb ->  Xa +> gR                        | _ -> notAccepted


let genTop = tryAll gR  // The top level generator begins with gR with any sym

let words = genTop 4    // Generate words up to length 4
// val words : seq<sym list> 
//           = seq [[Xa; Xb; Xa]; [Xa; Xc; Xb; Xa]; [Xa]; [Xc; Xb; Xa]]