Friday, September 17, 2010

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) = (fun s->Branch(s,f s)) sa
  member this.Return sa = (fun s->Leaf(s)) sa
// Test.
/// Split by bar, colon, then dot.
let barColonDot 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.
  (barColonDot "a0.a1:b0.b1|c0.c1:d0.d1")
printfn "Your breakpoint here."

No comments: