Marius Bancila’s Blog

Yesterday I wrote about list in F#. Today I’ll write about arrays, which unlike lists are a mutable flat storage and cannot be resized. That means you have to create a new array if you want to remove or add elements. Advantages include constant look-up time and the fact that they can store a large amount of data.

You can create a literal array in a similar way with the lists, placing the elements between [| |]:

let data1 = [|1;2;3;4|]
printfn "data1: %a" output_any data1

data1: [|1; 2; 3; 4|]

The empty literal array is [||].

To create an array you can either use Array.create or Array.init. They both create and initialize an array, but the second makes a lambda expression, which allows advance initialization possibilities. The following creates an array with 10 elements initialized to 1:

let data2 = Array.create 10 1
printfn "data2: %a" output_any data2

Here is the output:

data2: [|1; 1; 1; 1; 1; 1; 1; 1; 1; 1|]

The same can be achieved using Array.init:

let data3 = Array.init 10 (fun x -> 1)
printfn "data3: %a" output_any data3

data3: [|1; 1; 1; 1; 1; 1; 1; 1; 1; 1|]

But we can use Array.init to initialize the elements from 1 to N for instance:

let data4 = Array.init 10 (fun x -> x+1)
printfn "data4: %a" output_any data4

data4: [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10|]

The arrays are mutable data structures. Elements are accessed with .[] or .(). The following code shows how to set the elements of an array:

let data5 = Array.create 10 0
for i = 0 to (Array.length data5)-1 do
   data5.[i] <- i+1

printfn "data5: %a" output_any data5

data5: [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10|]

You can iterate over the elements of an array with Array.iter and Array.iteri, the second also providing access to the index of the elements.

data4 |> Array.iter (fun x -> printf "%d " x)
printfn ""

data4 |> Array.iteri (fun i x -> printfn "data4(%d) = %d" i x)

1 2 3 4 5 6 7 8 9 10
data4(0) = 1
data4(1) = 2
data4(2) = 3
data4(3) = 4
data4(4) = 5
data4(5) = 6
data4(6) = 7
data4(7) = 8
data4(8) = 9
data4(9) = 10

Retrieving the length of the array can either be done with Array.length arr or with arr.Length.

for i = 0 to data4.Length-1 do
   printfn "data4(%d) = %d" i data4.(i)

data4(0) = 1
data4(1) = 2
data4(2) = 3
data4(3) = 4
data4(4) = 5
data4(5) = 6
data4(6) = 7
data4(7) = 8
data4(8) = 9
data4(9) = 10

Like the lists, arrays provide mapping that creates a new array by applying a function on all the elements of an array (with Array.map) or two arrays (with Array.map2).

let data6 = data4 |> Array.map (fun x -> x*2)
printfn "data6: %a" output_any data6

let data7 = Array.map2 (fun x y -> x+y) data4 data6
printfn "data7: %a" output_any data7

data6: [|2; 4; 6; 8; 10; 12; 14; 16; 18; 20|]
data7: [|3; 6; 9; 12; 15; 18; 21; 24; 27; 30|]

A copy of an array can be done with Array.copy.

let data7 = Array.copy data6
printfn "data7: %a" output_any data7

data7: [|2; 4; 6; 8; 10; 12; 14; 16; 18; 20|]

Appending elements to an array is also possible with Array.append, but the result is a new array, created by concatenating two arrays.

let data8 = Array.append data7 [|100|]
printfn "data8: %a" output_any data8

data8: [|2; 4; 6; 8; 10; 12; 14; 16; 18; 20; 100|]

The last operation of arrays I'm going to mention here is the folding, which allows applying a function to all the elements of an array, threading an accumulator argument in the process. The following example shows how to compute the sum of the elements of an array.

let data9 = [|1;2;3;4|]
let sum1 = (Array.fold_left (fun acc x-> x + acc) 0 data9)
let sum2 = (Array.fold_right (fun acc x-> x + acc) data9 0)
printfn "sum1 = %d" sum1
printfn "sum2 = %d" sum2

sum1 = 10
sum2 = 10

Hits for this post: 17772 .

In this post I will talk about the lists in F#, one of the fundamental concepts of the language. What should be said from the very beginning is that list are imutable single linked list. That means whenever you change a list, a new list is created.

You can declare a list in the following ways:

let list1 = [1;2;3;4]
let list2 = 5::6::7::8::[]

To print the content of the list you can do this:

printfn “list1: %a” output_any list1
printfn “list2: %a” output_any list2

list1: [1; 2; 3; 4]
list2: [5; 6; 7; 8]

You can concatenate two lists with operator @:

let list3 = list1 @ list2
printfn "list3: %a" output_any list3

list3: [1; 2; 3; 4; 5; 6; 7; 8]

and you can append elements to the beginning of the list with operator ::

let list4 = -1::0::list3
printfn "list4: %a" output_any list4

list4: [-1; 0; 1; 2; 3; 4; 5; 6; 7; 8]

You can also use the List (defined in Microsoft.FSharp.Code) functionality to print a list by iterating over its elements:

list3: [1; 2; 3; 4; 5; 6; 7; 8]

1 2 3 4

The same can be achieved using the pipe operator:

list1 |> List.iter (fun x -> printf "%d " x)

You can also iterate and get the index of the list elements, with List.iteri:

list1 |> List.iteri (fun i x -> printfn "list1[%d] : %d " i x)

list1[0] : 1
list1[1] : 2
list1[2] : 3
list1[3] : 4

List have a special representation, a head followed by a tail, that is in turn another list (including empty list []). Let's consider the list [1;2;3]. It has the head 1, and the tail [2;3]. The tail, in turn, has the head 2 and the tail [3]. This tail has the head 3 and the tail [], which is the empty list.
You can see the head and tail of a list with List.hd and List.td:

printfn "head list1: %a" output_any (List.hd list1)
printfn "tail list1: %a" output_any (List.tl list1)

The ouput for list1 [1;2;3] is:

head list1: 1
tail list1: [2;3]

Enough with basic things. Let's try working with lists.

1. Minimum and maximum from a list

We can compute the maximum (or minimum) of a list using the following algorithm:

• if the list is empty, indicate error
• if the list has only one element, that is the maximum (or minimum)
• if the list has at least to elements, compute the maximum between that element and the maximum from the rest of the list

That sounds like a recursive operation, which can be simply put in F# like this:

let rec greatest_element l =
    match l with
    | [] -> failwith "empty list"
    | [x] -> x
    | x::rest -> max x (greatest_element rest)

let rec smallest_element l =
    match l with
    | [] -> failwith "empty list"
    | [x] -> x
    | x::rest -> min x (smallest_element rest)

We can use that like this:

let list1 = [1;2;3;4;-4;-3;-2;-1]
let list2 = []   

try
   printfn "maximum from list1: %d" (greatest_element list1)
   printfn "minimum from list1: %d" (smallest_element list1)

   printfn "maximum from list2: %d" (greatest_element list2)
   printfn "minimum from list2: %d" (smallest_element list2)
with
   Failure msg ->
      printfn "Error: %s" msg

and the output would be:

maximum from list1: 4
minimum from list1: -4
Error: empty list

2. Reversing a list

How would we reverse a list? We should take the last element and append to it the one before the last. To the new list we append the one before the one before the end, etc. That again sounds recursive.

let rec revert_list l =
   match l with
   | [] -> []
   | x::rest -> (revert_list rest) @ [x]

let list1 = [1;2;3;4;-4;-3;-2;-1]

printfn "list1: %a" output_any list1
printfn "list2: %a" output_any (revert_list list1)

And here is the output:

list1: [1; 2; 3; 4; -4; -3; -2; -1]
list2: [-1; -2; -3; -4; 4; 3; 2; 1]

3. Inserting in a list

So how could we insert an element in a list, before or after a specified element? We can use the following algorithm:

• if the list is empty, the new list has one element (the one to insert)
• else, if the head is the element we are looking for, create a list, with the new element either before the head, or between the head and the tail
• else, if the head is not the element we are looking for, append the head to a list created by inserting the new element in the tail.

You got that right, recursion again.

let rec insert_after elem newelem l =
    match l with
    | [] -> [newelem]
    | x::rest -> if x = elem then
                    (x::newelem::rest)
                 else
                     x::(insert_after elem newelem rest)

let rec insert_before elem newelem l =
    match l with
    | [] -> [newelem]
    | x::rest -> if x = elem then
                    (newelem::x::rest)
                 else
                    x::(insert_before elem newelem rest)        

let list1 = [1;2;3;4;-4;-3;-2;-1]
let list2 = insert_after 4 6 list1
let list3 = insert_before 6 5 list2

