‘F#’ Category Archives

« Older Entries
 
25
May

Real world functional programming

by Mikael Lundin in F#, Programming

No Comments Comments

Today I held a seminar about functional programming at Valtech Tech Day. It’s no coincidense that the title of the seminar is the same as the book by Tomas Petricek, since it inspired me to do the talk. After playing around with F# for over a year, it’s time to get serious and use it in production case.

You will find my slides here. (or download as pdf)

Do we need functional programming?

Yes! Our CPU’s aren’t getting faster, but better at doing several things at the same time. That is why we need to focus on parallel programming, and parallel programming is hard to do with imperative programming. That is why we must rethink our problem definitions and make them much more expressive, solving our problems with functional concepts.

What functional programming language should i learn?

If you’re on .NET today, F# will be the shortest path to functional programming for you. If you’re a hardcore Java developer you should look into Clojure. Erlang seems to be the coolest functional language right now, but Scala is also an alternative.

Is recursion the answer to everything?

Some people does not like recursion because they’re so used to iterative way of thinking. There’s nothing hard about recursive programming, but your brain is not tuned for it. Recursion is not the solution to everything, just as the foreach/while-loop is not the answer to everything, but I would say that its just as important as a looping construct.

Monads, gonads?

Ehhm … yeah.

8
Apr

Option type implementation in C#

by Mikael Lundin in F#, Programming

2 Comments Comments

F# has this clever functionality called Option<’a>. This means that, instead of returning null from a function, you return an option. This option could have the value Some x or None, where x is the value you want to return, clearly indicating that this method could return a value or not.

let getIndexOfSubstring (s : string) (substring : string) =
    let index = s.IndexOf(substring)
    match index with
    | -1 -> None
    | n -> Some n

Function signature:

val getIndexOfSubstring : string -> string -> int option

And for those of you not fluent in F#, this means that getIndexOfSubstring takes two strings and returns an option of int. This option could be Some int, or it could be None if the substring is not found.

What you win, is that option is now part of the method signature. As a method invoker you will have to handle the None option. As with NULL references, a null return value is often a side effect of the method and often unexpected.

Implement Option<’a> in C#

The option type is a type that we use as return value from a method.

public Option<int> GetIndexOfSubstring(string s, string substring)
{
    var index = s.IndexOf(substring);
    if (index == -1)
        return new None<int>();

    return new Some<int>(index);
}

What does this mean?

  1. The implementation clearly states that the method returns some value or no value at all.
  2. If the return type is an option, you need to return both Some and None for the construct to be valid. The caller of this method expects that both Some and None are possible values.

The method signature also provides you with better test names.

[Test]
public void ShouldReturnSomeIndexForExistingSubstring()
{
    /* Test implementation */
}

[Test]
public void ShouldReturnNoneWhenSubstringDoesNotExist()
{
    /* Test implementation */
}

What are Some and None?

The example code makes much more sense if you look at the class diagram of Some/None.

The code for the option is very abstract.

// Used as return type from method
public abstract class Option<T>
{
    // Could contain the value if Some, but not if None
    public abstract T Value { get; }

    public abstract bool IsSome { get; }

    public abstract bool IsNone { get; }
}

We could implement IsSome/IsNone by comparing this type with Some/None class, but I don’t like the idea of a superclass reference any subclass.

The implementation of Some and None are pretty straight forward.

public sealed class Some : Option
{
	private T value;
	public Some(T value)
	{
		// Setting Some to null, nullifies the purpose of Some/None
		if (value == null)
		{
			throw new System.ArgumentNullException("value", "Some value was null, use None instead");
		}

		this.value = value;
	}

	public override T Value { get { return value; } }

	public override bool IsSome { get { return true; } }

	public override bool IsNone { get { return false; } }
}

public sealed class None : Option
{
	public override T Value
	{
		get { throw new System.NotSupportedException("There is no value"); }
	}

	public override bool IsSome { get { return false; } }

	public override bool IsNone { get { return true; } }
}

Creating a Some instance with null value is only ridiculous, and that is why we throw an exeption. The same goes for calling Value on None.

How do you call a method that returns Option<T>?

Here is some code that will call my first example and act differently if the result is Some or None.

// Get string before substring
private string SubstringBefore(string s, string substring)
{
    var operations = new StringOperations();
    var index = operations.GetIndexOfSubstring(s, substring);

    if (index.IsSome)
        return s.Substring(0, index.Value);

    return s;
}

