Part I
Part II
Part III
Part IV
Part V
Part VI

I’ve made the decision to jump onto the functional bandwagon.  I could hardly help it, what with all the recent hype around F#.  At first I blew it off as a novelty language with little more use than selling more seats of Visual Studio, but eventually I decided to at least give it a look, and now I’m dangerously close to convincing myself that this is the language that I’ve been looking for, even though I didn’t know I was looking.

As a CAD manager, many of my coding projects are targeted to tackle a specific task, or linked set of tasks, iterate and manipulate large data sets, and present multiple views of that data.  And while C# can handle those projects, they can get verbose.  I think this is the niche for F#.  At least the niche that I see it filling for me.  Let me illustrate with a concrete example.

I have a small utility for our B.O.M. team that lets them select polylines.  It then displays the sum of the lengths and the sum of the areas of those polylines.  The tool reports to a palette and the values can be copied to the clipboard.  The team requested some updates and while reviewing the code it really struck me just how much code I typed, and now have to manage, for this seemingly small applet; about 430 lines of code across 7 files.

In this and in the next several posts I’m going to share my adventures in re-writing this application using Functional Programming, aka FP, with F#.  My goals for this project are to:

• Create a working application that I can distribute to my B.O.M. team.
• Determine if the design of this app is better expressed in imperative OO terms or in functional terms.
• Determine if the F# version will have less code, yet be just as readable.
• Start learning functional programming using F#.

Since I am still very much in the learning stages of FP & F#, I’m going to tackle this in small chunks.  The first, get my feet wet, chunk is to get a selection of polylines from the user and report the sum of the lengths.  Designing that chunk of code was my first test of one of my goals, “Can this problem be expressed in FP terms?”  And the answer for me was a resounding yes.  I wrote it in pseudo code that looked something like this:

//GetPolylines()
//GetPolylineLengths()
//GetSumOfLengths()
//PrintResult()

Not once did I consider creating an object, and certainly not an object hierarchy; and there was no need, as this is a simple problem and can be easily solved with a few tasks, or functions, with the data flowing from one task to the other.  I spent a total of 15 seconds reviewing my design and then jumped into the IDE, wiped the froth from my lips, and started hammering out code.  Not necessarily the recommended method, but I was having fun.

This is the header for the module.  The only interesting thing here are the identifiers marked as mutable.  These are scoped to the module so that all functions have access to them.  From a functional point of view, this is scary stuff.  Any function in the module can change the values and the other functions have no knowledge of that change happening.  When they access the value, they get whatever one of the other function put there.  It may be more common for FP programmers to pass these values as parameters from function to function.  With that said, this is a very common pattern in an OO class to store state in private member variables, although it is a best practice to access them through a property, and I’ll leave my mutable identifiers until, or if, I find a better, more FP way.  Maybe create functions that retrieve the current values, GetActiveDoc & GetCurrentEditor?  I’m still undecided on that one.

   1: #light

   2:  

   3: module BobbyCJones.BOMTools

   4:  

   5: open Autodesk.AutoCAD.Runtime

   6: open Autodesk.AutoCAD.ApplicationServices

   7: open Autodesk.AutoCAD.DatabaseServices

   8: open Autodesk.AutoCAD.EditorInput

   9:  

  10: //Declare some shared variables for the functions in the module

  11: let mutable activeDoc = Application.DocumentManager.MdiActiveDocument

  12: let mutable currentEditor = activeDoc.Editor

This is the first function in the module.  I modified the name slightly from my original design in order to better reflect what the function returns.  It’s pretty standard stuff, it takes unit for an argument and returns a list of ObjectId’s for the selected Polylines.  In F# unit is an empty list, or ().  Notice the bracket and bananas construct, [| |], to create an array for the SelectionFilter object.  I’ve always called the | symbol a pipe, but on several of the sites I visited to research this project, it was called bananas.  I’m sticking with bananas 🙂

At the end of the function I run a match on the ssResult.Status.  I could have used an if..then expression, but remember, one of my goals is to shake imperative programming thinking while coding in F#, and pattern matching is key to FP.

Also note the for loop to construct the output list.  It can iterate over any IEnumerable object, passing each element to an expression, and build the list from the value returned from that expression.  I simply return the ObjectId property of each selected entity, but any expression is valid, including functions, lambda or named.

   1: //Get a selection of polylines from the user

   2: let GetPolylineIdsFromUser () =

   3:   

   4:   let ssOpts = new PromptSelectionOptions()

   5:   ssOpts.MessageForAdding <- "Select polylines to count: "

   6:   ssOpts.AllowDuplicates <- false

   7:   

   8:   let ssFilter = new SelectionFilter [|new TypedValue((int)DxfCode.Start, "LWPOLYLINE")|]

   9:   

  10:   let ssResult = currentEditor.GetSelection(ssOpts, ssFilter)

  11:  

  12:   //Return a list of ObjectIds

  13:   match ssResult.Status with

  14:   | PromptStatus.OK -> [for selectedEnt in ssResult.Value -> selectedEnt.ObjectId]

  15:   | _ -> []

This next function was my first attempt at calculating the sum of the Polyline lengths.  It is certainly terse, which is one of the things that I was looking for with FP. 

I start a Transaction so I can open the Polylines, note the ‘use’ keyword to automatically dispose of the Transaction.  As a side note, the transaction should be committed prior to being disposed.  I’ll make that modification in the next post.  After starting the transaction, I define a nested function to open the Polylines.  I then map that function to the inputList to create a list of open Polylines, pipe that list to another map function which calls a lambda function to get a list of the lengths, and finally pipe that list to a function that calculates the sum of the lengths.

I was planning my second pass to condense this code even more and it struck me just how inefficient this function was.  It loops over the data three separate times, and that doesn’t include the loop in the previous function.  And although I created the function to sum lengths, I knew that eventually it would need to sum the areas as well, which would likely create even more loops over the data.  Instead of condensing it, I opted to scrap it and start over.

In all honesty the multiple loops didn’t bother me much, considering how small the data set was going to be, a dozen or so would be at the top end.  But this is a learning exercise and it’s better to start with best practices up front rather than try to unlearn bad habits later.

   1: let OrigGetTotalPolylineLength inputList =

   2:   use trans = activeDoc.TransactionManager.StartTransaction()

   3:   

   4:   let openId id =

   5:     trans.GetObject(id, OpenMode.ForRead) :?> Polyline

   6:   

   7:   List.map openId inputList 

   8:   |> List.map (fun ent -> ent.EndParam |> ent.GetDistanceAtParameter)

   9:   |> List.fold_left (+) 0.0

This is the function as it stands now.  Certainly not as terse as the first version, but it only loops the data once and it’s primed for morphing into a function that calculates the sums of lengths as well as areas.  It also demonstrates a couple of key patterns in functional programming, a tail recursive loop, and using an accumulator in a recursive loop.  First let’s look at the accumulator and then we’ll talk about tail recursion.

The nested Loop function is defined on lines 5 – 10.  It’s defined as recursive with the rec keyword.  It’s not fired up until line 13 where it’s started with a seed value of 0.0 for the totalLength and the inputList of ObjectId’s.  On the first pass of the loop a match is run on the inputList.  The first check, line 7, is to see if the inputList matches an empty list, [].  This match will succeed on two conditions, if the initial inputList was empty, in which case the functions simply returns the seed value, or if the recursive loop has reached the end of the list, at which point it will return the accumulated totals of all the lengths.  If the inputList is not empty, it will match the pattern on line 8, hd::tl.  The pattern says, if the list consists of an element, hd, cons’d, ::, with the remainder of a list, tl, then it’s a match.  In essence, this pattern will match any non-empty list.  If you wanted to match a list with exactly one item in it you could use this pattern, hd::[].  Props goes to the first person that comments on how to match other patterns, like a two element list.

The cool thing is that not only does pattern matching allow you to find matches on the structure of a list, but it allows you to assign identifiers to portions of the match and then write functions using those identifiers.  On line 8, the pattern assigns the identifier hd to the first item in a list, it’s head, and tl to the remainder of the list, its tail.  Just to clarify, the head of a list is the first element in the list whereas the tail is itself a list minus the first element.  And this is just the very tip of the iceberg of pattern matching.  But I digress and need to remind myself how to eat an elephant; one bite at a time.  We’ll leave further discussions on pattern matching for another time.