printfn "list1: %a" output_any list1
printfn "list2: %a" output_any list2
printfn "list3: %a" output_any list3

And the output is:

list1: [1; 2; 3; 4; -4; -3; -2; -1]
list2: [1; 2; 3; 4; 6; -4; -3; -2; -1]
list3: [1; 2; 3; 4; 5; 6; -4; -3; -2; -1]

4. Removing elements from a list

As a last exercise, let's consider the removing of elements from a list. The following steps can be used to remove elements:

• if the list is empty, return an empty list
• if the list is not empty and the head meets the removing criteria, return a list obtained by reiterating the algorithm on the tail of the list
• if the list is not empty and the head does not meet the removing criteria, return a list obtained by appending the head to a list optained by reiterating the algorithm on the tail of the list

let rec remove_if l predicate =
    match l with
    | [] -> []
    | x::rest -> if predicate(x) then
                    (remove_if rest predicate)
                 else
                     x::(remove_if rest predicate)

The great thing about this implementation is that we can pass a lambda expression as a predicate, and use it to specify the criteria for removing elements. We can remove like that, for instance, the odd elements, or the even elements, or the negative elements. Here is some sample code:

let list1 = [1;2;3;4;-4;-3;-2;-1]

let list2 = remove_if list1 (fun x -> (abs x &&&1) = 1)
let list3 = remove_if list1 (fun x -> (abs x &&&1) = 0)
let list4 = remove_if list1 (fun x -> x < 0)

printfn "%a" output_any list1
printfn "%a" output_any list2
printfn "%a" output_any list3
printfn "%a" output_any list4

The output for this sample is:

[1; 2; 3; 4; -4; -3; -2; -1]
[2; 4; -4; -2]
[1; 3; -3; -1]
[1; 2; 3; 4]

I hope this will help you to get a grip on how you can work on lists in F#.

F# tutorial article list recursive Hits for this post: 16711 .

I started a few days ago to study F# and I was struggling with some things that were not good documented. I want to share what I’ve learn from that and hopefully that will help others.

After you download and install F# (available at http://research.microsoft.com/fsharp/release.aspx) a new project template will be made available in VS 2008 under Other Porject Types > F# Projects. This is called simply F# Project. When you use that to create a project, it generates a project file with the extension fsharpp. Suppose the project is named demo, then the project file is demo.fsharpp. Initially, it looks like this:

"General"
{
"ProjectIdGuid" = "{4ABF8CC3-3B48-4D3F-8D73-A8BAB9748402}"
}
"Configurations"
{
   "Debug|Win32"
   {
   "ProjectType" = "EXE"
   "OptLevel" = "Off"
   "StrongNamingLevel" = "None"
   "OutputPath" = ""
   "SearchPath" = ""
   "StrongNameFile" = ""
   "OutputBase" = ""
   "CustomCommandLine" = ""
   "CustomCompiler" = ""
   "DebugCheck" = "TRUE"
   "CustomCompilationCheck" = "FALSE"
   "DebugStartMode" = "0"
   "StartApp" = ""
   "StartAppPath" = ""
   "CustomStartupArguments" = ""
   }
   "Release|Win32"
   {
   "ProjectType" = "EXE"
   "OptLevel" = "3"
   "StrongNamingLevel" = "None"
   "OutputPath" = ""
   "SearchPath" = ""
   "StrongNameFile" = ""
   "OutputBase" = ""
   "CustomCommandLine" = ""
   "CustomCompiler" = ""
   "DebugCheck" = "FALSE"
   "CustomCompilationCheck" = "FALSE"
   "DebugStartMode" = "0"
   "StartApp" = ""
   "StartAppPath" = ""
   "CustomStartupArguments" = ""
   }
}
"Files"
{
}
"ProjStartupServices"
{
}
"Globals"
{
}

Now, you can add files to the project. The following image shows the available project items:

You can see among the items the following:

• F# Source File – a file with extension .fs containing implementation of types and functions
• F# Interface File – a file with extension .fsi containing declarations/signatures for the implementation in a .fs file
• ML/F# Source File – a file with extension .ml containing the implmenetation of a module
• ML/F# Interface File – a file with extension .mli containing the declaration/signature of one or more F# modules

An .ml file is just an .fs file, except that is should contain the implementation of a module. A module is a named collection of definitions. On the other hand, the difference between .mli and .fsi is that the first should be used for declaring modules.

