Seven Languages In Seven Weeks: Erlang - Day 2
I just finished day 2 of Erlang from my Seven Languages in Seven Weeks book. This day talked a lot about lists and about the functionality that Erlang provides for accessing and mutating lists. Apparently, list mapping (mapping one list onto another list) is so foundational to the language that there is even a special syntax, known as a "list comprehension", that is used for ultra-concise list mapping.
A list comprehension is basically a way to apply multiple filters and generators to a list in order to create a new list. What's really cool about this syntax, though, is that it allows you to transform the list through unification while the mapping is executed.
HW1: Consider a list of keyword-value tuples, such as [{erlang, "a functional language"}, {ruby, "an OO language"}]. Write a function that accepts the list and a keyword and returns the associated value for the keyword.
My first instinct on this problem was to use the built-in functions provided by the existing "lists" module. There is already a keyfind() function which is designed specifically to examine lists of tuples (such as the one presented in this problem).
%-- Consider a list of keyword-value tuples, such as [{erland,
%-- "A functional language"}, {ruby, "An OO langauge"}]. Write a
%-- function that accepts the list and a keyword and returns the
%-- associated value for the keyword.
-module( hw1 ).
-export( [get_tuple_value/2] ).
%-- I get the Value associated with the tuple that has the given
%-- target key as its first value.
get_tuple_value( List, Key ) ->
%-- Get the tuple who's first value is our key.This will return
%-- the first instance of the given tuple or false.
Tuple = lists:keyfind( Key, 1, List ),
%-- Check to see the value that came back. Either we got our
%-- or we got false (or we got a tuple that doesn't match our
%-- desired structure.
case Tuple of
%-- We found our two-key tuple.
{Key, Value} ->
%-- Return the value.
Value;
%-- We did not match our two-item tuple with the given
%-- key.
_ ->
%-- Return false.
false
end
.
As you can see, this code simply searched the list for a Tuple who's first value is our keyword. Then, if a tuple was found, I returned the Value. When we compile and query this code, we get the following console output:
1> c( hw1 ).
{ok,hw1}
2> Girls = [{katie, "Adorable"}, {joanna, "Sassy"}, {tricia, "Sexy"}].
[{katie,"Adorable"},{joanna,"Sassy"},{tricia,"Sexy"}]
3> hw1:get_tuple_value( Girls, joanna ).
"Sassy"
4> hw1:get_tuple_value( Girls, samantha ).
false
As you can see, this was able to return the associated value for the tuple with the given key; or, it returned false when no tuple with the given key could be found.
This solution worked, but I was eager to play around with the list comprehensions. As such, I made another attempt at the problem, this time without the aide of any built-in functions:
%-- Consider a list of keyword-value tuples, such as [{erland,
%-- "A functional language"}, {ruby, "An OO langauge"}]. Write a
%-- function that accepts the list and a keyword and returns the
%-- associated value for the keyword.
-module( hw1b ).
-export( [get_tuple_value/2] ).
%-- I get the Value associated with the tuple that has the given
%-- target key as its first value.
get_tuple_value( List, TargetKey ) ->
%-- Use a list comprehension to get the Values for the target
%-- key. This may return a list with 0+ items.
Values = [ Value || {Key, Value} <- List, (Key == TargetKey) ],
%-- Check to see how our values came back.
case Values of
%-- At least one value came back.
[ FirstValue | _ ] ->
%-- Return the first value that came back.
FirstValue;
%-- We did not get a populated list (there was not matching
%-- tuple with the given key).
[] ->
%-- Return false for failed search.
false
end
.
This time, we are using a list comprehension in order to map the incoming tuple list into a list of corresponding values:
Values = [ Value || {Key, Value} <- List, (Key == TargetKey) ]
Essentially, this says, for each item in List, unify it with the tuple {Key, Value}, but only where the unified Key matches the incoming TargetKey argument. Then, for each of those valid tuples, return the Value property (the tuple's second index value). This will create an array of Value items, which we can match against in our succeeding Case statement.
And, when we compile and query the above code, we get the following console output:
1> c( hw1b ).
{ok,hw1b}
2> Girls = [{katie, "Adorable"}, {joanna, "Sassy"}, {tricia, "Sexy"}].
[{katie,"Adorable"},{joanna,"Sassy"},{tricia,"Sexy"}]
3> hw1b:get_tuple_value( Girls, joanna ).
"Sassy"
4> hw1b:get_tuple_value( Girls, kit ).
false
I don't know how well the list comprehensions lend themselves to readability; but, the ease with which multiple filters can be applied to a list mapping is pretty cool.
HW2: Consider a shopping list that looks like [{item quantity price},...]. Write a list comprehension that builds a list of items of the form [{item total_price},...], where total_price is quantity times price.
%-- Consider a shopping list that looks like [{item quantity price},
%-- ...]. Write a list comprehension that builds a list of items of
%-- the form [{item total_price}, ...], where total_price is quantity
%-- times price.
-module( hw2 ).
-export( [calculate_price/1] ).
%-- I convert the cart list into a list with price.
calculate_price( Cart ) ->
%-- Return a list of tuples in which the second value is the
%-- a product of the price times the quantity.
[ {Item, (Quantity * Price)} || {Item, Quantity, Price} <- Cart ]
.
As you can see, list comprehensions make list mapping pretty simple. When we compile and query the above code, we get the following console output:
1> c( hw2 ).
{ok,hw2}
2> Cart = [{widgetA, 1, 1.50}, {widgetB, 3, 2.50}].
[{widgetA,1,1.5},{widgetB,3,2.5}]
3> hw2:calculate_price( Cart ).
[{widgetA,1.5},{widgetB,7.5}]
Here, we mapped a list of tuples with 3 indices on to a list of tuples with 2 indices.
HW3: Bonus Problem: Write a program that reads a tic-tac-toe board presented as a list or a tuple of size nine. Return the winner (X or O) if a winner has been determined, cat if there are no more possible movies, or no_winner if no player has won yet.
I wanted to use list comprehensions for this but, I couldn't quite figure it out. I fell back on a more traditional style of programming.
%-- Write a program that reads a tic-tac-toe board presented as a
%-- list or a tuple of size nine. Return the winner (x or o) if a
%-- winner has been determined, cat if there no more possible moves,
%-- or no_winner if no player has won yet.
%--
%-- NOTE: This assumes that blank spaces are " ".
-module( hw3 ).
-export( [board_status/1] ).
%-- I get the status of the given tic-tac-toe board which is
%-- represented by the list of 9 spots.
board_status( Board ) ->
%-- Create a collection of possible winning paths. A board is
%-- a winner if a single player (X or O) has marks in all three
%-- indices of any of the following combinations.
PossibleWinningPaths = [
{1,2,3},
{4,5,6},
{7,8,9},
{1,4,7},
{2,5,8},
{3,6,9},
{1,5,9},
{3,5,7}
],
%-- Filter the possible winning paths down to a winning path(s).
%-- This will be a path that is not blank and is occupied with
%-- all of the same player pieces.
WinningPaths = lists:filter(
fun( Path ) ->
%-- Get the player pieces in the given path positions.
A = lists:nth( element( 1, Path ), Board ),
B = lists:nth( element( 2, Path ), Board ),
C = lists:nth( element( 3, Path ), Board ),
%-- Return TRUE if all three match (and are not blank).
(A /= " ") and (A == B) and (A == C)
end,
PossibleWinningPaths
),
%-- Check to see if we found a winning path.
case WinningPaths of
%-- We found a winning path. If for some reason the filter
%-- returned more than one winning path (invalid baord
%-- scenario), we're only going to deal with the first one.
[WinningPath | _] ->
%-- Return the first value in the winning path - this
%-- will reperesent the winning player.
lists:nth(
element( 1, WinningPath ),
Board
);
%-- No winning path was found.
[] ->
%-- If no winning path was found, we have to figure out
%-- if there is are any possible moves let, or if there
%-- is a tie (board is full).
HasSpaces = lists:any(
fun(X) -> (X == " ") end,
Board
),
%-- Check to see if any spaces were found.
if (HasSpaces) ->
%-- There is a space left, so return a status of
%-- no winner.
no_winner;
%-- There are no more spaces.
true ->
%-- Since there is no winner and there are no more
%-- possible moves, return a tie.
cat
end
end
.
When we compile and query the above code, we get the following console output:
1> c( hw3 ).
{ok,hw3}
2> hw3:board_status( [" "," "," "," "," "," "," "," "," "] ).
no_winner
3> hw3:board_status( ["X","X","X"," "," "," "," "," "," "] ).
"X"
4> hw3:board_status( ["O","X","O","X","O","X","O"," "," "] ).
"O"
5> hw3:board_status( ["O","X","O","X","O","X","X","O","X"] ).
cat
While I couldn't figure out how to leverage list comprehensions in this solution, I have to say that I am rather starting to enjoy the way pattern matching is performed in languages like this. The fact that you can both compare values and unify them with variables at the same time is quite an awesome technique.
So far, I am having a good time with Erlang. I think there are probably be more Prolog-like features that I could be leveraging as far as method-based pattern-matching goes; but, for the time-being, I'm having a good time experimenting with list comprehensions. I think concurrency is coming up next - I hope that this time it will start to make more sense.
Want to use code from this post? Check out the license.
Reader Comments
I'm only passingly familiar with Erlang, but I have been teaching CouchDB in the classroom for a few months now. CouchDB is built in Erlang. Your examples here show a certain, for lack of a better word, "smell" to Erlang that seems to have carried into CouchDB. I don't mean this in a bad way, I just now see how some of the odder syntax elements of CouchDB JavaScript seem to relate to similar syntax elements in Erlang. It's eye-opening, to be sure.
@Rick,
I don't know how much of what I have here should be considered even close to idiomatic for the language. If anything, I am sure I am using approaches that are exhibited by people not familiar with the efficiencies of the language.
That said, I do find some of the syntax choices a bit odd. He even says in the book that when you rearrange Case statements (for example), you have to actually change the syntax (ie. where the semi-colons are). This seems like an odd choice for the language to have made.
My attempt at a pattern matching solution:
I did this last night, and used a pattern matching approach too. Except in mine I don't repeat the rules for x and o, but I do have to add the "when" guards after each definition :/
e represents empty
I'd like to learn how to do metaprogramming in Erlang, so I could write a program that wrote these rules itself (there is lots of repetition and some obvious patterns).
Great blog. You have some courage to finish all exercises ! My Tic-Tac-Toe solution looks a bit different from those above : http://kuriqoo.blogspot.jp/2012/08/seven-languages-in-seven-weeks-erlang.html