F# Workflow for Building Immutable Trees from Delimited Strings

Here is an update on an earlier post: Computation Expressions with .NET Data Types. In that case, I showed how to use computation expressions to build a tree from a character-delimited string. However, there were two things about it I wanted to correct. First, my understanding of idiomatic F# has improved; it’s still a long way from perfect, but it has improved. Second, and more important, I really wanted to create an immutable version, but I lacked the skill with computation expressions at the time of the earlier post.

This post corrects those flaws and presents an interesting workflow design pattern which I think I’m going to find useful in a number of contexts. (For example, it can be adapted to trees based on data structures other than lists; even .NET data structures as in the original post.)

(As always, presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

/// Splits a string into a list, 

/// using char.

let splitter (c:char) =

  let ca = [|c|]

  (fun (s:string) ->

    s.Split(ca) |> Array.toList)

/// Canonical discriminated union tree.

type Tree = 

  | Branch of string*Tree list

  | Leaf of string

/// Computation expression class to

/// split a string into a tree.

type TreeSplitter () =

  member this.Bind (sa,f) =

    List.map (fun s->Branch(s,f s)) sa

  member this.Return sa = 

    List.map (fun s->Leaf(s)) sa

// Test.

/// Split by bar, colon, then dot.

let barColonDot s = 

  Branch(

    s, 

    TreeSplitter() {

      let! x = splitter '|' s

      let! x = splitter ':' x

      return splitter '.' x

    })

// Test print a tree.

let printo =

  let rec f (spc:string) = function

    | Branch(s,c) ->

      printfn "%s%s" spc s

      List.iter (f (spc+"  ")) c

    | Leaf(s) ->

      printfn "%s%s" spc s

  f ""

// Run a test.

printo 

  (barColonDot "a0.a1:b0.b1|c0.c1:d0.d1")

printfn "Your breakpoint here."