What are the benefits of the calling method?

  • The result must immediately be checked if it is Some/None before you start using the value. Of course you could ignore the check and go directly to index.Value if you’re willing to take the exception when index is None. (just like null values)
  • It’s clear for the reader that GetIndexOfSubstring might not return a value and that has to be dealt with.

Using Option<T> with reference types

Value types like int already have this functionality with Nullable<T>. Nullable works the same way with a different purpose, to give value types a null value.

With value types it is quite clear that “null” means “no value”, but with reference types it could mean

  • Abscense of value. The method states that for given input there is no output value.
  • Empty set. Specially working with databases, null could mean that the result set was empty.
  • Unknown. The method does not know how to respond and throw us a null (when it really should throw an exception)
  • Not initialized. An object has not been initialized and the reference is null.

The real danger of null in .NET is when it comes from the framework or a third part library and we where not expecting it. That is when you’ll see the NullReferenceException, the most – and it could pop up at any time in production.

This is why we don’t allow null values into Some. Better to fail early when we’re creating the result set of the method, than letting the program run in a faulted state until it tries to use that value.

public Option<User> FindUserByName(string name)
{
	var query = from user in Users
				where user.FirstName.Contains(name) || user.Surname.Contains(name)
				select user;

	var found = query.FirstOrDefault();
	if (found == null)
		return new None<User>();

	return new Some<User>(found);
}

What has to be noticed in this example, is that found really have to be checked for null before entered into Some, or it may blow up. This means that Some/None null checks would be all over the place violating DRY. Could we fix it with an extension method?

public static class OptionExtensions
{
    public static Option<T> SomeOrNone<T>(this T reference)
        where T : class
    {
        if (reference == null) return new None<T>();
        return new Some<T>(reference);
    }
}

And this changes the previous example to.

var found = query.FirstOrDefault();
return found.SomeOrNone();

When is it elegible to return Some<T> instead of Option<T>?

When we have a reference return type that we want to communicate, “could never be null”, we could use Some as the return type, but this would feel a bit weird at the method invokers end.

You could communicate the same thing with Microsoft Code Contracts.

Here’s really three possible state of Option<T>, Some/None and Null. How do I protect myself from a method with Option<T> return type, from returning null?

Microsoft Code Contracts is also the answer here, or you could look into AOP and write an aspect that will throw an exception when you try to return null instead of an instance of Option<T>.

If you’ve decided on the method signature, you probably also agree on the pattern Some/None. But the method signature could be forced upon you with an interface, and in that case some security measure that makes sure that you don’t return null could be useful.

All the source code in a nice packaged VS2010 solution can be downloaded from here.

22
Mar

F-sharpen your saw

by Mikael Lundin in F#, Programming

No Comments Comments

This is the content of a presentation of F# that I will have at the office in a couple of weeks. I wrote this presentation in HTML using the S5 framework by Eric Meyer. That is what makes it so simple for me to just post the content now on my blog. It’s all HTML. :)

F# is a programming language that allows you to write simple code to solve complex problems.

The quote comes from Don Syme.

With programming language, Don means that F# is not a new platform, but just another language on the CLR. This means that the libraries that already works for C# and VB.NET are likely to also work well with F#.

One strength with F# is to express as much intent as possible with little code. The theory is that quantity of code cause bugs and if we could limit the amount code we would also limit the amount of bugs. Reports from users has also told stories about exceptionally small amount of bugs in code produced in F#. This might be a hard statement to prove since F# draws the attention of developers of a different kind.

Don Syme says that F# is not a language meant to solve all problems, but specific problems of a complex nature. F# has never meant to replace C# or VB and is not suitable for tasks that depends on changing a mutable state. The first thing that comes to mind is Workflows and state machines.

Functional .NET

Two paradigms that rule the F# language

  1. Everything is a function
  2. Everything is immutable

Since every good thing comes in trees we should specify the big threes for functional
programming.

We will look at what a function is in F# and how treating everything as a function changes the way you code.

If you define a variable in F# it is immutable by default which means that its value will never change. This changes the way you loop and aggregate things in F# compared to an imperative language like C#.

Getting Started

F# Interactive is found in View/Other Windows/F# Interactive

F# interactive window within Visual Studio

