Transform an Abstract Syntax Tree (AST) in F#

I am trying to design an AST for a decision logic table. One of the things I would like to be able to do with the discriminated union that represents my AST is transform parts of it for different reasons. For clarity I will give you an example

Decision Logic Table

@ VAR = 10 ;Y;

The above can be read as there is one rule and the condition VAR = 10 enters this rule with a Y entry.

Abstract Syntax Tree Definition (simplified for this example)

 type expression = 
     | Value of double
     | Variable of string 
     | Equality of expression * expression

type entry =
    | Entry of string

type entries =
    | Entries of entry list

type conditional =
    | ConditionEntries of expression * entries

type condition
    | Condition of expression * string

type rule = 
    | Rule of condition list

Rendered (before transform)

ConditionEntries(
    Equality(
        Variable("VAR"), 
        Value(10.0)), 
    Entries(["Y"]))

Rendered (after transform)

Rule(
    Condition(
        Equality(
            Variable("VAR"),
            Value(10.0)
        ),
        Entry("Y")
    )
)

Now what I would like to do is transform the above tree to expand the rules that are represented in the entries. My thinking was I could use a recursive function and pattern-matching to do this but I am having a little trouble wrapping my head around it right now.

I guess in essence what I am trying to do is whenever I see a ConditionEntries node, I want to emit a new Rule for every string in the Entries list where the Condition is combined with the Entry. Does that make any sense?

Thanks in advance for any advice.

p.s. I haven't quite tried to compile the above example, so please forgive any grammati开发者_如何转开发cal errors.

Hmm, based on your AST, which is awfully broken up, here is a tranform function which produces the output from input you desire (though it's not recursive, just uses List.map with some pattern matching. expression is your only recursive type but it doesn't look like you want to process it recursively?):

let ex1 =
    ConditionEntries(
        Equality(
            Variable("VAR"), 
            Value(10.0)), 
        Entries([Entry("Y")]))

let ex2 =
    ConditionEntries(
        Equality(
            Variable("VAR"), 
            Value(10.0)), 
        Entries([Entry("X");Entry("Y");Entry("Z")]))

let transform ces =
    match ces with
    | ConditionEntries(x, Entries(entries)) ->
        entries
        |> List.map (function Entry(entry) -> Condition(x, entry))


//FSI output:
> transform ex1;;
val it : condition list =
  [Condition (Equality (Variable "VAR",Value 10.0),"Y")]
> transform ex2;;
val it : condition list =
  [Condition (Equality (Variable "VAR",Value 10.0),"X");
   Condition (Equality (Variable "VAR",Value 10.0),"Y");
   Condition (Equality (Variable "VAR",Value 10.0),"Z")]