Fibonacci Fun with F#

As you probably know, the Fibonacci sequence is the infinite sequence of integers where each element is the sum of the previous two (the first two elements being 0 and 1). Recently, I was inspired by a blog post, Ruby vs. Haskell – project Euler #25 deathmatch. In particular, I enjoyed the Haskell solution for its simplicity and declarativeness.

I decided to try and solve the same problem, but using F#, the functional programming language being introduced as a first class .NET citizen for the first time with Visual Studio 2010. If you have never seen F# code before, the snippets included in this post may be difficult to comprehend, especially if you are used to reading code written in imperative languages like C# or Java.

To declaratively create infinite sequences in F#, the Seq module provides the unfold function. This function takes two parameters, a generator function and an initial state. The generator function must take a state parameter and produce an option tuple with a sequence element and a new state. In F# notation, the unfold function has the signature Seq.unfold : ('State -> 'T * 'State option) -> 'State -> seq<'T>. Note that if the generator function always returns Some(_) and never None, the resulting sequence will be infinite.

An example of Seq.unfold in action is shown in the following one-liner, producing an infinite sequence of all positive integers.

let positiveIntegers = Seq.unfold (fun x -> Some(x, x + 1)) 1

In this example, the generator function takes an integer state as input. The sequence element produced by this function is the current state, while the next state is calculated by incrementing the current state. Thus, each time the generator function is called, the input integer state is one higher than the previous time. The initial state, 1, is passed as the final parameter to Seq.unfold. The result is the sequence “1, 2, 3, …, ∞” (or, strictly speaking, as far as 32 bit integers go).

So, how do we go from this sequence to the Fibonacci sequence? First of all, since each element of the Fibonacci sequence is the sum of the previous two, the state cannot consist only of a single integer. Rather, the state has to be a tuple of two integers. By choosing (0, 1) as the initial state, the generator function can use the first tuple element as sequence output and construct the next state as ([next], [current] + [next]), where [current] and [next] are the first and second element, respectively, from the current state tuple.

Translated into F# code, this yields the following definition of the Fibonacci sequence.

let fibonacci =
    Seq.unfold
        (fun (current, next) -> Some(current, (next, current + next)))
        (0, 1)

When enumerating this sequence, however, one problem becomes apparent. Element number 48 is a negative number. This is definitely erroneous behavior, as the Fibonacci sequence consists solely of positive integers. The error is due to the limited value space of 32 bit integers, causing an overflow. To circumvent this problem, we can use the BigInteger type, capable of representing integers of arbitrary size. The only change we need to make to our original Fibonacci definition is to change the initial state tuple to contain BigInteger values. The F# type inference system handles the rest.

open System.Numerics

let fibonacci =
    Seq.unfold
        (fun (current, next) -> Some(current, (next, current + next)))
        (BigInteger 0, BigInteger 1)

Now to the actual solution to Project Euler #25. Modelled after the previously mentioned Haskell solution, my solution also counts the number of elements in the Fibonacci sequence having a value less than 10999.

Again, translating this into F# results in the following code.

open System.Numerics

let limit = BigInteger.Pow(BigInteger 10, 999)

let fibonacci =
    Seq.unfold
        (fun (current, next) -> Some(current, (next, current + next)))
        (BigInteger 0, BigInteger 1)

let term =
    fibonacci
    |> Seq.takeWhile (fun n -> n < limit)
    |> Seq.length

printfn "%d" term

I am intrigued by how this functional solution focuses on what the Fibonacci sequence is, rather than how it is calculated. Constructing an infinite Fibonacci sequence in C# would typically require an iterator consisting of an infinite loop, representing state with two local variables. Counting elements having a value less than 10999, however, could easily have been accomplished in a functional manner using LINQ.

Advertisements

Custom Message Handling with WCF (Part 2 of 2)

In part one, I introduced the concepts behind custom message handling in WCF. This post is all about showing these principles in code. Allow me to first introduce the service I will be working with, a slightly modified version of the service from the default Visual Studio WCF template:

[ServiceContract(Namespace = "https://lookingsharp.wordpress.com/demo/")]
public interface IMyService
{
    [OperationContract]
    CompositeType GetData(CompositeType composite);
}

[DataContract(Namespace = "https://lookingsharp.wordpress.com/demo/")]
public class CompositeType
{
    bool boolValue = true;
    string stringValue = "Hello ";

    [DataMember]
    public bool BoolValue
    {
        get { return boolValue; }
        set { boolValue = value; }
    }

    [DataMember]
    public string StringValue
    {
        get { return stringValue; }
        set { stringValue = value; }
    }
}

My ultimate goal for this post is to communicate with this service, without deserializing the response into a CompositeType object. This requires a custom WCF client, which I prefer to base on the code generated by the Svcutil tool. Running Svcutil against the metadata exposed by the service is done as follows:

C:\temp>Svcutil http://localhost:8731/MyServiceLibrary/MyService/mex
Microsoft (R) Service Model Metadata Tool
[Microsoft (R) Windows (R) Communication Foundation, Version 3.0.4506.2152]
Copyright (c) Microsoft Corporation.  All rights reserved.

Attempting to download metadata from 'http://localhost:8731/MyServiceLibrary/MyS
ervice/mex' using WS-Metadata Exchange or DISCO.
Generating files...
C:\temp\MyService.cs
C:\temp\output.config

C:\temp>

The service definition in MyService.cs generated by Svcutil is equivalent to this code (adjusted to fit the page):

[GeneratedCode("System.ServiceModel", "3.0.0.0")]
[ServiceContract(
    Namespace="https://lookingsharp.wordpress.com/demo/", 
    ConfigurationName="IMyService")]