So, let’s add a F# source file to our empty project, and let’s call it main.fs. Visual Studio will populate it with sample code, but ignore that and replace it with:

#light   

open System   

let main() =
   Console.WriteLine("hello world")
   Console.ReadKey() 

main()

Well, I’m not going into the details of the syntax here; it’s enough to say that this small program prints “hello world” in the console and waits for the user to press a key. (Build it and run it).But let’s say we want to put the code that prints the message in the console in a separate function:

#light 

open System 

let welcome() =
   Console.WriteLine("hello world") 

let main() =
   welcome()
   Console.ReadKey() 

main()

This has the same result as the previous program. But what if I want that in a separate file? Well, let’s create a new F# source file and call it hellos.fs, and put the code in it:

#light   

open System   

let welcome() =
   Console.WriteLine("hello world")

with the main.fs file looking like this:

#light 

open System 

let main() =
   welcome()
   Console.ReadKey() 

main()

If you build this project, you’ll get the following error:

main.fs(6,1): error: FS0039: The value or constructor ‘welcome’ is not defined.

Looks like the welcome function is not defined. Why? Because we should also have signature file (.fsi) that should declare what hellos.hs is defining. It’s just like a header file in C or C++, containing the declaration of functions or classes.Let’s add a file called hellos.fsi with the following content:

#light   

val welcome : unit -> unit

Building this yields the following error:

hellos.fsi(1,0): error: An implementation of file or module Hellos has already been given. Compilation order is significant in F# because of type inference. You may need to adjust the order of your files to place the signature file before the implementation. In Visual Studio files are type-checked in the order they appear in the project file, and to edit a project file right-click on the project node, unload the project, right-click again, edit the project file manually then the reload the project.

The error message is very explanatory: order of compilation is not ok:

C:\Program Files\FSharp-1.9.3.14\bin\fsc.exe –fullpaths –progress -Ooff -g -o “f:\marius\f#\demo\demo.exe” “main.fs” “hellos.fs” “hellos.fsi”

main.fs is compiled before hellos.fs, and this one before hellos.fsi. In fact, they should be completly reserved. The only way to do that is manually, so you have to unload the project, edit the project file and load it again.If you look at the project file, it contains this:

"Files"
{
   "main.fs"
   {
   "ProjRelPath" = "T"
   }
   "hellos.fs"
   {
   "ProjRelPath" = "T"
   }
   "hellos.fsi"
   {
   "ProjRelPath" = "T"
   }
}

The order of files must be changed to:

"Files"
{
    "hellos.fsi"
    {
    "ProjRelPath" = "T"
    }
    "hellos.fs"
    {
    "ProjRelPath" = "T"
    }
    "main.fs"
    {
    "ProjRelPath" = "T"
    }
}

But if you build it now, you again get an error:

main.fs(6,3): error: FS0039: The value or constructor ‘welcome’ is not defined.

The reason is that a module name is inferred from the name of the hellows.fsi file (by capitalizing it). Thus, we either use the fully qualified name Hellows.welcome(), or apen the Hellos module in file main.fs.

#light 

open System
open Hellos 

let main() =
    welcome()
    Console.ReadKey() 

main()

And now everything works again! You can change the extensions from .fsi to .mli and from .fs to .ml and have the same result.

Hits for this post: 9914 .

I’ve recently discovered a new nice feature in the natice debugger of Visual Studio 2008: the visualization of bit flags.

Let’s take this enumeration for example. Notice that each constant is basically a bit flag.

enum Weekdays
{
   Monday = 1,
   Thuesday = 2,
   Wednesday = 4,
   Thursday = 8,
   Friday = 16,
   Saturday = 32,
   Sunday = 64
};

If we used those bitfields like this:

int _tmain(int argc, _TCHAR* argv[])
{
   Weekdays weeekend = (Weekdays)(Saturday | Sunday);

   return 0;
}

The debugger shows them like this:

However, if the constants are not bit flags, they are not shown. If you declare the enum like this:

enum Weekdays
{
   Monday,
   Thuesday,
   Wednesday,
   Thursday,
   Friday,
   Saturday,
   Sunday
};

you won’t get that in the debugger.

debugger, flags, VC++, VS2008 Hits for this post: 16261 .

The beta version of the MFC Feature Pack (the extension to MFC 9 from Visual Studio 2008) contains an extended dialog class implementation, CDialogEx. What this brings new, publicly, is the ability to set the background of the dialog box to a color or an image.

