Click here to Skip to main content
13,149,589 members (50,072 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as


23 bookmarked
Posted 3 Feb 2009

Introduction to Functional Programming using F# - Part 2

, 3 Feb 2009
Rate this:
Please Sign up or sign in to vote.
This article explains the fundamentals of functional programming and lambda calculus


In part 1 of this article, I explained the fundamentals of functional programming using F#. In this section, I explain the advantages of functional programming and a comparison between procedural and functional. Finally, I explain why F# and other most popular functional languages are not pure functional.

Advantages of Functional Programming

More Corresponds to Mathematics

If you are coming from a mathematics background, most of the computer theories are strongly based on Mathematics. Though we are now living in the trend of rapid application development in which core and repetitive tasks are abstracted, we find solutions to the real world problems on top of these abstractions. Anyhow, problem-solving is based on mathematics. The level of complexity and the appliance of mathematics help to find more effective solutions. Functional programming correspond more to mathematics. With a set of denotational semantics (you can see some simple examples in part 1 of this article), functional languages enable you to resolve a problem in a much simpler and effective manner than procedural languages. This denotational semantics saves us from non-terminated loop statements, goto and break statements.

No Side-effect on Expression Evaluation

Functional languages are created in such a way as to mimic the Mathematical concepts, hence sub-expressions in an expression can be evaluated at any order. This characteristic enables functional languages as the choice for parallel programming.

Parameterized Types and Functions

In part 1 code 4, you can see that the function square requires a function as an argument with the following denotational semantic:

let square (f : int -> int) n = f(n) * f(n);;

Like this, all types and functions are clearly parameterized what needs to be given and what will be returned. This characteristic makes the code more general meaning that you can apply a functionality to different related types.

Short Order of Magnitude O(n)

As we know, that order of magnitude is used to compare the performance between different algorithms for solving a particular problems, smaller the value higher in the performance. In comparing with typical procedural, theoretically there is no assignments in functional programming. (See the examples in part 1). Procedural programs contains 90 percent of assignment statements. This is the major reason for them having higher O(n) than functional.

Real Modular Programming

OO programming allows to do modular programming, however, with the compliment of parameterized type and non-sequential properties allows to write real modular programming using functional languages. You can see code 4 of part 1 where a function is consumed in a modular manner.

Where Functional Overtakes Procedural?

It is surprising that most of the procedural languages have some of the functional behaviour. Where do functional languages overtake procedural? Let us see.

  • Procedural languages such as C, C++ have function pointers, there we can treat them as high order and curried functions. However, those function pointers are very limited and in these languages, you cannot create functions dynamically without any name.
  • Those procedural languages too support recursive. But, these are again handled by sequential statements like a human approaches the computer.

Lambda Calculus - Origin of Functional Programming

Since it corresponds more to mathematics, functional programming concept is based on the mathematics Lambda Calculus. It is a system to express any type of algorithm in a much more effective and simpler way. Generally, in maths and procedural languages, functions are to be defined and referred by an arbitrary name, for example:
f(x) = { 0 if x = 0
x2 sin(1/x2) if x ? 0 But in high order functions, insistence on naming is rather inconsistent.

For example:
Define x and y by x = 2 and y = 4, then we can say xx = y, in this there is no need to give any name to this function.

A function can be defined anonymously in lambda calculus which expresses the function's action on its argument. Lambda calculus provides a notation ? to define a function. For example, f(x) = x + 1 can be defined as ?x.x+1. Here, the name of the function and parameters are immaterial and this application of this function f(2) would be (?x.x+1) 2. In this example, ? is function, x is an argument and x+1 is the function body.

Definition of Lambda Calculus

If t is a lambda calculus, if

  • t = x where x ? variables
  • t = ?x.M where x ? variables and M is lambda expression
  • t = MN where M and N are lambda expression

Function application is left associative, for example f x y = (f(x))(y). Simple, a lambda calculus takes only one argument and applies it and returns one result. All the functional language behaviours (recursive, any order evolution, stateless) are actually the basic behaviours of lambda calculus.

There are two types of variables that exist in lambda:

  • Bound Variable: This falls within the function (or lambda) scope.
  • Free Variable: This takes the value from the expression in the function body.

For example, in ?x.xy, x is bound variable and y is free variable. In programming languages, we call these as argument or parameter and local variable respectively.

Why F# & Other Popular Functional Languages are NOT Pure Functional

The two immediate reasons are:

  • Immutability: As we learned, immutable data structure causes performance. However, for collection type, immutability is much better than the mutability. F# stands at this point.
  • Inapplicable Places: Functional programming concepts are not suitable for some scenarios, for example I/O operation and GUI. In these areas, imperative style is recommended.


In this part, we learned the advantages and fundamental concepts behind functional languages. Also, view my two part screen cast about Functional Programming with C# 3.0 at and, or, download both from


  • 3rd February, 2009: Initial post


This article, along with any associated source code and files, is licensed under The Creative Commons Attribution-ShareAlike 2.5 License


About the Author

M Sheik Uduman Ali
Architect Aditi
India India
Working as Architect for Aditi, Chennai, India.

My Website:

My Blog:

You may also be interested in...


Comments and Discussions

GeneralMy vote of 3 Pin
ChantiPDM11-Jan-11 10:39
memberChantiPDM11-Jan-11 10:39 
GeneralMy vote of 2 Pin
cebess16-Feb-09 1:12
membercebess16-Feb-09 1:12 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.170924.2 | Last Updated 3 Feb 2009
Article Copyright 2009 by M Sheik Uduman Ali
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid