Tuesday, 20 September 2016

State machines

Someone on the internet recently asserted that F# is “atrocious” for implementing state machines compared to C#. I just Googled C# state machine and found this. I translated the example into the following F# code:

type State = Inactive | Active | Paused | Exited
type Transition = Begin | End | Pause | Resume | Exit
 
let move = function
  | Inactive, Begin -> Active
  | (Active | Paused), End -> Inactive
  | Active, Pause -> Paused
  | Paused, Resume -> Active
  | Inactive, Exit -> Exited
  | state, transition -> failwithf "Invalid transition: %A -> %A" state transition

Here is their original C# for comparison:

using System;
using System.Collections.Generic;
 
namespace Juliet
{
    public enum ProcessState
    {
        Inactive,
        Active,
        Paused,
        Terminated
    }
 
    public enum Command
    {
        Begin,
        End,
        Pause,
        Resume,
        Exit
    }
 
    public class Process
    {
        class StateTransition
        {
            readonly ProcessState CurrentState;
            readonly Command Command;
 
            public StateTransition(ProcessState currentState, Command command)
            {
                CurrentState = currentState;
                Command = command;
            }
 
            public override int GetHashCode()
            {
                return 17 + 31 * CurrentState.GetHashCode() + 31 * Command.GetHashCode();
            }
 
            public override bool Equals(object obj)
            {
                StateTransition other = obj as StateTransition;
                return other != null && this.CurrentState == other.CurrentState && this.Command == other.Command;
            }
        }
 
        Dictionary<StateTransition, ProcessState> transitions;
        public ProcessState CurrentState { get; private set; }
 
        public Process()
        {
            CurrentState = ProcessState.Inactive;
            transitions = new Dictionary<StateTransition, ProcessState>
            {
                { new StateTransition(ProcessState.Inactive, Command.Exit), ProcessState.Terminated },
                { new StateTransition(ProcessState.Inactive, Command.Begin), ProcessState.Active },
                { new StateTransition(ProcessState.Active, Command.End), ProcessState.Inactive },
                { new StateTransition(ProcessState.Active, Command.Pause), ProcessState.Paused },
                { new StateTransition(ProcessState.Paused, Command.End), ProcessState.Inactive },
                { new StateTransition(ProcessState.Paused, Command.Resume), ProcessState.Active }
            };
        }
 
        public ProcessState GetNext(Command command)
        {
            StateTransition transition = new StateTransition(CurrentState, command);
            ProcessState nextState;
            if (!transitions.TryGetValue(transition, out nextState))
                throw new Exception("Invalid transition: " + CurrentState + " -> " + command);
            return nextState;
        }
 
        public ProcessState MoveNext(Command command)
        {
            CurrentState = GetNext(command);
            return CurrentState;
        }
    }
 
 
    public class Program
    {
        static void Main(string[] args)
        {
            Process p = new Process();
            Console.WriteLine("Current State = " + p.CurrentState);
            Console.WriteLine("Command.Begin: Current State = " + p.MoveNext(Command.Begin));
            Console.WriteLine("Command.Pause: Current State = " + p.MoveNext(Command.Pause));
            Console.WriteLine("Command.End: Current State = " + p.MoveNext(Command.End));
            Console.WriteLine("Command.Exit: Current State = " + p.MoveNext(Command.Exit));
            Console.ReadLine();
        }
    }
}

 

 

Monday, 19 September 2016

Relating PDFs

The F# Journal just published an article about processing documents:
"This article tackles the challenge of computing the relationships between a set of PDF files using the commonality of words within them. The iTextSharp library is used to extract the text in PDF documents and the StemmersNet library is then used to convert the words into word stems. A simple numerical method is used to compute the commonality between the word frequencies in different documents and the resulting relationships are visualized using GraphViz..."

To read this article and more, subscribe to The F# Journal today!

Monday, 29 August 2016

Fun with sequences: part 2

The F# Journal just published an article about sequences:
"The previous article solved a variety of problems that permitted simple solutions. This article takes a look at another problem, run-length encoding, that is simple enough to describe but challenging to implement in F# using sequences..."

To read this article and more, subscribe to The F# Journal today!

Fun with sequences: part 1

The F# Journal just published an article about sequences:
"This article takes a look at sequences in F# in the form of the .NET `IEnumerable` class and its more common alias the `seq` type in F#. A variety of sequences are studied and the advantages and disadvantages of sequences discussed, both in the small and also the higher-level impact that sequences can have when exposed over APIs..."
To read this article and more, subscribe to The F# Journal today!

Sunday, 31 July 2016

Evolution: the weasel program

The F# Journal just published an article about genetic programming:
"In 1986, Richard Dawkins published a book called the Blind Watchmaker about evolution that included a program that was intended to demonstrate evolutionary algorithms running on a computer. The program proved contentious. This article looks at an F# implementation of the program and considers some variations of it to address people's objections to the original..."
To read this article and more, subscribe to The F# Journal today!

Sunday, 12 June 2016

Generating JSON serializers for other languages

The F# Journal just published an article about serialization:
"Serialization is a ubiquitous challenge when writing back-end systems. This article describes how we wrote code in F# that generates OCaml code including both type definitions and JSON serialization/deserialization as well as code to generate many example values adhering to the API for a recent project...."
To read this article and more, subscribe to The F# Journal today!

Combinatorial graph layout

The F# Journal just published an article about visualization:
"Laying out the vertices and edges of a graph in 2D to produce an informative diagram is an important challenge in computer science. This article takes a look at an algorithm for graph layout that uses combinatorial optimisation...."

To read this article and more, subscribe to The F# Journal today!

Monday, 16 May 2016

Fractal Explorer

The F# Journal just published an article about computer graphics:
"A fractal is a mathematical set that exhibits a self-repeating structure at arbitrary scales and sizes, and the concept can be used to describe naturally occuring phenomena such as clouds, coastlines, mountains or frost crystals. The advent of modern computer graphics allowed for the complexity and beauty of these structures to be seen in incredible detail by everyone, as first done in the work conducted by Benoƃ®t Mandelbrot at IBM in the 20th century. As technology advances further (in the form of GPUs), real-time fractal explorers have become feasible as well, an example of which will be shown in F# in this article..."
To read this article and more, subscribe to The F# Journal today!

Porting OCaml's Format module

The F# Journal just published an article about translating OCaml code:
" The F# programming language took most of its inspiration from the OCaml programming language that appeared in 1996. Like most members of the Meta Language (ML) family of programming languages, OCaml was bred specifically for metaprogramming and, consequently, provides a wealth of tools related to metaprogramming. One of these tools is the Format module that makes it easy to pretty print code and data in a structured way. This article looks at the work required to port OCaml's 1,329-line Format module to F#..."
To read this article and more, subscribe to The F# Journal today!

Sunday, 27 March 2016

Parsing METAR with FParsec

The F# Journal just published an article about parsing:
"The parser combinator libray FParsec is a very useful tool available for the F# language. It encapsulates a very common and useful computing pattern - the parser monad - and allows us to use it effortlessly in everyday programming tasks. We'll be using it to process METAR code, which is an international semi-standard used to report weather information in aviation..."
To read this article and more, subscribe to The F# Journal today!

Saturday, 26 March 2016

F# vs Rust: Dictionary and HashSet

The F# Journal just published an article about the Rust programming language:
"Garbage collection has been the most common way for programming languages to provide memory safety for the past 20 years but it does not come without its disadvantages. All known garbage collection algorithms offer either good throughput or good latency but never both at the same time. Rust is a new programming language that departs from this tradition of using garbage collection to provide memory safety. By tracking memory management in the type system, Rust makes it possible to achieve memory safety without garbage collection. This approach promises to combine speed and safety. In this article we take a look at some simple programs written in both F# and Rust in order to compare their performance characteristics..."
To read this article and more, subscribe to The F# Journal today!

