# Rash thoughts about .NET, C#, F# and Dynamics NAV.

## Saturday, 12. December 2009

### Christmas tree in F#

Filed under: Diverses — Steffen Forkmann at 12:19 Uhr

Today I had way too much time on the train ­¤śē , so I wrote a little functional christmas tree program:

let line width j =

List.init

width

(fun i -> if abs(width/2 – i) <= j then "*" else " ")

let tree n =

List.init (n/2) (line n) @        // treetop

List.init 2 (fun _ -> line n 0) // trunk

let printTree =

tree >> Seq.iter (Seq.fold (+) "" >> printfn "%s")

printTree 11

```    *
***
*****
*******
*********
*
* ```
Tags: ,

## Thursday, 2. July 2009

### F# BootCamp – Questions and Answers – part IV – Structural comparison

Filed under: English posts,F# — Steffen Forkmann at 17:37 Uhr

This is the third part in a ŌĆ£Questions and AnswersŌĆØ-series about the F# BootCamp in Leipzig. This time we will look at structural comparison and structural equality.

##### Question 6: Please describe the terms ŌĆ£Structural ComparisonŌĆØ and ŌĆ£Structural EqualityŌĆØ.

This was a simple question. Basically the answer is F# provides a default implementation for IComparable and .Equals() for all custom types. This default implementation compares all public fields of the two instances. LetŌĆÖs consider some samples:

##### Tuples
```let a = 3,4,"foo"
let b = 3,4,"bar"

printfn "a > b = %b" (a > b) // true
printfn "a < b = %b" (a < b) // false```
##### Records
```type MySimpleRecord =
{ a: int;
b: int;}

type MyCompositeRecord =
{ x: string;
y: int;
z: MySimpleRecord}

let a =
{ x = "Test";
y = 3;
z = {a = 1; b = 4;}}

let b =
{ x = "Test";
y = 3;
z = {a = 1; b = 2;}}

// Structural comparison
printfn "a > b = %b" (a > b) // true
printfn "a < b = %b" (a < b) // false

printfn "Min(a,b) = %A" (min a b)
printfn "compare(a,b) = %d" (compare a b) ```
##### Lists
```let a = [3; 2; 4; 5]
let b = [3; 2; 4; 3; 3]

// Structural comparison
printfn "a > b = %b" (a > b) // true
printfn "a < b = %b" (a < b) // false

printfn "Min(a,b) = %A" (min a b)
printfn "compare(a,b) = %d" (compare a b)```
Tags: , ,

## Wednesday, 1. July 2009

### Extensibility of functions with lambdas (in F# and C#)

Filed under: English posts,F# — Steffen Forkmann at 16:02 Uhr

One of the nice properties of functional programming languages is the easy extensibility of custom functions. LetŌĆÖs consider a simple F# function (from ŌĆ£FAKE ŌĆō F# MakeŌĆØ) for a recursive directory copy:

```open System
open System.IO

/// Copies a directory recursive
/// Thanks to Robert Pickering http://strangelights.com/blog/
///  param target: target directory : string
///  param source: source directory : string
let CopyDir target source =
Directory.GetFiles(source, "*.*", SearchOption.AllDirectories)
|> Seq.iter (fun file ->
let newFile = target + file.Remove(0, source.Length)
printf "%s => %s" file newFile
Directory.CreateDirectory(Path.GetDirectoryName(newFile)) |> ignore
File.Copy(file, newFile, true))```

If we want to allow users to set custom file filters, we can add a third parameter:

```/// Copies a directory recursive
/// and allows to filter the files
/// Thanks to Robert Pickering http://strangelights.com/blog/
///  param target: target directory : string
///  param source: source directory : string
///  param filterFile: FilterFunction: string -> bool
let CopyDirFiltered target source filterFile =
Directory.GetFiles(source, "*.*", SearchOption.AllDirectories)
|> Seq.filter filterFile
|> Seq.iter (fun file ->
let newFile = target + file.Remove(0, source.Length)
printfn "%s => %s" file newFile
Directory.CreateDirectory(Path.GetDirectoryName(newFile)) |> ignore
File.Copy(file, newFile, true))```

Now we can define some filter functions:

```/// Exclude SVN files (path with .svn)
/// excludeSVNFiles: string -> bool
let excludeSVNFiles (path:string) = not <| path.Contains ".svn"

/// Includes all files
/// allFiles: string -> bool
let allFiles (path:string) = true```

Now it is possible to use CopyDirFiltered in the following ways:

