Functional Programming(Lec05)

yukita@k.hosei.ac.jp

•Function

A function can be defined via the Function form.

f = Function[x, x^2]

Function[x, x^2]

Let us check how it works.

f[10]

100

Let us do a systematic experiment using Map.

Map[f, Range[10]]

{1, 4, 9, 16, 25, 36, 49, 64, 81, 100}

A function can be defined in other forms.

g = #^2 &

#1^2 &

Map[g, Range[10]]

{1, 4, 9, 16, 25, 36, 49, 64, 81, 100}

Let us examine the internal representations of f and g.

FullForm[f]

Function[x, Power[x, 2]]

FullForm[g]

Function[Power[Slot[1], 2]]

•Note

The Function form is not a pure function. This can be seen from the following sequence of operations.

x = 100

100

f = Function[x, x^3]

Function[x, x^3]

Map[f, Range[10]]

{1, 8, 27, 64, 125, 216, 343, 512, 729, 1000}

We assigned value 100 to variable x  before using parameter x in the subsequent function definition. However, there was no interferance between them. This shows that the Function form is not a pure function but a kind of function like thing that returns a pure function.

Clear[x]

We can do the same task in a way where there is no possibility of this kind of confusion.

Clear[f]

f = Function[Slot[1]^3]

#1^3 &

Map[f, Range[10]]

{1, 8, 27, 64, 125, 216, 343, 512, 729, 1000}

•Map in more details

Clear[f]

Map[f, Range[10]]

{f[1], f[2], f[3], f[4], f[5], f[6], f[7], f[8], f[9], f[10]}

Map[f, Table[3 i + j, {i, 3}, {j, 3}]]

{f[{4, 5, 6}], f[{7, 8, 9}], f[{10, 11, 12}]}

Map[f, Table[3 i + j, {i, 3}, {j, 3}], 2]

{f[{f[4], f[5], f[6]}], f[{f[7], f[8], f[9]}], f[{f[10], f[11], f[12]}]}

a = {{"taro", "hanako", "musashi", "kojiro"},  {" ... t;mon", "tue", "wed", "thu", "fri", "sat"}}

{{taro, hanako, musashi, kojiro}, {thomas, gordon, henry}, {sun, mon, tue, wed, thu, fri, sat}}

Map[ToUpperCase, a]

{{TARO, HANAKO, MUSASHI, KOJIRO}, {THOMAS, GORDON, HENRY}, {SUN, MON, TUE, WED, THU, FRI, SAT}}

Although the default level in Map is 1, the result was produced with level 2. This is because the ToUpperCase function does the list mapping automatically. To see this, try the following.

ToUpperCase[a]

{{TARO, HANAKO, MUSASHI, KOJIRO}, {THOMAS, GORDON, HENRY}, {SUN, MON, TUE, WED, THU, FRI, SAT}}

Attributes[ToUpperCase]

{Listable, Protected}

•Apply

Clear[f, a, b, c]

Compare the Apply and Map functions.

Apply[f, {a, b, c}]

f[a, b, c]

Map[f, {a, b, c}]

{f[a], f[b], f[c]}

The difference is fully understood if we use the full form for {a,b,c}.

FullForm[{a, b, c}]

List[a, b, c]

So, {a,b,c} is equivalent to List[a,b,c]. Let us do the comparison again in this full form.

Apply[f, List[a, b, c]]

f[a, b, c]

Map[f, List[a, b, c]] // FullForm

List[f[a], f[b], f[c]]

Now, the difference is clear. Apply replaces the head part of its second argument with the first argument while Map makes the given function plunge into lower level of the list. We will more clearly understand this by the following examples.

Apply[Plus, List[a, b, c]]

a + b + c

Apply[Plus, f[a, b, c]]

a + b + c

•Nest and NestList

Clear[f, x]

Nest[f, x, 3]

f[f[f[x]]]

NestList[f, x, 3]

{x, f[x], f[f[x]], f[f[f[x]]]}

f[x_] = x/(x - 1)

x/(-1 + x)

NestList[f, x, 4] // Simplify

{x, x/(-1 + x), x, x/(-1 + x), x}

f @ f[x] // Simplify

x

•FixedPoint

Clear[f]

Guess what happens if a list of numbers is passed to the following function.

f[x_List] :=  If[Length[x] == 1,       x,       If[x[[ ... [Rest[x]]]]],            Join[{x[[1]]}, f[Rest[x]]]]]

f[Range[10]]

{2, 3, 4, 5, 6, 7, 8, 9, 10, 1}

f @ f[Range[10]]

{3, 4, 5, 6, 7, 8, 9, 10, 2, 1}

Nest[f, Range[10], 4]

{5, 6, 7, 8, 9, 10, 4, 3, 2, 1}

FixedPoint[f, Range[10]]

{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}

FixedPointList[f, Range[5]]

{{1, 2, 3, 4, 5}, {2, 3, 4, 5, 1}, {3, 4, 5, 2, 1}, {4, 5, 3, 2, 1}, {5, 4, 3, 2, 1}, {5, 4, 3, 2, 1}}

•Exercises

•Problem 1

We have implemented the bubble sort algorithm as a fixed point of the following function f.

f[x_List] :=  If[Length[x] == 1,       x,       If[x[[ ... [Rest[x]]]]],            Join[{x[[1]]}, f[Rest[x]]]]]

Reimplement f using Do-loop. Present an example that demonstrates the validity of your implementation.

Hint: Try to fill in the blanks.

f[x_List] :=  Module[{y = x, temp},  Do[If[y[[i]] < y[[i + 1]],      &n ... p;    (* do nothing *)],        {i, 1, O O O O O O}] ;  y]

•Solution

•Problem 2

Let g be a function that accepts a list of real numbers as its only argument and return a new list whose each element is replaced with the arithmetic mean of the neighboring elements, and whose both end elements are unchanged. Implement g. Then, using FixedPoint, obtain the result as follows.

data = Table[Random[] * 10, {i, 10}]

{4.751897704001604`, 4.479436033481209`, 5.383563339547997`, 1.034672815495567`, 0.85531029056 ... 08416135359502`, 0.36796587718083223`, 3.9760540593161124`, 9.366244680610086`, 6.36294780206063`}

result = FixedPoint[g, data]

{4.751897704001604`, 4.930903270452598`, 5.1099088369035925`, 5.28891440335459`, 5.46791996980 ... 646925536256593`, 5.8259311027075995`, 6.0049366691586075`, 6.183942235609618`, 6.36294780206063`}

Use the ListPlot function to visualize data and result.

•Solution

Converted by Mathematica  (May 20, 2003)