Ken has posted 2 posts at DZone. View Full User Profile

An Introduction to Functional Languages: Part Two

06.30.2009
| 11796 views |
  • submit to reddit

Previously we gave an introduction to functional languages. Now we take a look at some functional programming examples with F#.

F# is a language which was developed in the Microsoft Research and has graduated to a general public release. It is considered to be OCaml on .Net, as it has strong ties to OCaml. What makes it significant to me is its tool support. As an addition to the .Net family of languages it has fantastic language support with Visual Studio. This is rarely the case with other functional languages and specifically the languages that interest me (Clojure, Scala, Erlang). F# is also a hybrid language. It has object-orient support and has the ability to be integrated into a C# or other CLR language with relative ease. Currently F# is strong typed language that uses type interference and runs on the CLR. I haven’t experienced it yet, but all signs indicate that it can be run on Mono.

/// A very simple constant integer
let int1 = 1
/// A function on integers
let f x = 2*x*x - 5*x + 3
// A simple tuple of integers
let pointA = (1, 2, 3)
// A simple tuple of an integer, a string and a floating point number
let dataB = (1, "fred", 3.1415)

Listing 1: F# let examples from Tutorials.fs

The first important operator in F# is let. When dealing with variables as in int1, it is important to realize that this is not really an imperative variable it is a symbolic assignment. let can also assign variables to functions as with the example of function f. The last two code examples are assignments of tuples. pointA is a sequence of all the same type while dataB is a sequence of multiple types. Listing 2 will show some lists and introduce some new operators in F#

Sequences in F#

let listA = [ ]  			/// The empty list
let listB = [ 1; 2; 3 ] /// A list with 3 integers
let listC = 1 :: [2; 3] /// A list with 3 integers, note :: is the 'cons' operation
let listD = [5 .. 10] /// A list of number 15 through 10
let listE = listC @ listD /// A concatenated list of listC and listD

/// Compute the sum of a list of integers using a recursive function
let rec SumList xs =
match xs with
| [] -> 0
| h::t -> h + SumList t
/// Sum of a list
let sum = SumList [1; 2; 3]

Listing 2: F# list examples 

The next important element of F# is working with lists. The list assignment code in listing 2 is easily readable with two exceptions, the :: and @ operators. The :: operator is the cons operator is another way of describing a list. It is great when used in pattern match, which we will see later. The @ operator concatenates two lists.

The function SumList is a recursive function (defined by the rec keyword). It takes a sequence; if the sequence is empty (defined by []) then 0 is returned, else the head of the sequence (h) is added to the recursive call of the SumList of the remaining sequence. It is very common in F# to see match for a sequence with head or h as the variable representing the head and tail or t representing the remainder of the sequence.

Working with a collection can be quite different using functional techniques. In Java for instance, the approach is to iterate over the collection, with perhaps a “for each” loop. In Groovy we would use an each method passing in a closure. In F# there is a List module and it is possible to pass a function of the List module a sequence. The function would be applied on each element of the sequence. Notice the abstraction from iterations and branching.

let Square x = x*x               /// A function that squares its input
let squares1 = List.map Square [1; 2; 3; 4] // Map a function across a list of values

Listing 3: F# List map function 

The map function of the List module returns a new list (remember lists are immutable), with the same number of elements, each element being the square of the original list.

fun in F#

Another language feature of F# is the fun keyword. The fun keyword allows us to write an anonymous function on the fly. This would allow us to rewrite the functions from listing 3 as listing 4.

let squares2 = List.map (fun x -> x*x) [1; 2; 3; 4]

Listing 4: F# fun keyword defines a function on the fly

Of course this doesn’t allow for function reuse, but it can be a very convenient technique to simplify complex function creation.

Pipe operator in F#

For longer curried functions sometimes it is difficult to read what is happening or the order of execution. F# introduces an operator which makes this very easy, referred to as the pipe operator (|>). Listing 5 rewrites the functions from listing 3 and 4 one more time using the pipe operator.

let squares3 = [1; 2; 3; 4] |> List.map (fun x -> x*x) 

Listing 5: F# pipe operator

This time the sequence is piped into the List.map. In a currying way these pipe operators are often chained as in listing 6.

let SumOfSquaresUpTo n = 
[1..n]
|> List.map Square
|> List.sum

Listing 6: F# pipe operator chaining

Discriminated Unions in F#