```/// Copies all files <=> same as CopyDir
CopyDirFiltered "C:\\target" "C:\\source" allFiles

/// Copies all files except SVN files
CopyDirFiltered "C:\\target" "C:\\source" excludeSVNFiles

/// Copies all files only if random number <> 2
let r = new Random()
CopyDirFiltered "C:\\target" "C:\\source" (fun path -> r.Next(5) <> 2)```
##### Extensibility of functions in C#

Of course we can do the same thing in C# 3.0:

```/// <summary>
/// Copies a directory recursive
/// and allows to filter the files
/// </summary>
/// <param name="target">The target.</param>
/// <param name="source">The source.</param>
/// <param name="fileFilter">The file filter.</param>
public static void CopyDirFiltered(string target, string source,
Func<string, bool> fileFilter)
{
string[] allFiles = Directory.GetFiles(
source, "*.*", SearchOption.AllDirectories);
foreach (string file in from f in allFiles
where fileFilter(f)
select f)
{
string newFile = target + file.Remove(0, source.Length);
Console.WriteLine("{0} => {1}", file, newFile);
Directory.CreateDirectory(Path.GetDirectoryName(newFile));
File.Copy(file, newFile, true);
}
}```

Now it is easy to use the C# function with lambdas:

ŌĆ£A lambda expression is an anonymous function that can contain expressions and statements, and can be used to create delegates or expression tree types.ŌĆØ

[MSDN]

```Func<string, bool> filterSVN = x => !x.Contains(".svn");
Func<string, bool> allFiles = x => true;

/// Copies all files <=> same as CopyDir
CopyDirFiltered("C:\\target", "C:\\source", allFiles);

/// Copies all files except SVN files
CopyDirFiltered("C:\\target", "C:\\source", filterSVN);

/// Copies all files only if random number <> 2
var r = new Random();
CopyDirFiltered("C:\\target", "C:\\source", path => r.Next(5) != 2);```

Keeping this simple technique in mind allows to create very flexible functions.

Tags: , , ,

## Wednesday, 24. June 2009

### F# BootCamp – Questions and Answers – part III – Lazy evaluation

Filed under: English posts,F#,Informatik — Steffen Forkmann at 11:27 Uhr

This is the third part in a ŌĆ£Questions and AnswersŌĆØ-series about the F# BootCamp in Leipzig. This time we will look at lazy evaluation.

##### Question 5 ŌĆō What is the difference between ŌĆ£Lazy EvaluationŌĆØ and ŌĆ£Eager evaluationŌĆØ?

Lazy evaluation is a technique of delaying a computation until the result is required. If we use eager evaluation an expression is evaluated as soon as it gets bound to a variable.

One participant answered that lazy evaluation is used in most programming languages to calculate boolean expressions faster. For instance in the expression ŌĆ£x() or y()ŌĆØ the function y() is never called if x() returns true.

Of course this answer is correct, but this "short-circuit evaluation" is only a special case of lazy evaluation. The program would also work correctly without it. But if we want to define an infinite sequence then we can not use eager evaluation. LetŌĆÖs look at an example:

```// val fibs: seq<int>
let fibs = (1, 1) |> Seq.unfold(fun (n0, n1) -> Some(n0, (n1, n0 + n1)))```

We do not need to understand the concrete syntax of this code here. WeŌĆÖll discuss this later. LetŌĆÖs just say fibs is bound to an infinite sequence (IEnumerable<int>) of Fibonacci numbers. You could also write this in C#:

```/// <summary>
/// Infinite sequence of Fibonacci numbers.
/// </summary>
public static IEnumerable<int> Fibs()
{
var n0 = 1;
var n1 = 1;
while(true)
{
yield return n0;
var t = n1;
n1 = n1 + n0;
n0 = t;
}
}```

The trick is IEnumerable evaluates the elements lazy. Only at the time we take an element from the sequence the element will be computed:

```fibs
|> Seq.take 10
|> Seq.to_list
|> printfn "%A" // prints [1; 1; 2; 3; 5; 8; 13; 21; 34; 55]```

If we would use eager evaluation then ŌĆ£Seq.takeŌĆØ would never been called. But we can go one step further. If we want to get the first 10 even-valued terms in the Fibonacci sequence, we can write this code:

```fibs
|> Seq.filter (fun fib -> fib % 2 = 0) // lazy (via pipe)
|> Seq.take 10                         // lazy (via pipe)
|> Seq.to_list                         // eager
|> printfn "%A"

// prints [2; 8; 34; 144; 610; 2584; 10946; 46368; 196418; 832040]```

This would be a little bit tricky if we use eager evaluation, but of course this nice laziness comes with some costs for storing intermediate results (and code). So eager evaluation is still often the better choice and sometimes (e.g. DateTime.Now()) it makes no sense to use lazy evaluation ŌĆō at least not if we donŌĆÖt reevaluate the function.

