Channels ▼
RSS

.NET

Introduction to Functional Programming


Functional vs. Imperative

We can think of imperative programming as writing code that describes in exacting detail the steps the software must take to execute a given computation. These steps are generally expressed as a combination of statement executions, state changes, loops and conditional branches.

In contrast, functional programming looks at a program as a set of nested functions -- one "outer" function (the program) calling one or more "inner" functions to calculate a value to be returned as the result of the program. Functions take arguments and calculate return values, but do not maintain a "state of the program" per se.

Most modern programming languages support sufficient logic and data storage as to make them Turing complete. This means that in principle they can be used to write programs to solve any "computable" problem. F# is also a Turing complete language. The crux of choosing a language is not then one of capability, but of inherent applicability.

F# offers some advantages over other languages when working on certain classes of problems. Some general strengths of F# are as follows:

  • The signal-to-noise ratio is high. F# is economically expressed, e.g., favoring whitespace over other grouping symbols. As a result, your code ends up being quite succinct.
  • Powerful matching logic based not only on Boolean values but the "shape" and type of the data.
  • Built-in support for "lazy evaluation" of expressions.
  • Built-in support for writing thread-safe and asynchronous applications very simply via asynchronous workflows.

To help make things a little more concrete, and whet your appetite for the material to come, let's consider a few examples that help contrast how we'd look at and solve the same problem from the imperative vs. the functional perspective.

Example 1: Filtering a List

Let's suppose we have a list of 10000 employee records in a list, and we want to find all the employees who salary equals or exceeds 100,000 dollars. Taking the imperative approach, we would most likely write a for- or while-style loop, examining each employee's salary to see if it met our criteria. For each employee meeting the criteria, we would append the record to a growing list of matches. As you can see, we delineate each and every step in detail. In contrast, from a functional perspective, we would describe this solution as applying a filter (function) to a list with the goal of producing a new resulting list.

Example 2: Downloading Files Asynchronously

Asynchronous and parallel programming are difficult to do and even more difficult to get right. For example, to asynchronously download HTML pages from the Web via imperative languages requires us to create HTTP channels, issue asynchronous calls, write completion routines, and manage failures. Depending on the implementation, we may need to also manage our own threads. This results in a lot of complex, error-prone code. While we can't escape having to perform these tasks in some way, we can manage them much more succinctly and rigorously in functional languages by structuring and sequencing the calls using a concept called workflows.

Example 3: Customizing Algorithms

A classic problem that functional languages address elegantly is that of arbitrary value comparison. When your program needs to sort or compare values, it needs a mechanism to determine whether two values are "equal" or if one value is "less than" the other. When using naturally ordered elements, such as numbers or letters, the natural ordering applies. In many business-style programs, however, we need to compare elements that have no natural ordering, e.g., Employees, Automobiles, Tickets, Movies, Concerts, etc. In these types of applications, it's extremely convenient to supply a comparison or sorting function that can be subsequently executed against two elements. This is one of the most powerful capabilities of functional programming -- the ability to not only pass and return simple values, but the ability to pass and return functions.

To solve this problem in a functional language, you merely pass the main comparison function a "sort function" that it can use to compare two elements. Depending on the context of the application, or the types being sorted, the program can pass along different "sort functions" without changing the main routine whatsoever. Functional languages tend to exhibit this compositionality in most aspects of their design and, ahem, function.

To address this problem in traditional imperative languages, we'd need to resort to function pointers or similar constructs. Again, this is possible to do, but not as clean or elegant as it can be. We should note here that C# now ships with some functional constructs, including anonymous functions and lambda expressions, which help to elegantly address this type of problem.

Example 4: Creating Infinite Sequences

There are certain data sets that are "naturally infinite", e.g., the set of all prime numbers, making their complete calculation impossible. Functional languages employ mechanisms such as lazy evaluation and delayed computation to make infinite sets both representable and efficiently computed in on-demand fashion. Again, while you can accomplish the same things in non-functional languages, the imperative implementations tend to be "less natural" and more convoluted.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video