You will find the F# interactive window in the View/Other Window menu option. This is where you can evaluate your expressions as you code. Simply copy the code to the interactive and add double semicolon ‘;;’ to evaluate, or use one of the shortcut commands in Visual Studio. Mine is, mark the code to evaluate and press Alt + ‘

Everything is a function

  • let area w h = w * h

    Result: val area : int -> int -> int

  • let half x = x / 2

    Result: val half : int -> int

  • let triangleArea w h = half (area w h)

    Result: val triangleArea : int -> int -> int

  • let myTriangle = triangleArea 2 4

    Result: val myTriangle : int = 4

A function is defined with the keyword let. First argument is the name of the function and the rest are arguments to that function. After the “=” (equals sign) comes the function body. In F# we don’t make a distinction between variables and functions with no arguments. These are the same. If the expression can be evaluated it will.

Argument types are inferred at compile time. Sometimes the compiler can’t inferr the types and we’ll have to specify them explicity.

Mutability

This imperative language uses the side effect of the for loop to change the mutable
state of the result variable

		namespace LiteMedia.CSharpLecture
		{
			public class Example1
			{
				const int Max = 100000;

				public void Aggregate()
				{
					var result = 0;
					for (int i = 1; i < Max; i++)
						result += i;

					System.Console.WriteLine(result);
				}
			}
		}

If the world can’t change it won’t have side effects. Since the world can’t change we continue to create new and better versions of the world.

Imperative programming languages depends on changing states of the program. This is why you aggregate by adding numbers to a result variable.

Immutability → Purity

In a functional programming language where variables are immutable, state won’t change.

		let sum max =
			let result = 0
			for i = 0 to max do
				result <- result + i
			result

		sum 100000

Result: error FS0027: This value is not mutable

Clearly, this program does not work as intended.

You can’t change the state of an immutable variable. This means that

  • Traditional looping makes little sense in F# – recursion
  • Output of a function depends only on the input arguments – purity
  • Side effects are eliminated
  • Calling function f(x) twice will yield the same result both times

Immutability → recursion

		let rec sum max =
			if max = 0 then
				0
			else
				max + sum (max - 1)

Function calls


sum 3 = 3 + (sum 2)
sum 2 = 2 + (sum 1)
sum 1 = 1 + (sum 0)

sum 0 = 0
3 + 2 + 1 + 0 = 6

Since we can’t change the value we will have to create a new value, and easiest way of doing that is calling the method again with different arguments. This is called recursion.

Recursion in F#

Doing it for real does not involve if statements

	let rec sum max =
		match max with
		| 0 -> 0
		| _ -> max + sum (max - 1)
match..with is such common operation it has an alias: function

		let rec sum = function
			| 0 -> 0
			| n -> n + sum (n - 1)

Recursion is not done in F# with if statements, but with matching patterns. This works pretty much like a switch statement on steroids.

Aggregation

let sum max = [1..max] |> List.fold (+) 0
could be written in C#

var result = Enumerable.Range(1, Max).Aggregate((acc, x) => acc + x);
yielding numbers in F#

let sum max = seq { for i in 1..max do yield i } |> Seq.fold (+) 0

Recursing to sum up all the digits from 1-100000 is quite unnessesary. This is how you would do it by using a list, and F# built in Fold.

You can accomplish the same thing with Linq.Aggregate.

Since Linq.Aggregate yields numbers as we request them, this is a more effective solution. The F# code has to first create the list and then sum it up. We can mend this by also yielding numbers.

Even though, the F# solution is 66 characters and the C# solution is 72.

Operators are functions

  • (+)

    Result: val it : (int -> int -> int)

  • (*) 6 7

    Result: val it : int = 42

  • 			let (++) a b = (a + b) * 2
			5 ++ 7

    Result:

    val ( ++ ) : int -> int -> int
    val it : int = 24

Operators are functions too. Just evaluating the + operator will tell us
that it is a function that takes two integers and returns an integer. We
can use it as a function with prefix notation as well as the more ordinary
infix notation.

Creating our own custom operators is trivial, just like defining any function and can be used with both prefix and infix notation.

Partial function calls

let addFive = (+) 5

Result: val addFive : (int -> int)

[1; 2; 4] |> List.map addFive

Result: val it : int list = [6; 7; 9]

When we call a function with less arguments we create a new function with the missing parameters as arguments.

Once we have the correct function definition we can use it anywhere. For example mapping the function onto values in a list.

