functional_smoothing.html

Functional Smoothing - A case study in functional programming

Ken Levasseur
Mathematical Sciences
UMass Lowell
kenneth_levasseur@uml.edu

From Wikipedia's article on functional programming (January 2007): Functional programming is a programming paradigm that conceives computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast with imperative programming, which emphasizes changes in state.

Is that clear? Maybe an example will make it clearer. If you don't have any functional programming experience, take at a few minutes to think about how you would solve this problem.

Problem: Write a program that takes a list of numbers as an input and generates a list for which each entry is the average of the corresponding entry in the input and its left and right neighbors. For example, the fifth entry of the output will be the average of the fourth, fifth and sixth entry of the input. Assume the matrix wraps around so that the first entry has the last entry as its neighbor

Example data we'll use below.

[Graphics:HTMLFiles/functional_smoothing_4.gif]

Here is a functional programming solution to the problem

$smooth[data_] := Plus @@ ({RotateRight[#], #, RotateLeft[#]}/3&[data])$

The key part to this is the function {RotateRight[#],#,RotateLeft[#]}/3& which acts on the data list this way:

( {{e/3, a/3, b/3, c/3, d/3}, {a/3, b/3, c/3, d/3, e/3}, {b/3, c/3, d/3, e/3, a/3}} )

This is a list of three lists. The first is a cyclic rotation to the right of the data, divided by three. The second is just the original data divided by . The last list is a cyclic rotation to the left of the data, also divided by three. The expression Plus@@list, adds the entries in any list. For example Range[100] is the list of integers from 1 to 100 and to add them you can do this:

In the definition of smooth, this has the effect of adding coordinatewise to produce the desired list.

My preferred syntax uses piping: expressions such as x//f1//f2//f3, which are equivalent to f3[f2[f1[x]]]. The following function is identical to smooth. I just prefer to work from left to right.

$smoothPiped[data_] := data//{RotateRight[#], #, RotateLeft[#]}/3&//Plus @@ #&$

Test with symbols:

{a(1)/3 + a(2)/3 + a(6)/3, a(1)/3 + a(2)/3 + a(3)/3, a(2)/3 + a(3)/3 + a(4)/3, a(3)/3 + a(4)/3 + a(5)/3, a(4)/3 + a(5)/3 + a(6)/3, a(1)/3 + a(5)/3 + a(6)/3}

Test of piped definition:

{a(1)/3 + a(2)/3 + a(6)/3, a(1)/3 + a(2)/3 + a(3)/3, a(2)/3 + a(3)/3 + a(4)/3, a(3)/3 + a(4)/3 + a(5)/3, a(4)/3 + a(5)/3 + a(6)/3, a(1)/3 + a(5)/3 + a(6)/3}