Wakatta!

Like Eureka!, only cooler

Seven Languages in Seven Weeks Erlang Day 2

Second day with Erlang, this time to cover basic controls, and more functional goodies such as anonymous and higher-order functions, list functions and list comprehensions.

Erlang’s support for list processing is quite extensive (as it should be for a language with limited mutable state). Using is properly requires the kind of mental twist that is needed for effective (set oriented) SQL usage. But once acquired, it is hard to get back to generic imperative programming.

This chapter introduces various functions from the lists module: lists:map, and lists:foreach. I probably should not have used the former in yesterday’s “Counting to 10” exercise. The latter was more appropriate:

New version of Count module (count_2.erl) download
1
2
3
4
5
6
7
8
9
10
11
12
-module(count_2).
-export([count_to_10/0]).
-export([count_to/1]).
-export([count_up_to/1]).

count_to_10() -> count_to(10).

count_to(N) ->
  L = count_up_to(N),
  lists:foreach(fun(X) -> io:fwrite("~w~n", [X]) end, L).

count_up_to(N) -> lists:seq(1,N).

(also changed: I’m using the tilde format escape character, rather than backslash. Erlang is a child of Lisp, not C).

Exercises

Dictionary lookup

Just using pattern matching, the solution is very short an clean.

I named the module dictionary as the name dict was already used in the standard library. Erlang has a flat module naming system, so conflicts are bound to happen.

As it happens, Erlang lists:keyfind already implements this feature, as shown in lookup_alt.

Dictionary module (dictionary.erl) download
1
2
3
4
5
6
7
8
9
-module(dictionary).
-export([lookup/2]).
-export([lookup_alt/2]).

lookup(_, []) -> false;
lookup(K, [{K, V}|_]) -> V;
lookup(K, [_|T]) -> lookup(K, T).

lookup_alt(K, L) -> lists:keyfind(K, 1, L).

Testing the code:

Testing Module dictionary
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1> c(dictionary).
{ok,dictionary}
2> D = [{erlang, "a functional language"}, {ruby, "an OO language"}, {java, "a soso language"}].
[{erlang,"a functional language"},
 {ruby,"an OO language"},
 {java,"a soso language"}]
3> dictionary:lookup(erlang, D).
"a functional language"
4> dictionary:lookup(java, D).
"a soso language"
5> dictionary:lookup(c, D).
false
6> dictionary:lookup_alt(erlang, D).
{erlang,"a functional language"}

Computing prices

Once again, pattern matching makes it really easy to write such function. For extra credit (ok, no credit. Just for fun), I also wrote a function that depends on lists:map.

It just shows how easy it is to process lists of things in Erlang or any other decent functional language (one with pattern matching and list comprehension, that is).

Price module (price.erl) download
1
2
3
4
5
6
-module(price).
-export([compute_map/1, compute_lc/1]).

compute_map(L) -> lists:map(fun({Item, Quantity, Price}) -> {Item, Quantity * Price} end, L).

compute_lc(L) -> [{Item, Quantity * Price} || {Item, Quantity, Price} <- L].

Testing both functions, they return the same answer (always a good thing for functions meant to have identical meaning):

Testing Module price
1
2
3
4
5
6
7
8
9
10
11
1> c(price).
{ok,price}
2> Items = [{processor, 5, 200}, {memory, 4, 100}, {screen, 1, 1000}, {drive, 3, 150}].
[{processor,5,200},
 {memory,4,100},
 {screen,1,1000},
 {drive,3,150}]
3> price:compute_map(Items).
[{processor,1000},{memory,400},{screen,1000},{drive,450}]
4> price:compute_lc(Items).
[{processor,1000},{memory,400},{screen,1000},{drive,450}]

Playing Tic-Tac-Toe

I have to admit I cannot stand hard coding anything. Whenever I have a choice between hard coding and generating coding, I’ll pick the latter every single time.

So for the Tic-Tac-Toe exercise, I wrote code that computes the list of potential victory lines, even though the list for a board of 3 by 3 is much shorter. When Tic-Tac-Toe is finally played on 19 by 19 boards (as games for grown ups tend to be), my code will be ready…

I used a small utility module to transpose a matrix; the code is very similar, and indeed, lifted, from a previous Prolog exercise (the Sudoku one).

Matrix module (matrix.erl) download
1
2
3
4
5
6
7
8
9
10
11
12
-module(matrix).
-export([transpose/1]).

head([H|_]) -> H.
tail([_|T]) -> T.

transpose([]) -> [];
transpose([[]|_]) -> [];
transpose(M) ->
  Heads = lists:map(fun head/1, M),
  Tails = lists:map(fun tail/1, M),
  [Heads|transpose(Tails)].

Once thing to note: as in the export statement, a function name must include its arity when passed to higher order functions. See above for fun head/1 for instance.

Once this is defined, the code for Tic-Tac-Toe is fairly simple:

  • generate a list of lines on a board (tictactoe:make_winners) *
  • for each of these lines, determine if it belongs to a single player (tictactoe:check_align, called from tictactoe:check)
  • if any player owns a line, declare her the winner (tictactoe:check, using tictactoe:player)
  • otherwise, depending on whether there is any non player own square, declare the game over or undecided (tictactoe:check, using tictactoe:free).
Checking Tic-Tac-Toe (tictactoe.erl) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
-module(tictactoe).
-export([check/1]).
-export([make_winners/1]).

make_rows(N) -> [[{X,Y} || X <- lists:seq(1,N)] || Y <- lists:seq(1,N)].

make_lines(N) ->
  Rows = make_rows(N),
  Rows ++ matrix:transpose(Rows).
  
make_diag(N) -> [{X, N-X+1} || X <- lists:seq(1, N)].


make_winners(N) ->
  Lines = make_lines(N),
  Diag1 = make_diag(N),
  Diag2 = lists:map(fun({X,Y}) -> {4-X, Y} end, Diag1),
  [Diag1, Diag2] ++ Lines.

get_pos({X, Y}, B) -> lists:nth(X+3*(Y-1), B).

check_align(L, B) ->
  Line = lists:map(fun(P) -> get_pos(P, B) end, L),
  case Line of
      [x,x,x] -> x;
      [o,o,o] -> o;
      _ -> no_winners
  end.

player(x) -> true;
player(o) -> true;
player(_) -> false.

free(P) -> not player(P).

check(B) ->
  Checks = lists:map(fun(L) -> check_align(L, B) end, make_winners(3)),
  Win = lists:filter(fun player/1, Checks),
  case Win of
      [R|_] -> R;
      _ -> case lists:filter(fun free/1, B) of
          [_|_] -> no_winner;
          _ -> cat
      end
  end.

Testing is a bit tedious, because of the way the board is defined. First a winner on either diagonal is checked, then a draw, then an unfinished game:

Testing Module tictactoe
1
2
3
4
5
6
7
8
9
10
1> c(tictactoe).
{ok,tictactoe}
2> tictactoe:check([x, n, n, o, x, n, n, o, x]).
x
3> tictactoe:check([n, o, x, n, x, n, x, o, n]).
x
4> tictactoe:check([x, o, x, o, x, x, o, x, o]).
cat
5> tictactoe:check([o, x, n, x, x, o, n, o, n]).
no_winner

Wrapping Up Day 2

Erlang functional features make it very concise (adding currying would be sweet, though); the resulting code is short, readable, and flexible.

Despite a non mainstream pedigree, clearly this is a language whose design has been guided by actual usage and experience.

Comments