Anonymous functions

Just like lambdas in C# we have anonymous functions in F#.

(fun x -> x * x) 7

Result: val it : int = 49

Functions as arguments

[1..10] |> List.filter (fun x -> x % 2 = 0)

Result: val it : int list = [2; 4; 6; 8; 10]

Just like in C# we have anonymous functions in F#. We use these as arguments to other functions.

For every number from 1 to 10, filter out those that are x % 2 = 0, even.

Composite functions

When one function is not enough..

	type Color = | Red | Green | Blue
	let colors = [Red; Red; Red]

Is there any color that is not red?

colors |> List.exists (fun c -> c <> Red)

Without lambda expressions

colors |> List.exists (not << (=) Red)

Same thing as

(fun c -> not ((=) Red c))

We can add functions together in F#, very much like calling a function with the result from another function. We do this with the operator << or >>. That means, take the result of this function and feed it to the next function. This can be very useful for simplify things.

NULL does not exist

Have you ever seen this before?

Website that throws NullReferenceException

Have you ever seen the null reference exception YSOD? Then you will be glad to know that no function in F# may return null.

Option<’a>

		let rec findPrime l =
			let isPrime n = [2..(n/2)]
				|> List.exists (fun x -> n % x = 0) |> not

			match l with
			| [] -> None
			| head :: tail when head |> isPrime -> Some(head)
			| head :: tail -> findPrime tail

We can match on the option<int>

			let hasPrime l =
				match findPrime l with
				| None -> false
				| Some(x) -> true

			[4; 6; 8; 9; 11] |> hasPrime

Result: val it : bool = true

Instead of returning null we use the new Some(x)/None functionality. This lets us match on the return value. In this example we have a function that will return first prime number in the list, or None.

We can create a hasPrime function that will check if we get Some(x) that is prime or if we get None.

Why is Option<’a> better than NULL?

  • The Option exists in the function definition.
    val findPrime : int list -> int option
  • The NULL value is an indirect side effect of references. The Option is explicit. When you call the findPrime function, you have to handle the Option result.
  • The match..with pattern matching is designed to handle Some/None values. 
    				match findPrime l with
				| None -> false
				| Some(x) -> true

Records for data structures

You can define complex data structures as records

	type Book = { Title : string; Author : string }
	let book = { Title = "The Treasure Island";
				 Author = "Robert Lewis Stevenson" }
but remember that everything is immutable

book.Title <- "Treasure Island"

Result: error FS0005: This field is not mutable

If you need to define more complex data structures you can define a record type. But you’ll have to remember that this type is immutable as everything else. You can’t change its values once it has been set.

Records as values

You use records in functions as any other value

		type Point = { x : int; y : int }

		let graph fn width height =
			// Is point y between y1 and y2
			// int -> int -> Point -> bool
			let yBetween y1 y2 point = point.y > y1 && point.y < y2

			// For all x, -100 to 100
			[-(width / 2)..(width / 2)]
				|> List.map (fun x -> { x = x; y = fn x})
				|> List.filter (yBetween -(height / 2) (height / 2))

In this example we would like to spot a graph on a panel.

It’s nice to notice that the compiler will asume that we create a Point type at line 10, and we use the partial method yBetween to filter out points at line 11.

When I see such code, I find it amusing to think that F# is a statically typed language and yet, we don’t specify types anywhere but in the type definition. The compiler will try to find out the types as we go and will tell us where it fails.

graph (fun x -> 2 * x + pown x 3) 200 200

Result: val it : Point list = [{x = -4; y = -72;}; {x = -3; y = -33;}; {x = -2; y = -12;}; {x = -1; y = -3;}; {x = 0; y = 0;}; {x = 1; y = 3;}; {x = 2; y = 12;}; {x = 3; y = 33;}; {x = 4; y = 72;}]

graph for y = 2x + x^3

The panel is 200×200 and the graph we would like to draw is y = 2x + x^3. For this purpose we use create a series of point types from x = -100 to x = 100 with the distinction that y also has to be within -100 < y < 100.

Object orientation

A new class called Queue

		type Queue() =
			let mutable queue = []

			member this.Empty = queue = []

			member this.Push x = queue <- queue @ [x]

			member this.Pop =
				match queue with
				| [] -> None
				| head :: tail ->
					queue <- tail
					Some(head)

