Lindenmayer System String Generator in F#

Question

Lindenmayer Systems or L-systems are fractals that can be constructed by applying replacement rules to a string for a certain amount of iterations. For example:

Axiom (start): "FX"
Rules: 
  X -> "X+YF+"
  Y -> "-FX-Y"

Iteration 0: FX
Iteration 1: FX+YF+
Iteration 2: FX+YF++-FX-YF+
Iteration 3: FX+YF++-FX-YF++-FX+YF+--FX-YF+

 F means draw forward
 + means turn clockwise 90 degrees
 - means turn counter-clockwise 90 degrees
 Everything else is ignored

So each can be simplified to:
 0: F
 1: F+F+
 2: F+F+F-F+
 3: F+F+F-F+F+F-F-F+

The goal of my program is to print out those simplified strings given the axiom, rules, and iteration

module LSystem

let getLSystem axiom rules i = 
    let rec find i =
        let replace (str:string)= 
            str
            |> List.ofSeq
            |> List.map (fun x -> 
                match List.tryFind (fun (c,_) -> c = x) rules with
                | Some (_,r) -> r
                | None -> x.ToString() )
            |> List.reduce (+)
        match i with
        | 0 -> axiom
        | _ -> i-1 |> find |> replace
    let simplify (s:string) = s.Replace("X","").Replace("Y","").Replace("+++","-").Replace("---","+").Replace("+-","").Replace("-+","")
    i |> find |> simplify

And something to run it:

open LSystem

let getDragonCurve =
    let axiom = "FX"
    let rules  = [
        ('X',"X+YF+");
        ('Y',"-FX-Y")]
    getLSystem axiom rules

[for i in 0..5 -> getDragonCurve i]
|> List.iter (fun x -> printf "%s\n" x)

System.Console.ReadKey() |> ignore

I'm specifically concerned about the simplify function, as using straight up C# methods is often a sign you're doing things wrong. I'm quite new to F#, so any style-centric tips are greatly appreciated.

Answer 1

To simplify you should just split at the F's and replace each section of +, -, X and Y characters with a string of +, a string of - or the empty string depending what the final balance of +/- characters are. Then you will only be making one pass over the string.

Consider what happens with your approach if the string to be simplified is ++---. If I understand your code correctly you end up with +++ which you would like to represent as -. In order to do this, however, you have to make another pass over the string.

Using my phone right now. When I get to a real computer I'll update with some code.

Update: You can see a Haskell implementation of simplify here: (link). It should readily translate to F#.