I recently wanted to learn more functional programming, particularly F#, having some long-ago background in Haskell. As we all know, you can find various code snippets and help at various websites, but small examples just don’t expose the challenges that you face in doing a realistic, non-trivial example. Conversely, sometimes you find rather voluminous source code with little comment as to how it works and fits together, and more importantly the process that was used to get to that point. Why were certain choices made? So I wrote these learning experiences here to possibly help others. Depending on the interest, I could put this up at Github or elsewhere as well, although there are ample code downloads provided here. There are of course a great many snippets of code here, but at various points, I provide a link to download complete file(s) of what was done to this point. I always find this to be useful in that I don’t have stitch together various snippets to recreate someone else’s code body, possibly getting it wrong or incomplete.
So with some F# basics under my belt, and decided to use the branch and bound algorithm to deepen my F# skills. It shows a bottom-up type approach as we build towards a generalized solution and is meant to be primarily tutorial in nature; I’ll have further comment on doing a top-down approach later. As will be seen, this domain will create some interesting choices and is also ameniable to parallel processing which will bring up the need to use additional language features.
I assume that you have some basic knowledge of F# as well as a programming background. While this material is not geared to experts, and starts from the beginning in terms of the example domain, it assumes you know the basics of functions, data types, indentation style, containers, etc. It gently guides you towards a functional approach, and explores many options along the way. I am using Visual Studio 2013 Pro with F# version 3.1, but I think you can do everything I have here with the free Visual Studio Community edition or other tools as available at F#. There are many introductory F# resources, such as this one, to consult if necessary and implementations on various platforms. F# has a rich set of available libraries including coupling with .NET on various platforms (see the Mono project). I avoid using .NET functionality until Parts III and IV as the emphasis is on learning core F# and focussing on the functional programming style. The goal is also not developing or implementing state-of-the-art branch and bound techniques; but nontheless the code base may prove to be quite useful.
While I think that I am rapidly getting up to speed on F#, I do not purport to be an expert. Indeed you will see several places in the text where I pose a question for the community. I would really like to get input on these, as well as any other input. Please feel free to contact me at the email above. You are free to use the code here for any purpose, but there is no warranty of any kind of course. You can’t reprint or repurpose the textual material, however, without permission.
Thanks goes to the developers of Pandoc and the F# formatting tools which were used to create this site.
On to: Part I: 0-1 Knapsack