You create a class very much like a record. When you want to specify member methods you use the keyword member instead of let. I use this to identify the current instance of the class.

Since object oriented programming is very much about changing states of objects, you can create mutable fields within the class. You specify the mutable keyword after let to tell F# that the field is mutable.


type Queue =
class
new : unit -> Queue
member Push : x:obj -> unit
member Empty : bool
member Pop : obj option
end

Using our queue object

let queue = new Queue()

Result: val queue : Queue

[1; 2; 3] |> List.iter queue.Push

Result: val it : unit = ()

			let rec dequeue (q : Queue) =
				match q.Empty with
				| true -> []
				| false -> q.Pop.Value :: dequeue q
			dequeue queue

Result: val dequeue : Queue -> obj list
val it : obj list = [1; 2; 3]

You create a new instance the same way you do in C# with the new keyword.

We can write a function that will dequeue the whole queue into a list.

Unit of measure

An int is not just an int

		[<Measure>] type m
		[<Measure>] type s

		let distance = 100.0<m>
		let worldRecord = 9.58<s>
		let speed = distance / worldRecord

Result: val speed : float<m/s> = 10.43841336

			let km = 1000.0<m>
			let h = 3600.0<s>

			let speedInKmPerHour = speed / (km/h)

Result: val it : float = 37.5782881

What is an int? When I went to school we were forced to answer every math question with the unit of the answer.
- If you take two apples and add three apples, how many apples have you got?
- Five!
- Five, what?
- Five apples.

With this in mind, an int is not just an int. We usually try to tell in the variable name, what the int symbolizes but that is not very type safe. Welcome to a world of units of measure.

Monads Gonads

	// Identity monad
	type Identity<'a> =
		| Identity of 'a

	type IdentityBuilder<'a>(v : 'a) =
		let value = v
		member self.Bind ((Identity v), f) = f(v)
		member self.Return v = Identity v

	let identity = new IdentityBuilder<int>(0)

	let answerToEverything =
		identity { return System.Int32.Parse("42")  }

This is an Identity Monad defined in F#. If you don’t know what a monad is, you don’t have to, because in F# this is abstracted into computational expressions. When a monad is defined it can be used as a computational expression as you see on line 13.

This leads us on to…

Asyncronous F#

		open System.Net
		open Microsoft.FSharp.Control.WebExtensions

		let webGet (name, url) =
			async {
				let uri = new System.Uri(url)
				let webClient = new WebClient()
				let! html = webClient.AsyncDownloadString(uri)
				return name, html.Length
			}

		let addresses = [ "Valtech", "http://www.valtech.se";
						  "LiteMedia", "http://litemedia.se" ]

		let contentLengths =
			addresses
			|> Seq.map webGet
			|> Async.Parallel
			|> Async.RunSynchronously

Async in F# is a monad. That means that you write asynchronous tasks within a computational expression
and bind the async monad to a async task.

webGet is a function with the signature 'a * string -> Async<'a * int> and this enable us to run several instances of this function in parallel. There are several helper functions in F# like AsyncDownloadString that will make it easier for us to write these async tasks.

The example will get content lengths of addresses of a list, in parallel.

Unit Testing F#

No ceremony unit testing

	open Xunit

	// SUT
	let add a1 a2 = a1 + a2

	[<Fact>]
	let ShouldAddTwoNumbersTogether() =
		let result = add 8 4
		Assert.Equal(12, result)

Most exciting part of unit testing with F# is the complete lack of ceremony. All you need is an open Xunit and you’re all set writing tests.

Notice the end parathesis of the let function. This is needed because without it F# will give a function with the definition unit where as Xunit will look for tests with the definition unit -> unit. The paranthesis forces this function signature.

Test doubles

Imagine the following LoginController using a repository

		public class LoginController
		{
			private readonly IRepository<User> userRepository;
			public LoginController(IRepository<User> userRepository)
			{
				this.userRepository = userRepository;
			}

			public bool Login(string username, string password)
			{
				var users = userRepository.GetAll();
				return users.Any( user =>
						user.UserName.Equals(username, StringComparison.InvariantCultureIgnoreCase) &&
						user.Password.Equals(password));
			}
		}

Following is the system we would like to test. The problem is that we have to stub the userRepository to be able to create an instance of LoginController and test the login method. In C# I would use a framework like Rhino Mocks or Moq, but how do we tackle this problem in F#?