Sunday, 13 March 2016

Going retro: Bresenham's line and circle algorithms

The F# Journal just published an article about computer graphics:
"This is the first article in our "Going Retro" series that takes a look at some old algorithms that were crucially important in the 1980s but disappeared in the 1990s with the emergence of ubiquitous floating point units and consumer-level graphics hardware. This article looks at Bresenham's line and circle algorithms that were widely used in computer graphics..."
To read this article and more, subscribe to The F# Journal today!

Porting OCaml code to F#: Delaunay triangulation

The F# Journal just published an article about computer graphics:
"Daniel Sleator wrote a great little OCaml program implementing the Delaunay triangulation algorithm in quadratic time. This is an important algorithm in many fields including computer graphics and numerical methods. This article walks through the process of translating this program first into working F#, then into idiomatic F# and finally into efficient F#..."
To read this article and more, subscribe to The F# Journal today!

Sum columns

The F# Journal just published an article about a programming challenge:
"The challenge of a summing the columns of data in a CSV file was posed and solved in a variety of programming languages including F#. Several interesting solutions were presented but the space of solutions is remarkably large for this problem. This article looks at a variety of different solutions and highlights the relative advantages and disadvantages of different approaches..."
To read this article and more, subscribe to The F# Journal today!

Saturday, 23 January 2016

Stoer-Wagner Min Cut algorithm

The F# Journal just published an article about graph theory:
"Many practical problems require the ability to find or approximate the set of edges with the smallest total weight that join a graph into two separate subgraphs. This article walks through the design and implementation of a simple F# program to compute the exact min cut of an undirected weighted graph using the Stoer-Wagner algorithm..."
To read this article and more, subscribe to The F# Journal today!

Sunday, 17 January 2016

Lexing floating-point numbers efficiently

The F# Journal just published an article about lexing:
"The .NET Framework provides functions to parse primitive types including floating point numbers. These functions all adhere to the same API: the string being parsed must hold only the number. This simple API is fine for prototyping and production when performance does not matter but practical applications often lex streams of input containing numbers and, therefore, benefit from the ability to parse a number that is a substring in a given string with a specific starting index and length. This article looks at the design and implementation of a function to lex a sequence of floating point numbers from a string and compares the performance with a version that uses the built-in parsing functions..."
To read this article and more, subscribe to The F# Journal today!

Lexing integers efficiently

The F# Journal just published an article about lexing:
"The .NET Framework provides functions to parse primitive types including integers. These functions all adhere to the same API: the string being parsed must hold only the number. This simple API is fine for prototyping and production when performance does not matter but practical applications often lex streams of input containing numbers and, therefore, benefit from the ability to parse a number that is a substring in a given string with a specific starting index and length. This article looks at the design and implementation of a function to lex a sequence of integers from string and compares the performance with a version that uses the built-in parsing functions, finding that the bespoke solution is 9x faster..."
To read this article and more, subscribe to The F# Journal today!

Decorating trees

The F# Journal just published an article about data structures:
"F# is a versatile language that allows for many different ways in which to tackle a problem, since it encompasses functional, imperative and object-oriented programming techniques. However, the fact remains that it is a functional-first language, and as such, unless otherwise stated, it treats each computation as the evaluation of a mathematical function. Functions are seen as pure, meaning that they do not have side effects, either via memory or I/O actions - they do not alter the program's state. We're going to look at a standard problem which, using F#'s capabilities, can be solved by making use of some notion of state..."
To read this article and more, subscribe to The F# Journal today!

A new GVEdit

The F# Journal just published an article about GUI applications:
"Graphviz is a great tool for visualizing graphs and network diagrams. Sadly the accompanying gvedit tool that is provided with a Windows install leaves a lot to be desired. This is supposed to be a graphical user interface to the Graphviz tool but it is plagued with crashing and lacks some basic modern features such as real-time preview. This article looks at the design and implementation of a replacement for gvedit..."
To read this article and more, subscribe to The F# Journal today!