Erlang Programming Exercise: 3-7
For this exercise we get to rewrite Exercise 3-4 using the lists module. The author asks us how much shorter the newer version is from the first version. My old version is 39 lines long while my new version is 30 lines. It's a nice savings, but I was hoping for more. The change that I like the most, is that I don't have any a recursion. I can see at a glace what the functions are doing now.
-module(threeseven).
-export([new/0, destroy/1, write/3, delete/2, read/2, match/2]).
new() ->
[].
destroy(_Db) ->
ok.
delete(Key, Db) ->
lists:keydelete(Key, 1, Db).
write(Key, Element, Db) ->
NewDb = delete(Key, Db),
[{Key, Element}|NewDb].
read(Key, List) ->
case lists:keyfind(Key, 1, List) of
false -> {error, instance};
{Key, Value} -> {ok, Value}
end.
match(Element, Db) ->
Matcher = fun(Elem) ->
case Elem of
{_Key,Element} -> true;
_Other -> false
end
end,
lists:filter(Matcher, Db).
It took me a while to get the syntax for the case statement and the fun. I found it confusing why I didn't need any punctuation after the last case statement or the end token.
I think it's important to point out how valuable the erlang man pages are. I was able to find the information I needed about the lists module by running this at the command line:
erl -man lists
It gives you a nice bit of documentation about the lists module.
Cheers,
-Halzy
Erlang Programming Exercise: 3-6 (quicksort)
Quicksort! Wow, it's been forever since I've had to implement a sorting routine. Here are the instructions:
Quicksort: The head of the list is taken as the pivot; the list is then split according to those elements smaller than the pivot and the rest. These two lists are then recursively sorted by quicksort, and joined together, with the pivot between them.
-module(threesix).
-export([quicksort/1]).
quicksort(Pivot, Left, Right, []=_Src) ->
{Left, Pivot, Right};
quicksort(Pivot, Left, Right, [H|T]=_Src) when H < Pivot ->
quicksort(Pivot, [H|Left], Right, T);
quicksort(Pivot, Left, Right, [H|T]=_Src) ->
quicksort(Pivot, Left, [H|Right], T).
quicksort([]) ->
[];
quicksort([H|T]=_List) ->
{Left, Pivot, Right} = quicksort(H, [], [], T),
quicksort(Left) ++ [Pivot] ++ quicksort(Right).
In chapter 2 of Erlang Programming the author talks about how the ++ operator isn't very efficient. So I tried swapping it out with my previous implementation of concatenate. I then ran some timing tests and found that ++ was faster than my concatenate. 
A bit disturbed by this I went back to read the warnings again and found that the author was warning against using the ++ operator to prepend single items to a list. So you shouldn't use [1] ++ [2,3,4] in place of [1|[2,3,4]].
To test this out, I went back and modified my reverse function to use the ++ operator:
reverseA(To, []) ->
To;
reverseA(To, [H|T]) ->
reverseA([H] ++ To, T).
reverseA(List) ->
reverseA([], List).
To my surprise, there was no difference in the speed. I then swapped the [H] and To:
reverseA(To, []) ->
To;
reverseA(To, [H|T]) ->
reverseA(To ++ [H], T).
reverseA(List) ->
reverseA([], List).
This version took FOREVER to run. I didn't quite understand it so I went searching. There is a nice post here that has a nice explanation.
Here is the important bit from that page:
++ is only slow when used wrongly, used carefully it is as fast as anything you could craft by hand. You have to make sure you work through the list in the correct direction, otherwise the resulting append is O(N^2). When we do X ++ Y, we must make a copy of X and then prepend it to Y which is not copied.
Cheers,
-Halzy
Erlang Programming Exercise: 3-5 (refactor)
I wasn't happy with how the flatten and concatenate functions turned out. They weren't taking advantage of tail call optimizations, so I rewrote the flatten function for fun. During my rewrite I also wanted to avoid using BIFs to work on my pattern matching. I wasn't sure if I would be able to match the head of a list, that was the head of a list. It worked out, here is the result:
flattenHelper(Dst, []) ->
Dst;
flattenHelper(Dst, [[[]|HeadTail]|T]) ->
flattenHelper(Dst, [HeadTail|T]);
flattenHelper(Dst, [[HeadTop|HeadTail]|T]) ->
NewList1 = [HeadTail|T],
NewList2 = [HeadTop|NewList1],
flattenHelper(Dst, NewList2);
flattenHelper(Dst, [[]|T]) ->
flattenHelper(Dst, T);
flattenHelper(Dst, [H|T]) ->
flattenHelper([H|Dst], T);
flattenHelper(Dst, Item) ->
[Item|Dst].
flatten(Lists) ->
reverse(flattenHelper([], Lists)).
Cheers,
-Halzy
Erlang Programming Exercise: 3-5
This one was a four part exercise, so I've broken the file into sections.
-module(threefive). -export([filter/2, reverse/1, concatenate/1, flatten/1]).
Write a function that, given a list of integers and an integer, will return all integers smaller than or equal to that integer.
filter(Filtered, [], _Number) -> reverse(Filtered); filter(Filtered, [H|T], Number) when H =< Number -> filter([H|Filtered], T, Number); filter(Filtered, [_H|T], Number) -> filter(Filtered, T, Number). filter(List, Number) -> filter([], List, Number).
I'm using filter/2 as the interface function. It passes the arguments off to filter/3 which does the work. The extra argument that gets passed into filter/3 is the results list, and as you can see, it starts out empty. I ended up using that same pattern for all four of these exercises.
Write a function that, given a list, will reverse the order of the elements.
reverse(To, []) -> To; reverse(To, [H|T]) -> reverse([H|To], T). reverse(List) -> reverse([], List).
Reverse was the easiest of the four. You simply take the head from one list, and push it onto another list.
Write a function that, given a list of lists, will concatenate them.
concatenate(Dst, []) -> Dst; concatenate(Dst, [H|T]) -> concatenate([H|Dst], T). concatenateHelper(Dst, []) -> Dst; concatenateHelper(Dst, [H|T]) -> Dst2 = concatenate(Dst, H), concatenateHelper(Dst2, T). concatenate(Lists) -> reverse(concatenateHelper([], Lists)).
In order to concatenate, I take the items from the lists one at a time and add them to a result list. When we're all out of lists to copy items from, we're done. My function naming is a bit confusing. I have concatenate/1 calling concatenateHelper/2 which in turn calls concatenate/2.
Write a function that, given a list of nested lists, will return a flat list.
flattenHelper(Dst, []) -> Dst; flattenHelper(Dst, [H|T]) -> Dst2 = flattenHelper(Dst, H), flattenHelper(Dst2, T); flattenHelper(Dst, Item) -> [Item|Dst]. flatten(Lists) -> reverse(flattenHelper([], Lists)).
I don't like my solution for flatten, specifically lines 34-36. If I had a very deep structure to flatten it would consume a lot of stack space. I'll have to go back and optimize that for fun. 
Cheers,
-Halzy
Erlang Programming Exercise: 3-4
In this exercise you are to make a database using this interface:
db:new() ⇒ Db.
db:destroy(Db) ⇒ ok.
db:write(Key, Element, Db) ⇒ NewDb.
db:delete(Key, Db) ⇒ NewDb.
db:read(Key, Db) ⇒{ok, Element} | {error, instance}.
db:match(Element, Db) ⇒ [Key1, ..., KeyN].
This one took a while to get right. In other languages I can look at some code and quickly figure out what it does. When I look at erlang recursive list code, it takes a while to parse it and figure out what it does.
In the read/2 and match/2 functions below, I end up discarding the head item from the list if it doesn't match what I'm looking for. It took a while for me to get used to throwing away data like this. In other languages I would iterated over the list until I found what I was looking for, saving allocation and deallocation cycles. Getting access to the head item in Erlang is very fast so this is a common pattern. This makes me wonder what sort of optimizations the Erlang VM (beam) guys have done to minimize the data copy costs. Anyhow, here is my solution:
-module(threefour_db).
-export([new/0, destroy/1, write/3, delete/2, read/2, match/2]).
new() ->
[].
destroy(_Db) ->
ok.
delete(_Key, NewDb, []) ->
NewDb;
delete(Key, NewDb, [{Key, _Element}|T]) ->
delete(Key, NewDb, T);
delete(Key, NewDb, [H|T]) ->
delete(Key, [H|NewDb], T).
delete(Key, Db) ->
delete(Key, [], Db).
write(Key, Element, Db) ->
NewDb = delete(Key, Db),
[{Key, Element}|NewDb].
read(_Key, []) ->
{error, instance};
read(Key, [{Key,Element}|_T]) ->
{ok, Element};
read(Key, [_H|T]) ->
read(Key, T).
match(_Element, [], Keys) ->
Keys;
match(Element, [{Key,Element}|Db], Keys) ->
match(Element, Db, [Key|Keys]);
match(Element, [_H|Db], Keys) ->
match(Element, Db, Keys).
match(Element, Db) ->
match(Element, Db, []).
Cheers,
-Halzy
Erlang Programming Exercise: 3-3
Side Effects is the title of exercise 3-3. Is printing to stdout a side effect? It must be since it makes a permanent change to the system. I just hadn't considered that before.
After the first couple of exercises, this one is a bit easier and gives you a little pat on the back. Enjoy feeling smart for a couple minutes, exercise 3-8 is around the corner.
Here are the two parts for this exercise:
Write a function that prints out the integers between 1 and N.
Write a function that prints out the even integers between 1 and N.
-module(threethree).
-export([print_count/1, print_even_count/1]).
print_number(Number) ->
io:format("Number:~p~n", [Number]).
print_count(End, End) ->
print_number(End);
print_count(Current, End) ->
print_number(Current),
print_count(Current+1, End).
print_count(Num) when Num > 0 ->
print_count(1, Num).
print_even_number(Number) when Number rem 2 == 0 ->
print_number(Number);
print_even_number(_Number) ->
ok.
print_even_count(End, End) ->
print_even_number(Current);
print_even_count(Current, End) ->
print_even_number(Current),
print_even_count(Current+1, End).
print_even_count(Num) when Num > 0 ->
print_even_count(1, Num).
I didn't refactor this code until I went to post it. My guards are on the print function, so I re-use the incrementing loop and pass in which print function I want to use:
-module(threethree_ref).
-export([print_count/1, print_even_count/1]).
print_number(Number) ->
io:format("Number:~p~n", [Number]).
print_even_number(Number) when Number rem 2 == 0 ->
print_number(Number);
print_even_number(_Number) ->
ok.
print_count_loop(Print, End, End) ->
Print(End);
print_count_loop(Print, Current, End) ->
Print(Current),
print_count_loop(Print, Current+1, End).
print_count(Num) when Num > 0 ->
print_count_loop(fun print_number/1, 1, Num).
print_even_count(Num) when Num > 0 ->
print_count_loop(fun print_even_number/1, 1, Num).
Here it is in action:
2> threethree:print_count(5). Number:1 Number:2 Number:3 Number:4 Number:5 ok 3> threethree:print_even_count(5). Number:2 Number:4 ok
Cheers,
-Halzy
Erlang Programming Exercise: 3-2
Exercise 3-2 is also 2 questions:
Write a function that returns a list of the format [1,2,..,N-1,N].
Write a function that returns a list of the format [N, N-1,..,2,1]
I've created 4 functions, create/1, create/2, reverse_create/1, and reverse_create/2. The /1 functions set up the arguments for the /2 worker functions to loop on.
-module(threetwo). -export([create/1, reverse_create/1]). create(1, [1|_T]=List) -> List; create(Num, List) -> Next = Num-1, create(Next, [Next|List]). create(Num) when Num > 0 -> create(Num, [Num]). reverse_create_list(Num, [Num|_T]=List) -> List; reverse_create_list(Num, [H|_T]=List) -> reverse_create_list(Num, [H+1|List]). reverse_create(Num) when Num > 0 -> reverse_create_list(Num, [1]).
An example run:
4> threetwo:create(10). [1,2,3,4,5,6,7,8,9,10] 5> threetwo:reverse_create(10). [10,9,8,7,6,5,4,3,2,1]
The key in is to pass your target number along and to build the list from right to left. In each iteration we peak at the head of the list, modify that value and then prepend the result to the head of the full list.
[H|_T]=List
H is the first item in the list.
List is the full List.
Cheers,
Ben
Erlang Programming Exercise: 3-1
I'm posting the exercises starting with chapter 3. The previous chapters have you work in the shell and don't require much file work. Exercise 3-1 is:
Write a function sum/1 which, given a positive integer N, will return the sum of all the integers between 1 and N.
And the second part:
Write a function sum/2 which, given two integers N and M, where N =< M, will return the sum of the interval between N and M. If N > M, you want your process to terminate abnormally.
Here is my solution: threeone.erl
-module(threeone). -export([sum/1, sum/2]). sum(1) -> 1; sum(Number) -> Number + sum(Number - 1). sum(Lower, Lower) -> Lower; sum(Lower, Upper) when Lower =< Upper -> Upper + sum(Lower, Upper-1).
If you give sum/1 a number less than 1, you'll infinite loop.
The above solution doesn't use Erlang's tail call optimizations. If you give them a very large set of numbers to add up, they keep eating up memory. I wanted to see what would happen when it ran out of memory or stack space, so I told it to sum up a billion. After my system started swapping and started to crawl I killed the process. Maybe next time.
Here is the reworked version that takes advantage of tail call optimization and can sum up numbers from 1 to a billion without making my system swap. The beam.smp process stays around 10mb of memory.
-module(threeone_tco). -export([sum/1, sum/2]). sum_range(Sum, Lower, Lower) -> Sum + Lower; sum_range(Sum, Lower, Upper) -> sum_range(Sum + Upper, Lower, Upper-1). sum(Number) when Number > 0 -> sum_range(0, 1, Number). sum(Lower, Upper) when Lower =< Upper -> sum_range(0, Lower, Upper).
The big change comes from passing the Sum as an argument to the next function call. To use TCO (Tail Call Optimization) you want to leave no work to be done in your function, and the last thing your function does, should be calling itself. Previously, the function would still have to add two numbers after it's recursion finished.
Cheers,
-Halzy
Learning Erlang
It all started way back when I was doing concurrent programming in Java for the MMORPG when a buddy of mine pointed out CouchDB. It's a neat project, but was written in some strange language called Erlang. I started to look more into Erlang and found that the language was designed to addressed some of the more complicated aspects of concurrent programming. This appealed to me because those were my current pain points with the game. When do we lock around what data, which threads are changing what, do I need to use volatile for this variable too. It's a lot to think about, it's hard to get right, and Erlang solves those problems for you if you're willing to think differently.
I started by reading Programming Erlang by Joe Armstrong and now I'm reading through Erlang Programming by Francesco Cesarini and Simon Thompson. I'm enjoying the second book more than the first one, but this could be a side effect of being more comfortable with Erlang because I read the first book. I'm so taken with this bizarre language that I've decided to work through all of the exercises in Erlang Programming. I'll be posting my solutions and hopefully, by the time I get through all of them I'll feel comfortable enough with Erlang to build something with it.
Cheers,
- Halzy