Sunday, March 6, 2011

Use sequence to solve the problem

When I went through a problem which requires to find the maximum of difference between two elements. The 2nd element's index must greater than the 1st element. So the way to solve the problem is two steps:

1. generate the sequence
2. filter the element which meet the requirement.

Before we start, somebody might want to ask, what is the performance of the code if we generate a whole list and then filter it. Do not worry, the sequence is not holding any memory or resource. It is just a lazy evaluation, so it will just return one element at one time.

Now we can concentrate on how to solve the sequence problem. We need to find a function to generate
    output = sequence of (element0, element1)
    input  = sequence of element

when we get the output, we need to find the element where (element1-element0) is the maximum.

the sequence is IEnumerable < (element, element) > by using yield return statement

for ( i = 0 ; i < input.Length; i++)
    for (j=i; j < input.Length; j++)
        yield return ( input[ j ], input[ i ] );

After we have this output sequence, we try to get the maximum by using output.Max(n => n.element1 - element.0)

The way I like functional programming is it more like human's thinking. The closer we think like human (or in a mathematical way), the less chance we generate an error. If we can represent a program in a mathematical way, it'll be much easier to verify it as well. In this solution, I still got some FOR loop, in this solution, let me come back later to get rid of this FOR.

Today seems a good time to get rid of FOR.

the idea is simple: we need two sequence, one is [1..count], the other has to use the element from first sequence as a parameter.

Enumerable.Range(0, count).SelectMany(i => Enumerable.Range(i, count - i).Select(j => new Tuple(i, j)));

No comments: