Skip to content

Latest commit

 

History

History
249 lines (203 loc) · 8.77 KB

ch07-higher-order-functions-and-lists.asciidoc

File metadata and controls

249 lines (203 loc) · 8.77 KB
Raw

Higher Order Functions and List Comprehensions

Note
 You can learn more about working with higher order functions in Chapter 9 of Erlang Programming, Section 3.4 of Programming Erlang, Section 2.7 of Erlang and OTP in Action, and Chapter 6 of Learn You Some Erlang For Great Good!. List comprehensions are in Chapter 9 of Erlang Programming, Section 3.6 of Programming Erlang, Section 2.9 of Erlang and OTP in Action, and Chapter 1 of Learn You Some Erlang For Great Good!.

Étude 7-1: Simple Higher Order Functions

In calculus, the derivative of a function is "a measure of how a function changes as its input changes" (Wikipedia). For example, if an object is traveling at a constant velocity, that velocity is the same from moment to moment, so the derviative is zero. If an object is falling, its velocity changes a little bit as the object starts falling, and then falls faster and faster as time goes by.

You can calculate the rate of change of a function by calculating: (F(X + Delta) - F(X)) / Delta, where Delta is the interval between measurements. As Delta approaches zero, you get closer and closer to the true value of the derivative.

Write a module named calculus with a function derivative/2. The first argument is the function whose derivative you wish to find, and the second argument is the point at which you are measuring the derivative.

What should you use for a value of Delta? I used 1.0e-10, as that is a small number that approaches zero.

Here is some sample output.

1> c(calculus).
{ok,calculus}
2> F1 = fun(X) -> X * X end.
#Fun<erl_eval.6.82930912>
3> F1(3).
9
4> calculus:derivative(F1, 3).
6.000000496442226
5> calculus:derivative(fun(X) -> 3 * X * X + 2 * X + 1 end, 5).
32.00000264769187
6> calculus:derivative(fun math:sin/1, 0).
1.0

  • Line 3 is a test to see if the F1 function works.

  • Line 5 shows that you don’t have to assign a function to a variable; you can define the function in line.

  • Line 6 shows how to refer to a function in another module. You start with the word fun followed by the __module__:__function__/__arity__.

Étude 7-2: List Comprehensions and Pattern Matching

Is it possible to use pattern matching inside a list comprehension? Try it and find out.

Presume you have this list of people’s names, genders, and ages:

People = [{"Federico", $M, 22}, {"Kim", $F, 45}, {"Hansa", $F, 30},
{"Tran", $M, 47}, {"Cathy", $F, 32}, {"Elias", $M, 50}].

Part One

In erl (or in a module, if you prefer), write a list comprehension that creates a list consisting of the names of all males who are over 40. Use pattern matching to separate the tuple into three variables, and two guards to do the tests for age and gender.

Part Two

When you use multiple guards in a list comprehension, you get the moral equivalent of and for each condition you are testing. If you want an or condition, you must test it explicitly. Write a list comprehension that selects the names of all the people who are male or over 40. You will need one guard with an or; you may also use orelse.

Note
 Because or has higher priority than comparison operators like < and ==, an expression like X > 5 or X < 12 will generate an error, as Erlang interprets it to mean X > (5 or X) < 12. Use parentheses to force the correct evaluation: (X > 5) or (X < 12). If you use orelse, which has a lower priority than the comparison operators, you don’t need the parentheses, though it doesn’t hurt to have them. Another advantage of orelse is that it doesn’t do any unnecessary comparisons.

Étude 7-3: Using lists:foldl/3

Add mean/1 and stdv/1 functions to the stats module which you created in Étude 6-2 to calculate the mean and standard deviation for a list of numbers.

1> c(stats).
{ok,stats}
2> stats:mean([7, 2, 9]).
6.0
3> stats:stdv([7, 2, 9]).
3.605551275463989

The formula for the mean is simple; just add up all the numbers and divide by the number of items in the list (which you may find by using the length/1 function).Use lists:foldl/3 to calculate the sum of the items in the list.