Please to meet object expressions

		[<Fact>]
		let ShouldSuccessfullyLoginToController() =
			// Setup
			let user = new User("Mikael", "Hello")

			let repository = {
				new IRepository<User> with
					member this.GetAll() = [|user|] :> seq<User> }

			let controller = new LoginController(repository)

			// Test
			let result = controller.Login(user.UserName, user.Password)

			// Assert
			Assert.True(result)

In F# we can generate concerete instances of any abstract class or interface with object expressions. This is very useful when creating test doubles in testdriven development, since we no longer have any use for stubbing frameworks – only mocking.

Web development

Download Daniel Mohl’s MVC templates

Extension manager - F# and C# ASP.NET MVC3

Daniel Mohl has written a couple of extensions that will help you getting started with F# web development. You’ll find them in the Tools/Extension Manager within Visual Studio. Select the Online tab and search for Daniel Mohl to find all of his extensions available.

Create a new project

Add New Project - F# ASPMVC

With Daniel Mohl’s extension installed you should be able to create a new F# ASPNET project from the Add New Project menu.

The project stub

The project stub

The project created is the same project that you would create for a C# MVC site, but with F# libraries instead. The route setup is translated into F# as with the model binders.

Writing our first home controller

		namespace LiteMedia.Web

		open System.Web
		open System.Web.Mvc

		[<HandleError>]
		type HomeController() =
			inherit Controller()

			member x.Index () : ActionResult =
				x.ViewData.["Message"] <- "Welcome to ASP.NET MVC!"
				x.View() :> ActionResult

			member x.About () =
				x.View() :> ActionResult

Our HomeController is very simple and it displays how to write the index and about methods. Nothing here that is suprising. Very simplistic code and yet everything that comes with the original C# version of this example site.

WCF in F#

It’s easy to define a web service in F#

		[<ServiceContract(ConfigurationName = "IsItFriday",
			Namespace = "http://litemedia.se/IsItFriday")>]
		[<ServiceBehavior(InstanceContextMode=InstanceContextMode.PerCall)>]
		type public IsItFriday() =
			class
				[<OperationContract>]
				member public x.Query() =
					DateTime.Today.DayOfWeek = DayOfWeek.Friday
			end

Kickstart the service

		let host = new ServiceHost(	typeof<IsItFriday>,
			[|new Uri("http://localhost:18889/")|]);

		host.Open();

Writing a WCF web service in F# is pretty straight forward since web services is all about functions and not preserving state.

The web service up an running

A wcf webservice written in F#

Fibonacci

	let fibonacci = Seq.initInfinite (fun i ->
		let rec fibonacci_inner = function
			| 0 -> 0
			| 1 -> 1
			| n -> fibonacci_inner (n - 1) + fibonacci_inner (n - 2)
		fibonacci_inner i)

Result


val fibonacci : seq<int>
val it : seq<int> = seq [0; 1; 1; 2; ...]

Sieve of Eratosthenes

	let primes n =
		let rec sieve = function
		| [] -> []
		| head :: tail -> head ::
			sieve (tail |> List.filter (fun x -> x % head <> 0))
		sieve [2..n]

Result


primes 100

val it : int list = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 73; 79; 83; 89; 97]

16
Feb

Citerus programming challenge

by Mikael Lundin in F#, Programming

No Comments Comments

I’m very weak for programming challenges. Citerus held a contest where you could win an iPad if you would solve their problem. Since I’m a .NET developer, I’m not elegible for winning such a challenge but I love to meet a challenge just for the sake of it.

The Challenge

Given a string

VOCDIITEIOCRUDOIANTOCSLOIOCVESTAIOCVOLIOCENTSU

And a collection of abbreviations

TDD, DDD, DI, DO, OO, UI, ANT, CV, IOC, LOC, SU, VO

What is the shortest string you could produce by removing abbreviations from it?

Example

1) ...BIDDDOCDDD...  (remove DDD)
2) ...BIDDDOC...     (remove DDD again)
3) ...BIOC...        (remove IOC)

The solution

This kind of problem is ideal for F#.

The main problem is that you just can’t remove abbreviations, because you won’t find the shortest string. You will have to try to remove abbreviations in all orders to find the shortest string produced. I do this by recursive calls, where every abbreviation removal is a path in the tree. I solve the problem by taking the branch with the shortest result.

// http://www.citerus.se/jfokus
module CiterusChallenge