Now that line 8 has matched a list with something in it, line 9 opens the polyline and line 10 adds the polyline’s length to our running total, our accumulator, and recursively calls the Loop function with the running total and the remainder of the list, the tail.  If you’re like me, you need a concrete example to visualize the process.

Let’s imagine that the input list contains 3 polylines with lengths of 5, 1, and 3 respectively.  In these examples I’m going to show a list with lengths, but remember that our actual list contains ObjectId’s not lengths.  On the first call the totalLength is the seed value, 0.0.

Loop 0.0 [5; 1; 3]

The inputList is matched to the non-empty list pattern and the length 5 is extracted and added to totalLength, 0.0 + 5.  Then the Loop function is called again with our new totalLength and the tail of the original list. 

Loop 5.0 [1; 3]

Again a non-empty list is matched and the length 1 is extracted from the head and added to the passed in totalLength, 5.0 + 1.  The loop is called again with our new values.

Loop 6.0 [3]

The list still isn’t empty, so the match is made and 3 is added to totalLength.  The loop is called again.  This time there is nothing after the head, so the tail is an empty list.

Loop 9.0 []

Now the match is on the empty list pattern and the function simply returns our accumulated totalLength, 9.0.  That’s a classic recursive accumulator.

One other note on this recursive function.  It’s tail recursive.  That means that the very last action taken in the recursive section of code is the recursive call.  In other words, no other work is done after the recursion.  It doesn’t take much Google searching to find examples of recursion where it is difficult for the untrained eye to see if it’s tail recursive or not.  My eye is certainly untrained and I hope to get better in this area with time.  Be sure and check out Kean Walmsley’s blog for more information on this topic.

   1: let GetTotalPolylineLength inputList =

   2:   use trans = activeDoc.TransactionManager.StartTransaction()

   3:   

   4:   //Recursive loop to accumulate total length

   5:   let rec Loop totalLength inputList =

   6:     match inputList with

   7:     | [] -> totalLength

   8:     | hd::tl ->

   9:       let polyline = trans.GetObject(hd, OpenMode.ForRead) :?> Polyline

  10:       Loop (totalLength + polyline.Length) tl

  11:   

  12:   //Start the loop

  13:   Loop 0.0 inputList

Here’s something that really amazes me about the F# compiler.  Below is a screen shot of the Visual Studio IDE.  I’m hovering the cursor over the above function’s declaration.  It’s telling me that this function accepts an ObjectId list and returns a float.  Nowhere in this code have I specified type information, not in function declarations, nor in any identifier declarations.  Similar C# and VB code would be peppered with type information.  How does it know that the identifier ‘inputList’ refers to a list of ObjectId’s?  How does it know it returns a float?  It’s almost magical how F# can infer type information.  My best guess is that it infers it’s a list because of the match patterns I’m performing on it and it infers that the list contains ObjectId’s because I pass the list elements as the first argument of the trans.GetObject() method and that argument requires an ObjectId.  On occasion you’ll need to give the compiler a hint by declaring a type, but I haven’t had to do it yet in my admittedly simple application.

And finally we have the CommandMethod function that brings all the others together.  It also sets values for the mutable activeDoc and currentEditor identifiers.  If we didn’t do this, then these identifiers would always refer to the document that was open when the assembly was first loaded; an apt illustration of the dangers of maintaining state.  Ooh, I think I’ve finally scared myself into not using these.  Yet another change for the next installment.

The rest of the code flows pretty much with my original design, just calling the other functions and piping the results through until it prints the result at the end.

   1: [<CommandMethod("GetPolys")>]

   2: let Main () =

   3:   activeDoc <- Application.DocumentManager.MdiActiveDocument

   4:   currentEditor <- activeDoc.Editor

   5:   

   6:   GetPolylineIdsFromUser () 

   7:   |> GetTotalPolylineLength 

   8:   |> (fun length -> "\nTotal length: " + length.ToString())

   9:   |> currentEditor.WriteMessage

In Part II I’ll refine these a little more and add the ability to report area as well as length.