Tags: , ,

## Tuesday, 2. June 2009

### F# BootCamp – Questions and Answers – part I – Introduction

Filed under: .NET,F#,Informatik,Mathematik,Steffen,TechTalk,Tools — Steffen Forkmann at 10:34 Uhr

Last Friday we had a fantastic LearningByTeaching F# BootCamp in Leipzig. Each attendee got homework and had to solve one theoretical question and one programming task. For this two questions they had to present their results to the rest of us and after this I gave my solution in addition.

It was very interesting to see the different strategies and solutions. In this post series I will discuss the questions and some of the possible solutions.

##### Question 1 – What is ŌĆ£Functional ProgrammingŌĆØ in contrast to ŌĆ£Imperative ProgrammingŌĆØ?

This seems to be an easy question but in fact, the attendees had some problems to give a short definition of both functional and imperative Programming.

I didnŌĆÖt find a formal definition of the terms so my intention was to clarify things with an informal description like the one from Wikipedia:

ŌĆ£In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state. Functional programming has its roots in the lambda calculus, a formal system developed in the 1930s to investigate function definition, function application, and recursion.ŌĆØ

Wikipedia

I think the main aspect here is: avoiding state and mutable data. Maybe the words ŌĆ£side-effectŌĆØ, recursion and ŌĆ£higher-order functionsŌĆØ could also be used, but they will be discussed in later questions.

On my slides I covered the following aspects:

• Functional programming is a paradigm
• FP tries to avoid shared state
• Functions are first class citizens, enabling higher-order functions
• Pure functions
• no side-effects
• Results calculated only on the basis of input values
• No information storage
• Deterministic
• ==> Debugging and testing benefits
• ==> Thread-safe without locking of data

For further reading I recommend "Conception, evolution, and application of functional programming languages" (Paul Hudak) or ŌĆ£Functional Programming For The Rest of UsŌĆØ (Slava Akhmechet).

##### Question 2 ŌĆō Explain the keyword ŌĆ£letŌĆØ. In F# we are talking about ŌĆ£let-bindingsŌĆØ and not ŌĆ£variablesŌĆØ. Why?

Basically you use the let keyword to bind a name to a value or function. It wonŌĆÖt change any more, so a binding is immutable at default and not ŌĆ£variableŌĆØ.

I was glad to see the presenter showing the problem with an imperative assignment like
x = x + 1, which from a mathematical view is paradoxical. There is no x which equals x plus one. I think choice of the F# assignment operator is better than equality sign. The statement x <- x + 1 shows the real intention. I want to put the old value of x plus one into the memory cell where x was before.
So we discussed some basic terms like scope and mutability here and I showed how we can explicitly tell the compiler to use mutable data using reference cells or mutable variables.

Maybe it wasnŌĆÖt that good idea to discuss ŌĆ£Imperative F#ŌĆØ at such an early point (without knowing any functional concepts), but it showed the contrast to immutable let-Bindings.

##### Question 3 ŌĆō What is a recursion? Try to explain why we often want recursions to be tail-recursive. Hint: Look at the following C# program. What is the problem and how could you solve it?
```public static Int64 Factorial(Int64 x)
{
if (x == 0) return 1;
return x*Factorial(x - 1);
}
ŌĆ”
Factorial(10000);```

It was interesting to see that nearly nobody expected a real problem in such a short code snippet. Some attendees thought this program might have an integer overflow ŌĆō but only the presenters (they tested the program) gave the right answer (stack overflow). In fact they gave a very good and deep explanation about recursion and the problem on the stack.

As the question hinted, a possible solution was adding a accumulator variable and using tail-recursion:

```public static BigInt FactorialTailRecursive(BigInt x, BigInt acc)
{
if (x == BigInt.Zero) return acc;
return FactorialTailRecursive(x - BigInt.One, x*acc);
}```

Unfortunately this "trick" doesn’t work in C# (the compiler doesnŌĆÖt use tail calls), but it leads to the correct idea ŌĆō converting it to a while-loop. Of course I would prefer the tail-recursive F# solution:

```/// Tail recursive version
let factorial x =
let rec tailRecursiveFactorial x acc =
match x with
| y when y = 0I -> acc
| _ -> tailRecursiveFactorial (x-1I) (acc*x)

tailRecursiveFactorial x 1I```

We didnŌĆÖt cover continuation passing here. I think this could be something for an advanced session.

Next time I will discuss the rest of the introduction and show some of the first programming tasks.

Tags: , , ,