5
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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#.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.