The following is the algorithm for calculating the standard deviation. Presume that N is the number of items in the list.

  1. Add up all the numbers in the list (call this the sum).

  2. Add the squares of the numbers in the list (call this the sum of squares).

  3. Multiply N times the sum of squares.

  4. Multiply the sum times itself.

  5. Subtract the result of step 4 from the result of step 3.

  6. Divide the result of step 5 by N * (N - 1).

  7. Take the square root of that result.

Thus, if your numbers are 7, 2, and 9, N would be three, and you would do these calculations:

  • The sum is 7 + 2 + 9, or 18.

  • The sum of squares is 49 + 4 + 81, or 134.

  • N times the sum of squares is 134 * 3, or 402.

  • The sum times itself is 18 * 18, or 324.

  • 402 - 324 is 78.

  • 78 divided by (3 * (3 - 1)) is 78 / 6, or 13.

  • The standard deviation is the square root of 13, or 3.606.

In your code, you can do steps three through seven in one arithmetic expression. You’d have variables in your expression rather than constants, of course.

math:sqrt((3 * 134 - 18 * 18)/(3 * (3 - 1))

Use lists:foldl/3 to calculate the sum and the sum of squares. Bonus points if you can calculate both of them with one call to lists:foldl/3. Hint: the argument for the accumulator doesn’t have to be a single number. It can be a list or a tuple.

Étude 7-4: Using lists:split/2

Use erl -man lists to see how the lists:split/2 function works, or try the following example and see if you can figure it out. Experiment to see what happens if the first argument is zero.

1> lists:split(4, [110, 220, 330, 440, 550, 660]).
{[110,220,330,440],[550,660]}

Use lists:split/2 and lists:foldl/3 to rewrite the dates:julian/1 function from Étude 6-3. Hint: you’ll use those functions when calculating the total number of days up to (but not including) the month in question.

Étude 7-5: Multiple Generators in List Comprehensions

Back to list comprehensions. You can have more than one generator in a list comprehension. Try this in erl:

1> [X * Y || X <- [3, 5, 7], Y <- [2, 4, 6]].
[6,12,18,10,20,30,14,28,42]

Using what you’ve learned from this example, write a module named cards that contains a function make_deck/0. The function will generate a deck of cards as a list 52 tuples in this form:

[{"A","Clubs"},
 {"A","Diamonds"},
 {"A","Hearts"},
 {"A","Spades"},
 {2,"Clubs"},
 {2,"Diamonds"},
 {2,"Hearts"},
 {2,"Spades"},
 ...
 {"K", "Clubs"},
 {"K", "Diamonds"},
 {"K", "Hearts"},
 {"K", "Spades"}]
Note

When you run this function, your output will not show the entire list; it will show something that ends like this. Don’t freak out.

{7,"Clubs"},
{7,"Diamonds"},
{7,[...]},
{7,...},
{...}|...]

If you want to see the full list, use this function.

show_deck(Deck) ->
  lists:foreach(fun(Item) -> io:format("~p~n", [Item]) end, Deck).

Étude 7-6: Explaining an Algorithm

You need a way to shuffle the deck of cards. This is the code for doing a shuffle, taken from the Literate Programs Wiki.

shuffle(List) -> shuffle(List, []).
shuffle([], Acc) -> Acc;
shuffle(List, Acc) ->
  {Leading, [H | T]} = lists:split(random:uniform(length(List)) - 1, List),
  shuffle(Leading ++ T, [H | Acc]).
----

Wait a moment. If I've just given you the code, what's the purpose
of this étude? I want you to understand the code. The object of this
étude is to write the documentation for the algorithm.
If you aren't sure what the code does, try adding some
+io:format+ statements to see what is happening. If you're totally
stuck, http://en.literateprograms.org/Fisher-YatesShuffle_%28Erlang%29[see the explanation from Literate Programs site].

<<SOLUTION07-ET06,See a suggested solution in Appendix A.>>