Constructing a simple tree with ASCII in F#

Question

This is just a basic HackerRank challenge I was working on to better understand F#. Its purpose is just to print a tree that has a straight 'trunk' of \$n\$, splits into 2 branches which diverge to \$n\$, then branches grow a straight trunk to \$\frac{n}{2}\$ which split and diverge to \$\frac{n}{2}\$, etc.

(Note: I was told to avoid using variables if possible, so the only one I used was to store the iterations which are meant to be \$n \le 5\$.)

[<EntryPoint>]
let main argv = 

    let iterations = System.Convert.ToInt32(System.Console.ReadLine())

    //63 rows
    //100 cols
    //16 length

    let splitRoots = fun x -> Array.collect (fun elem -> [|elem-1;elem+1|]) x

    let isEven = fun i -> if i % 2 = 0 then true else false

    let advanceBranch = fun x -> Array.mapi (fun i elem -> if isEven i then elem-1 else elem+1) x

    let treeLine = fun oneLocs w -> 
        String.concat "" (Seq.map (fun x -> if Array.exists (fun elem -> elem = x) oneLocs then "1" else "_") w)

    //if trunk and counter > 0  -->  write more trunk
    //if trunk and counter = 0 --> split and transition to branch
    //if branch and counter > 0 --> write more branch
    //if branch and counter = 0 --> transition to trunk and deecrement max
    let rec tree = fun l w h max original counter branch roots acc -> 
        match branch with
        | _ when max = 0 -> 
            acc
        | false when counter > 0 -> 
            tree l w h max original (counter-1) false roots (acc @ [ treeLine roots (seq { 1 .. w }) ])
        | false when counter = 0 -> 
            tree l w h max original (original-1) true (splitRoots roots) acc
        | true when counter > 0 ->             
            tree l w h max original (counter-1) true (advanceBranch roots) (acc @ [ treeLine roots (seq { 1 .. w })])
        | true when counter = 0 ->
            tree l w h (max-1) (original/2) (original/2) false roots (acc @ [ treeLine roots (seq { 1 .. w }) ])

    let emptyRow = String.concat "" (Seq.map (fun x -> "_") (seq{ 1..100}))

    let makeEmptyRowList n = [1..n] |> List.map (fun x -> emptyRow)

    let fillList notFilled = (fun x -> x @ (makeEmptyRowList (63-x.Length))) notFilled

    (tree 16 100 64 iterations 16 16 false [| 50 |] (List.empty))
        |> fillList
        |> List.rev 
        |> List.iter (fun (x:string) -> System.Console.WriteLine(x))

    0 // return an integer exit code

Answer 1

It is good to see that you use recursion instead of for or while loops. For many people who are used to imperative programming, this can be a difficult thing to get used to.

You can make the recursion a bit more readable, though, by confining it to the parts where you need it. At the moment, it is the main event of your program, containing practically all the code. Separation of concerns is not just something that belongs in class design (if you have an OO background); it can (and should) be applied in functional design as well.

For instance, you could split the calculation of the "ones" from the conversion to printable lines. In the recursive function tree, you combine them, making it a bit harder to follow. If you'd change the acc parameter from [string] to [int []], you could have the function return the list of arrays of indices, and do something like:

tree 16 100 64 iterations (*...*)
|> treeToStrings 100
|> List.iter System.Console.WriteLine

And have a function treeToStrings, which contains a slightly modified version of the function treeLine and converts the indices to the strings you want to display:

let displayTree w tree =
    let treeLine oneLocs =
        String.concat "" (Seq.map (fun x -> if List.exists (fun elem -> elem = x) oneLocs then "1" else "_") [1..w])
    List.map treeLine tree
    |> List.append (makeEmptyRowList (63 - tree.Length))

You may notice that this version of treeLine no longer has the extra int seq parameter, but instead gets a single int, passed through from the containing function. This would hide the implementation (how is the conversion to characters done) from the callers. You now no longer need to create a seq everywhere you call this function, you just tell it how long the string should be. You do this already, actually, in your definition of makeEmptyRowList.

A second separation of concerns could be to split growing the trunks from advancing the branches. The recursive tree function has so many parameters because it is used for doing both of these.

Example: when growing trunks (the branch parameter is false) the function recurses just to increase the counter. While the trunks are growing, actually only the third pattern is matched. You could write a smaller function that just grows the trunks, and have it return a list of arrays of the indices for the trunks. This part of the tree function would than change to (for now, ignore the seemingly missing parameters when tree' is called, or that its name changed, I will explain below):

| false ->
    let trunks = growTrunks counter roots
    tree' max original (original-1) true (splitRoots roots) (acc @ trunks)

The same, of course, could be done for advancing the branches:

| true ->
    let branches = growBranches counter roots
    tree' (max-1) (original/2) (original/2) false (branches |> List.rev |> List.head) (acc @ branches)

This would then remove the need for either the counter parameter or the original, as they are not used for recursing through these subfunctions any more.

About the other missing parameters from tree': remember where I metioned hiding the implementation from the callers? In the original parameter list for tree, not only do you need to pass the dimensions of the tree and the initial roots, you also need to pass an empty list, a value for original and counter and a false for branch. This is not so nice to the caller, because the function will behave strangely if I mess some of them up. Besides, we already know what they should be to make a nice tree. We might as well hide the initial values for recursion inside the original function:

let tree l w h max roots =
    let rec tree' max original counter branch roots acc =
        match branch with
        | _ (* ... *)
        (* ... *)
    tree' max l l false roots List.empty

Now the caller does not need to know what that bool means, or that the value for original and counter should be the same as for l.

As a final remark: it's really great to try and reduce the number of variables in your program. However, it's still a good practice to give names to constants. The comments reading //63 rows, //100 cols and //16 length are good information, but it's safer to bind those constants to names, and use those names wherever you need the values:

let rows = 63
let cols = 100
let length = 16

(* ... *)

tree length cols rows iterations (*...*)
|> treeToStrings cols
|> List.iter System.Console.WriteLine

This will make it easier to read whenever they are used. And it may be good to know that a let binding does not create a variable, but more of a constant anyway :).

I'd like to end with: thank you for posting this code! It is nice to see F# code that really puts effort in avoiding mutable state and imperative style code!

Answer 2

There's a couple of simple things you can do to reduce the clutter in your code. For example, this:

let isEven = fun i -> if i % 2 = 0 then true else false

Firstly,

if someCondition then true else false

can always be written simply as

someCondition

You're also missing a trick with your declaration:

let someFunction = fun i -> ...

Can simply be written as

let someFunction i = ...

So your isEven function is simply:

let isEven i = i % 2 = 0

I'm coming back to F# after a long break (2+ years) so I'm not going to suggest anything else as I'm still relearning!

Edit:

Actually...

let emptyRow = String.concat "" (Seq.map (fun x -> "_") (seq{ 1..100}))

Is simply:

 let emptyRow = String.replicate 100 "_"