A first new method allows to set a background color.

void SetBackgroundColor(COLORREF color, BOOL bRepaint = TRUE);

A second overloaded method allows to set an image on the background.

void SetBackgroundImage(
    HBITMAP hBitmap,
    BackgroundLocation location = BACKGR_TILE,
    BOOL bAutoDestroy = TRUE,
    BOOL bRepaint = TRUE);

BOOL SetBackgroundImage(
    UINT uiBmpResId,
    BackgroundLocation location = BACKGR_TILE,
    BOOL bRepaint = TRUE);

You can use it like this:

BOOL CDialogDemoDlg::OnInitDialog()
{
	CDialogEx::OnInitDialog();

	// ...

	HBITMAP bmp = ::LoadBitmap(AfxGetResourceHandle(), MAKEINTRESOURCE(IDB_BITMAP_LOGO));
	SetBackgroundImage(bmp, BACKGR_TILE);

	return TRUE;
}

What is very weird is that the only styles for the image are these:

enum BackgroundLocation
{
	BACKGR_TILE,
	BACKGR_TOPLEFT,
	BACKGR_TOPRIGHT,
	BACKGR_BOTTOMLEFT,
	BACKGR_BOTTOMRIGHT,
};

This implementation lacks two basic styles: Center and Stretch. I really don’t understand why they were not implemented. It’s much more likely to need an image centered or stretched that aligned at the bottom-left, for instance. Thus, I don’t see how good this class is if I have to override the entire painting myself if I need that functionality.

Here is an implementation of a dialog class that supports those styles.

Hits for this post: 19531 .

At the beginning of January, Microsoft released a beta version of MFC Feature Pack, an exstension to the MFC shipped with Visual Studio 2008. This feature pack allows developers to create applications with the look and feel of Office, Visual Studio and Internet Explorer. MFC application can now support:

• Office Ribbon
• Office 2003, XP and 2007 look and feel
• docking toolbars and panes in the Visual Studio style
• customizable toolbars and menus
• advanced GUI controls
• advaced MDI tabs and groups

I have published an article on www.codeguru.com about enabling Office 2007 style on a MDI application. The article is called MFC Feature Pack: An Introduction. I encourage you to read it. A Romanian version will be available soon at www.codexpert.ro.

article, beta, MDI, MFC, Office2007, ribbon Hits for this post: 30259 .

There are two way of converting strings to numerical values in .NET. The first one, supported since the first version of the platform, is the use of System.Convert class. It has methods like ToInt32, ToChar, ToDouble, ToDataTime, ToDecimal, etc.

Here is an example of converting string “123″ to numerical value 123.

string text = "123";
int number = Convert.ToInt32(text);
Console.WriteLine(number);

The catch with this method (and all the others from Convert) is that an exception is thrown, if the conversion failed.

 Unhandled Exception: System.FormatException: Input string was not in a correct f
 ormat.
    at System.Number.StringToNumber(String str, NumberStyles options, NumberBuffer&
        number, NumberFormatInfo info, Boolean parseDecimal)
    at System.Number.ParseInt32(String s, NumberStyles style, NumberFormatInfo info)
    at System.Convert.ToInt32(String value)
    at vs2008_cs_test.Program.Main(String[] args) in [...]\Program.cs:line 14

The correct use of ToIn32 is:

string text = "123s";
try
{
    int number = Convert.ToInt32(text);
    Console.WriteLine(number);
}
catch(FormatException e1)
{
    Console.WriteLine(e1.Message);
}
catch(OverflowException e2)
{
    Console.WriteLine(e2.Message);
}

Probably because too many programmers failed to try-catch these ToXXX methods and run into trouble, beginning with version 2.0 of the framework, a second method of converting string to numerical values was provided. All built-in numerical types (such as char, boolean, int, double, decimal, etc.) and others (such as DateTime, TimeSpan, IPAddress, etc.) have a static method called TryParse, that takes an in parameter the string to convert and and out parameter, the parsed value, and returns a boolean value to indicate success or failure.

string text = "123";
int number;
if(int.TryParse(text, out number))
{
    Console.WriteLine(number);
}
else
{
    Console.WriteLine("Could not parse string!");
}

Between the two, the second is recommended because is less error-prone. If an error occurs during parsing, you don’t get an exception so your program won’t crash. Moreover, the out value is set to the default value (false, 0, etc.).

Hits for this post: 11093 .