7
\$\begingroup\$

Inspired by this question, I decided to grow my own fractal tree.

The problem is: given an integer \$n\$, \$0 \leq n \leq 5\$, print the \$n\$th iteration of the fractal tree. The tree is probably easiest to describe in pictures, so here's a minified version of the first iteration:

__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
_________________1_______________1________________
__________________1_____________1_________________
___________________1___________1__________________
____________________1_________1___________________
_____________________1_______1____________________
______________________1_____1_____________________
_______________________1___1______________________
________________________1_1_______________________
_________________________1________________________
_________________________1________________________
_________________________1________________________
_________________________1________________________
_________________________1________________________
_________________________1________________________
_________________________1________________________
_________________________1________________________

And the second iteration:

__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
__________________________________________________
_____________1_______1_______1_______1____________
______________1_____1_________1_____1_____________
_______________1___1___________1___1______________
________________1_1_____________1_1_______________
_________________1_______________1________________
_________________1_______________1________________
_________________1_______________1________________
_________________1_______________1________________
_________________1_______________1________________
__________________1_____________1_________________
___________________1___________1__________________
____________________1_________1___________________
_____________________1_______1____________________
______________________1_____1_____________________
_______________________1___1______________________
________________________1_1_______________________
_________________________1________________________
_________________________1________________________
_________________________1________________________
_________________________1________________________
_________________________1________________________
_________________________1________________________
_________________________1________________________
_________________________1________________________

The problem states that the output consists of 63 rows and 100 columns, and that the number of iterations is read from standard input. The length of the root (and each branch) of the first iteration is 16, and halves with each iteration.

let translateBy x0 y0 = Seq.map (fun (x, y) -> (x + x0, y + y0))

let reflectYAxis (x, y) = (-x, y)

let root n = seq { for i in 0 .. n - 1 -> (0, i) }
let diag n = seq { for i in 0 .. n - 1 -> (i, i) }

let right n = diag n |> translateBy 1 n
let left n = Seq.map reflectYAxis (right n)

let branch n = seq {
        yield! left n
        yield! right n
        yield! root n
    }

let rec tree n iterations =
    match iterations with
    | 0 -> Seq.empty
    | _ -> seq {
               yield! branch n
               let child = tree (n/2) (iterations - 1)
               yield! child |> translateBy n (2*n)
               yield! child |> translateBy (-n) (2*n)
           }

let format rows columns points =
    let pointsByY =
        Seq.groupBy snd points
        |> Seq.map (fun (y, pts) -> (y, Seq.map fst pts |> set))
        |> Map.ofSeq

    seq {
        for y in rows - 1 .. -1 .. 0 ->
            match pointsByY.TryFind y with
            | None -> new string('_', columns)
            | Some xs -> String.init columns (fun x -> if xs.Contains x then "1" else "_")
    }

[<EntryPoint>]
let main argv =
    let iterations = System.Console.ReadLine() |> System.Int32.Parse

    let rows = 63
    let columns = 100
    let size = 16

    let points = tree size iterations |> translateBy (columns/2 - 1) 0
    for line in format rows columns points do
        printfn "%s" line

    0
\$\endgroup\$
4
\$\begingroup\$

Nice and clean code! There is nothing duplicated, and the functions are all small and clear. I like the different approach from the question that inspired you, taking on a more vector plotting solution, combining the lines afterwards. A few points (no pun intended) I could think of:

The abstraction of calling tree just leaks a bit, when you need to call the translateBy in the main function. You might want to either:

  • pass the columns parameter to the tree and centering the points there (which would move the recursive function to a sub-function tree')

Like this:

let tree n iterations columns =
    let rec tree' n iterations =
        match iterations with
        | 0 -> Seq.empty
        | _ -> seq {
                   yield! branch n
                   let child = tree' (n/2) (iterations - 1)
                   yield! child |> translateBy n (2*n)
                   yield! child |> translateBy (-n) (2*n)
               }
    tree' n iterations |> translateBy (columns/2 - 1) 0
  • or have a separate function called centerTree to do the translateBy part

Like this:

let centerTree columns points = points |> translateBy (columns/2 - 1) 0

Some statements switch between the "normal" parameter adding and the "forward pipe" |> style. I would replace code like

Seq.groupBy snd points
|> Seq.map

with code like

points
|> Seq.groupBy snd
|> Seq.map

just to keep the flow going.

When you avoid the for loop at the end, and replace it with a Seq.iter, that would be more "functional style", and you could write:

tree size iterations
|> centerTree columns
|> format rows columns
|> Seq.iter (printfn "%s")

which may or may not be your preferred style. Mind, the for loop is definitely idiomatic F#, it's just less FP, which I am just more fond of.

\$\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.