// In the string
let s = "VOCDIITEIOCRUDOIANTOCSLOIOCVESTAIOCVOLIOCENTSU"

// Any occurrence of
let abbreviations = ["TDD"; "DDD"; "DI"; "DO"; "OO"; "UI"; "ANT"; "CV"; "IOC"; "LOC"; "SU"; "VO"]

// Should be removed
let rec remove (abbreviations : string List) (s : string) =

    // Collect any version where one abbr is removed from s
    // Filter out those with no effect on s
    let collect =
        abbreviations
        |> List.map (fun abbr -> s.Replace(abbr, ""))
        |> List.filter (fun short_s -> short_s.Length < s.Length)

    // Select longest string of s1 and s2, or s1 if they're equal
    let min (s1 : string) (s2 : string) =
        if s1.Length <= s2.Length then s1 else s2

    // Match result of abbreviations removal
    match collect with
    | [] -> s
    | _  -> List.fold ( min ) s (collect |> List.map ( remove abbreviations ))

// Execute
let solution = lazy ( s |> remove abbreviations )
Utilities.measure_execution_time solution |> ignore

// Tests
let tests =
    "HELLO" = ("HETDDLLDIO" |> remove abbreviations )    &&  // Two consecutive abbr
    "HELLO" = ("HEDTDDILLO" |> remove abbreviations )    &&  // Two nested abbr
    "HELLO" = ("HEDTDDILLO" |> remove abbreviations )    &&  // Removing TDD before DI
    "HELIUM" = ("HELANTDDDIUM" |> remove abbreviations ) &&  // Don't remove DI or TDD, remove ANT then DDD
    "" = ("DTDDIIOC" |> remove abbreviations )           &&  // Take TDD then IOC last DI will leave only empty string
    "B" = ("BIDDDOCDDD" |> remove abbreviations)             // Some wierd example from the problem description

Look, F# with syntax highlighting! All in all, the algorithm code is 11 LOC, if you remove the comments, and runs for 320 ms on my machine.

14
Jan

Communicate your e-mail

by Mikael Lundin in F#, Programming

No Comments Comments

For anyone to contact you they need to know how. That’s why you should display your e-mail everywhere. Except … you will get a lot of spam because e-mail is not secure by default.

The e-mail protocols are flawed and that is why there are spammers, constantly scanning the web for new e-mail addresses for sending crap to.

What alternatives do you have communicating your e-mail address on the web, without handing it over to spammers framed in gold?

Content information as an image

Spammers are lazy. If it takes too much effort to extract an e-mail they will skip it, because there are millions more waiting. Easiest way to protect your e-mail address from spammers is to put it in an image like below.

Cons

  • You can’t mark and copy the e-mail address into your e-mail client. You’ll have to type it out manually.
  • The image can’t be percieved by blind people or other kinds of screen readers.

Use scripts to display e-mail

Since spambots very seldom execute client side scripts on a page it would be safe to create a placeholder on the page and replace the contents with the e-mail. You could do it with javascript, or Flash, Silverlight if you want to make it even harder to parse out it with a bot.

<html>
	<body>
		<span id="email">[Email Placeholder]</span>
		<script type="text/javascript">
			document.getElementById('email').innerText = "spam@litemedia.se";
		</script>
	</body>
</html>

Cons

  • Today, most browsers are able to run scripts and most companies allows their employees to run javascript, but this is not unobtrusive javascript. If you turn of javascript, content of the page will change.

Convert to HTML Literals

Most of the bots are quite stupid. They download the html page and run a regex looking for e-mail addresses. If your e-mail address does not look like an e-mail address they will not find it. That’s why you could convert every character in your e-mail address to ascii html literals.

Here’s how to do the conversion in F#.

let encode (s : string) =
    s
    |> Seq.map (fun c -> System.String.Format("&#{0:d};", c |> int))
    |> System.String.Concat

> encode "spam@litemedia.se";;
val it : string =
  "&#115;&#112;&#97;&#109;&#64;&#108;&#105;&#116;&#101;&#109;&#101;&#100;&#105;&#97;&#46;&#115;&#101;&quot

This is what my e-mail will look like after being rendered in a browser: spam@litemedia.se

Cons

  • A really clever bot will look for the @ literal &#64; and parse out the rest of the e-mail address. That is however not very likely since it is too much work and there are millions of unprotected e-mails waiting.