Yesterday I attended my first MobiDevDay conference and presented a talk titled “Functional Programming for the Rich Mobile Web with F#.
The scenario for the demo’ed sample app is that a central website receives orders for flowers from all across the US. Local florists can look at the orders in their area and choose to fill the ones they can – with the help of the sample app. The app has only two screens as shown below:
Running sample: http://mdd.apphb.com
(needs HTML5 browser and location access). Allow upto 20 seconds for the first page to load. The sample is running is on the free version of AppHarbor which probably provisions some parts on demand. The total data downloaded (including all scripts) is only 250K for the first page.
My previous post on Bin Packing described how the best fit heuristic algorithm can be used for creating job shop schedules. However, as they say, a picture is worth a thousand words so being able to visualize a schedule would be very desirable.
Above is a Gantt chart created from a schedule of machine jobs. The sample F# script code describing how to generate such a chart is here: http://fssnip.net/hK
Many types of computational problems can be mapped to ‘bin packing’. Scheduling of jobs on a set of available machines is one such problem which is common in job shop type environments.
Here is some F# code that implements the ‘best fit’ heuristic algorithm for bin packing:
Also provided is an implementation of binary tree with duplicates for tracking remaining bin capacities:
There are two issues:
2) Rich and mobile web development is becoming more like client-server development but the client side and the server side are two different worlds; lacking is a way of developing in a cohesive way for both.
Fortunately there is F# and WebSharper!
Recently I rolled up the sleeves and jumped in with both feet to build a mobile web application in WebSharper and JQuery mobile - as a learning exercise.
Sample application is online here: http://mins.apphb.com (needs an HTML5 capable browser). The full source code is here: http://ahmobe.codeplex.com
In natural language processing (NLP), one of the first steps is to find the ‘stems’ of words from the ‘paradigm’ forms found in regular text. For example “construction” and “constructing” are paradigms of the stem “construct”. (Note there is a *lot* more to NLP, even stemming, than what can be described here).
For textual analysis, one is usually interested in the stems. One of the best known algorithms for stemming is Porter’s Stemming Algorithm, described in this paper: http://tartarus.org/martin/PorterStemmer/def.txt.
The corresponding F# implementation is here: http://fssnip.net/eR
On the main site - http://tartarus.org/martin/PorterStemmer/ - there is a list of implementations of the Porter algorithm in different languages. It is interesting to compare the implementations to see how different languages deal with essentially the same algorithm.
I have not looked exhaustively but I believe the Haskell implementation is the shortest and the cleanest (only about 150 lines). The F# code I wrote is about 190 lines.
In terms of readability, there are parts of the Haskell code that are very obtuse. It takes quite a bit of mental parsing to figure out what is going on. By comparison, I wrote the F# code by reading the paper section by section and just translating that to code. If you look at the rules in the original paper, you will find an almost exact correspondence in the F# code.
For F# I used Active Patterns extensively for pattern matching and as a result you get a Prolog like feel to the code.
Constraint Programming is a vast subject area in AI and Operations Research. Some well-known Constraint Satisfaction Problems (CSP) are Sudoku, N-Queens, Map Coloring, Scheduling (of many kinds, e.g. classrooms-to-courses).