public interface IMyService
{
    [OperationContract(
        Action="https://lookingsharp.wordpress.com/demo/IMyService/GetData", 
        ReplyAction="https://lookingsharp.wordpress.com/demo/IMyService/GetDataResponse")]
    CompositeType GetData(CompositeType composite);
}

The ConfigurationName property of the ServiceContract attribute refers to the name of the configuration generated in the output.config file.

Now, in order to prevent WCF from deserializing the response of this service, the return type of the GetData method must be Message, and the input parameter must be of type Message or of a type tagged with the MessageContract attribute. Message contracts are explained in the MSDN article “Using Message Contracts“.

According to the metadata of our service, requests are expected to have the following format:

<GetData xmlns="https://lookingsharp.wordpress.com/demo/">
	<composite>
		<BoolValue>True</BoolValue>
		<StringValue>SomeString</StringValue>
	</composite>
</GetData>

Mapping this request format to a WCF message contract is quite straight-forward. Simply reuse most of the CompositeType class generated by Svcutil and wrap it in a request class tagged with the MessageContract attribute, like this:

[MessageContract(
    WrapperName = "GetData",
    WrapperNamespace = "https://lookingsharp.wordpress.com/demo/")]
public class GetDataRequest
{
    [MessageBodyMember(
        Name = "composite",
        Namespace = "https://lookingsharp.wordpress.com/demo/")]
    public CompositeType Request { get; set; }
}

[DataContract(
    Name = "CompositeType",
    Namespace = "https://lookingsharp.wordpress.com/demo/")]
public class CompositeType
{
    [DataMember]
    public bool BoolValue { get; set; }

    [DataMember]
    public string StringValue { get; set; }
}

I can now modify the service contract generated by Svcutil to accept GetDataRequest objects as input and produce Message objects as output. This results in the following definition:

[ServiceContract(
    Namespace = "https://lookingsharp.wordpress.com/demo/",
    ConfigurationName = "IMyService")]
public interface IMyService
{
    [OperationContract(
        Action = "https://lookingsharp.wordpress.com/demo/IMyService/GetData",
        ReplyAction = "https://lookingsharp.wordpress.com/demo/IMyService/GetDataResponse")]
    Message GetData(GetDataRequest request);
}

As for implementing the actual WCF client, I simply inherit ClientBase<IMyService> and delegate requests to base.Channel:

public class MyServiceClient : ClientBase<IMyService>, IMyService
{
    public Message GetData(GetDataRequest request)
    {
        return base.Channel.GetData(request);
    }
}

By default, this client will use the configuration specified by IMyService. I copy the relevant content of the output.config file generated by Svcutil into my project’s app.config file.

That is it. A console application’s Main method using this client could like like this:

static void Main(string[] args)
{
    var client = new MyServiceClient();
    var request = new GetDataRequest
    {
        Request = new CompositeType
        {
            BoolValue = true,
            StringValue = "Hello "
        }
    };
    var response = client.GetData(request);

    Console.WriteLine(response.ToString());
    Console.ReadLine();
}

Feel free to download the complete source code for this post. (Note that the service requires administrative privileges.)

Custom Message Handling with WCF (Part 1 of 2)

Windows Communication Foundation (WCF) is a great framework for creating service-oriented applications. It provides APIs for creating, hosting and consuming services, through text-based protocols like HTTP or binary protocols like TCP or even named pipes. Most of the time, you would conveniently rely on WCF to serialize and deserialize requests and responses on the fly, letting you focus on the business logic. However, sometimes it is necessary to take full control of the messages transferred to another endpoint, or to interpret response messages without WCF interfering with its deserialization functionality.

To take control of the messages, you need to interacts with WCF’s Message class. By default, when you add a service reference in Visual Studio, a set of classes are generated to represent the elements of the messages recognized by the service. To interact with the Message class, you need to write your own WCF client, rather than relying on Visual Studio service references. This might sound intimidating, but is actually quite easy.

With the .NET SDK comes a tool called ServiceModel Metadata Utility Tool (Svcutil.exe). This command line tool generates WCF clients based on WSDL metadata. As a matter of fact, Visual Studio relies on Svcutil to generate its service references. When creating WCF clients without the support of Visual Studio service references, I find it useful to base my code on the types generated by Svcutil.

In order to interact with the Message class, the service interfaces generated by Svcutil require some slight modifications. MSDN provides an article, “Using the Message Class“, which contains information and examples on how to modify the service interface to enable interaction with the Message class. In short, for each operation you require custom handling, replace the parameters (if any) with a single Message parameter or a single MessageContract-attributed type. Further, if it is a non-void operation, the return type must be Message.

Once the interface is modified to fit your requirements, you are ready to create your custom WCF client. This is, in fact, very easy. Creating a custom WCF client is simply a matter of inheriting ClientBase<TChannel> and delegate all method calls to base.Channel.

Consider this simple interface:

[ServiceContract(
    Namespace = "https://lookingsharp.wordpress.com/demo/",
    ConfigurationName = "IMyService")]
public interface IMyService
{
    [OperationContract(
        Action = "https://lookingsharp.wordpress.com/demo/IMyService/GetData",
        ReplyAction = "https://lookingsharp.wordpress.com/demo/IMyService/GetDataResponse")]
    Message GetData(Message request);
}

The code for the corresponding WCF client would the be:

public class MyServiceClient : ClientBase<IMyService>, IMyService
{
    public Message GetData(Message request)
    {
        return base.Channel.GetData(request);
    }
}

This client will by default use the configuration called IMyService, generated by Svcutil along with the IMyService interface. Include this generated configuration in you application’s app.config file, and tweak it as you wish.

In part two I show, step by step, how to create a WCF client that does not rely on the default WCF message deserialization, and rather prints the raw XML content of the response message to the console.