Another feature of F# is the ability to create a discriminated union, which is a type which is limited to a defined set of types. For instance:

type exampleUnion =
| ex1 of int * string
| ex2 of bool
| ex3
// constructing instances
let a = ex1(42,"life")
let b = ex3
let f du =
// pattern matching
match du with
| ex1(x,s) -> printfn "x is %d, s is %s" x s
| ex2(b) -> printfn "b is %A" b
| ex3 -> printfn "three"

f a // x is 42, s is life
f b // three

Listing 7: F# Discriminated Union

Listing 7 defines a type that is limited to an integer string pair, a boolean or nil. This can be incredibly useful when leverage with pattern matching as evident in this listing. This is a great example of a technique that can’t be done with a switch statement. Where a switch statement must be for a specific type, pattern matching in F# is capable of switching on the type and providing easy access to that types payload.

Since we are pattern matching, lets end with the Fibonacci sequence implementation if F#.

let rec fib n =
match n with
| 1 -> n
| 2 -> 1
| n -> fib (n-1) + fib (n-2)

Listing 8: F# Fibonacci Function

This F# example is not as concise as the Mathematica example in listing 6, but close and very easy to read. Unlike Mathematica code however, F# is running on the CLR and is reasonably easy to integrate into a C# application.

Summary

This has been a whirlwind tour of the concept of functional programming. There are whole books written on the subject of functional programming and F# which don’t completely cover the subject. This article addresses some of the conceptual differences of functional development as faced by an individual who has worked solely with imperative languages. The concepts of lambda expressions, currying, closures and tuples were covered with sufficient detail to get started. F# examples were provided to put some of the defined terms to practice.

The need for functional programming is growing and the barrier to entry has never been smaller, its time to add functional programming to your knowledge portfolio. I would recommend taking a look at Scala or Clojure on the JVM or F# on the CLR.

Resources

Web

  • http://en.wikipedia.org/wiki/Functional_programming 
  • http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/default.aspx
  • http://msdn.microsoft.com/en-us/fsharp/default.aspx 
  • http://deepfriedbytes.com/podcast/episode-23-functional-programming-in-csharp-with-oliver-sturm/ 
  • http://www.strangelights.com/fsharp/wiki/

Books

  • Programming Scala by Venkat Subramaniam
  • Programming Clojure by Stuart Halloway
  • F# in a nutshell by Amanda Laucher and Ted Neward
  • Expert F# by Don Syme
  • Learning F# 1.0 by Chris Smith.
  • Functional Programming in C# by Oliver Sturm

 

Published at DZone with permission of its author, Ken Sipe.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Tags:

Comments

Otengi Miloskov replied on Tue, 2009/06/30 - 1:19pm

Scala? F# but that is a .net language you should post that on .Net. Or even take the examples with ocaml.

Dominique De Vito replied on Tue, 2009/06/30 - 2:40pm

After reading your second FP article, I thought about the Niklaus Wirth's book entitled : "Algorithms + Data Structures = Programs"

IMHO, it looks like FP languages are much more on the side of "Data Structures" than imperative languages which are more on the side of "Algorithms".

Indeed, FP languages are related to "Data Structures":
- they enable to make explicit the data structure through the creation of discriminated unions
- they make much more explicit pattern matching according to the data structure too
- they hide underlined implementation, the list implementation for example, and provide operators matching more clearly the structure of the data type (like the :: and the @ operator).

And while being more high-level, they hide details and give more place to the compiler to do its job, may be to generate code for a multi-core CPU.

Mark Haniford replied on Tue, 2009/06/30 - 3:26pm

It needs to be emphasized how great the "live editor" is for the F# addin in Visual Studio.  It feels like a scripting environmnent because of the type inferencing, but the background compiler knows when you've screwed something up (ala Eclipse, VS with resharper, etc).

kelly jason replied on Wed, 2009/10/21 - 11:04am

http://www.b2ubags.com/598-louis-vuitton-epi-leather-bucket-pm-m58992.html Louis Vuitton Epi Leather Bucket PM M58992 http://www.b2ubags.com/597-louis-vuitton-epi-leather-speedy-25-m5903e.html Louis Vuitton Epi Leather Speedy 25 M5903E http://www.b2ubags.com/596-louis-vuitton-epi-leather-speedy-30-m59022-black.html Louis Vuitton Epi Leather Speedy 30 M59022 black

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.