#functionally solving problems

Picture: The Clash - London Calling

Heathrow to London - PART II

Reading/Parsing Files

1> {ok, Binary} = file:read_file("road.txt"). {ok,<<"50\r\n10\r\n30\r\n5\r\n90\r\n20\r\n40\r\n2\r\n25\r\n10\r\n8\r\n0\r\n">>} 2> S = string:tokens(binary_to_list(Binary), "\r\n\t "). ["50","10","30","5","90","20","40","2","25","10","8","0"]

3> [list_to_integer(X) || X <- S]. [50,10,30,5,90,20,40,2,25,10,8,0]

-module(road). -compile(export_all). main() -> File = "road.txt", {ok, Bin} = file:read_file(File), parse_map(Bin). parse_map(Bin) when is_binary(Bin) -> parse_map(binary_to_list(Bin)); parse_map(Str) when is_list(Str) -> [list_to_integer(X) || X <- string:tokens(Str,"\r\n\t ")].

group_vals([], Acc) -> lists:reverse(Acc); group_vals([A,B,X|Rest], Acc) -> group_vals(Rest, [{A,B,X} | Acc]).

parse_map(Bin) when is_binary(Bin) -> parse_map(binary_to_list(Bin)); parse_map(Str) when is_list(Str) -> Values = [list_to_integer(X) || X <- string:tokens(Str,"\r\n\t ")], group_vals(Values, []).

1> c(road). {ok,road} 2> road:main(). [{50,10,30},{5,90,20},{40,2,25},{10,8,0}]

the book chapter

You're on a plane due to land at Heathrow airport in the next hours. You have to get to London as fast as possible; your rich uncle is dying and you want to be the first there to claim dibs on his estate.--book

There are two roads going from Heathrow to London and a bunch of smaller streets linking them together. Because of speed limits and usual traffic, some parts of the roads and smaller streets take longer to drive on than others. Before you land, you decide to maximize your chances by finding the optimal path to his house. Here's the map you've found on your laptop--book

road.txt:

50 10 30 5 90 20 40 2 25 10 8 0

The road is laid in the pattern: A1, B1, X1, A2, B2, X2, ..., An, Bn, Xn, where X is one of the roads joining the A side to the B side of the map. We insert a 0 as the last X segment, because no matter what we do we're at our destination already. Data can probably be organized in tuples of 3 elements (triples) of the form {A,B,X}.--book

Writing a Recursive Function

Base case

When writing a recursive function, the first thing to do is to find our base case. For our problem at hand, this would be if we had only one tuple to analyze, that is, if we only had to choose between A, B (and crossing X, which in this case is useless because we're at destination)--book

A ---10 min-- | Destination | B ---23 min---

In base case scenario you got two options, or rather two roads that leads to your destination. Either you pick road A which will take you 10 minutes to get to your destination or road B which takes 23 minutes.

Then the choice is only between picking which of path A or path B is the shortest. If you've learned your recursion right, you know that we ought to try and converge towards the base case. This means that on each step we'll take, we'll want to reduce the problem to choosing between A and B for the next step.--book

Let's extend our map and start over:

Ah! It gets interesting! How can we reduce the triple {5,1,3} to a strict choice between A and B?--book

For Point A (*)

A1 Pt A A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2

Let's see how many options are possible for A [(*)]. To get to the intersection of A1 and A2 (I'll call this the point A1), I can either take road A1 directly (5), ...

A1 A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2

or come from B1 (1) and then cross over X1 (3).

A1 A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2

In this case, The first option (5) is longer than the second one (4). For the option A, the shortest path is [B, X].

So what are the options for B?

A1 A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 Pt B B2

You can either proceed from A1 (5) then cross over X1 (3),

A1 A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 Pt B B2

or strictly take the path B1 (1).--book

A1 A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 Pt B B2

Alright! What we've got is a length 4 with the path [B, X] towards the first intersection A and a length 1 with the path [B] towards the intersection of B1 and B2. We then have to decide what to pick between going to the second point A (the intersection of A2 and the endpoint or X2) and the second point B (intersection of B2 and X2). To make a decision, I suggest we do the same as before. Now you don't have much choice but to obey, given I'm the guy writing this text. Here we go!--book

A1 A2 Pt A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2 Pt B2

All possible paths to take in this case can be found in the same way as the previous one. We can get to the next point A [Pt A2] by either taking the path A2 from [B, X], which gives us a length of 14 (14 = 4 + 10),

A1 A2 Pt A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2

or by taking B2 then X2 from [B], which gives us a length of 16 (16 = 1 + 15 + 0).

A1 A2 Pt A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2

In this case, the path [B, X, A] is better than [B, B, X].--book

We can also get to the next point B by either taking the path A2 from [B, X] and then crossing over X2 for a length of 14 (14 = 4 + 10 + 0),

A1 A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2 Pt B2

or by taking the road B2 from [B] for a length of 16 (16 = 1 + 15). Here, the best path is to pick the first option, [B, X, A, X].--book

A1 A2 A --- 5 ----*---------- 10 ------------*-- | | 3 | X1 0 | X2 | | B --- 1 ----*---------- 15 ------------*-- B1 B2 Pt B2

more of these pictures @ xkcd

Reverse Polish Notation Calculator - PART III

Well an alternative implementation to fun erlang:'*'/2 is:

lists:foldl(fun(X, Prod) -> X * Prod end, 1, [1,2,3,4,5]).

Original book's version

lists:foldl(fun erlang:'*'/2, 1, [0.5, 20, 10, 10]).

Code Review - "breaking it down"

foldl(Fun, Acc0, List) -> Acc1

Calls Fun(Elem, AccIn) on successive elements A of List, starting with AccIn == Acc0. Fun/2 must return a new accumulator which is passed to the next call. The function returns the final value of the accumulator. Acc0 is returned if the list is empty.

The code (that we're analyzing):

lists:foldl(fun(X, Prod) -> X * Prod end, 1, [1,2,3,4,5]).

Fun is fun(X, Prod) -> X * Prod end

Acc0 is 1

List is [1,2,3,4,5]

Elem is X

Reverse Polish Notation Calculator - PART II

rpn(L) when is_list(L) -> [Res] = lists:foldl(fun rpn/2, [], string:tokens(L, " ")), Res. rpn("prod", Stack) -> [lists:foldl(fun erlang:'*'/2, 1, Stack)]; rpn(X, Stack) -> [read(X)|Stack]. %% read(String()) -> Int() | Float() read(N) -> case string:to_float(N) of {error,no_float} -> list_to_integer(N); {F,_} -> F end. 1000.0 = rpn("10 10 20 0.5 prod"),

"10 10 20 0.5 prod"

rpn("10 10 20 0.5 prod") when is_list("10 10 20 0.5 prod") -> [Res] = lists:foldl(fun rpn/2,[], string:tokens("10 10 20 0.5 prod", " ")), Res.

when is_list("10 10 20 0.5 prod")

1> is_list("10 10 20 0.5 prod"). true

rpn("10 10 20 0.5 prod") when true -> [Res] = lists:foldl(fun rpn/2,[], string:tokens("10 10 20 0.5 prod", " ")), Res.

string:tokens("10 10 20 0.5 prod", " ")),

1> string:tokens("10 10 20 0.5 prod", " "). ["10","10","20","0.5","prod"]

rpn("10 10 20 0.5 prod") when true -> [Res] = lists:foldl(fun rpn/2,[], ["10","10","20","0.5","prod"]), Res.

["10","10","20","0.5","prod"] Starting at "10"

...

OH damn I don't really know how foldl really works! FML.

foldl(Fun, Acc0, List) -> Acc1

Calls Fun(Elem, AccIn) on successive elements A of List, starting with AccIn == Acc0. Fun/2 must return a new accumulator which is passed to the next call. The function returns the final value of the accumulator. Acc0 is returned if the list is empty. For example:

> lists:foldl(fun(X, Sum) -> X + Sum end, 0, [1,2,3,4,5]). 15 > lists:foldl(fun(X, Prod) -> X * Prod end, 1, [1,2,3,4,5]). 120

Back to the Main Picture

rpn("prod", Stack) -> [lists:foldl(fun erlang:'*'/2, 1, Stack)];

The main picture is figuring out how prod works.

One main reason why I couldn't figure it out is because I assume that I knew what foldl actually does. Looking carefully at foldl and it's parameters. I've realized I was wrong.

rpn("10 10 20 0.5 prod") when true -> [Res] = lists:foldl(fun rpn/2,[], ["10","10","20","0.5","prod"]), Res.

going back to:

["10","10","20","0.5","prod"] Starting at "10"

With "10" we pattern match to rpn(X, Stack) -> [read(X)|Stack]. and get:

rpn("10 10 20 0.5 prod") when true -> [Res] = lists:foldl(fun rpn/2,[], ["10","10","20","0.5","prod"]), Res. rpn("10", Stack) -> [read("10")|Stack].

We converted (to an integer) and push 10 on to Stack.

> Stack [10]

Looking back at foldl. lists:foldl(fun rpn/2,[], ["10","10","20","0.5","prod"]) mapping foldl(Fun, Acc0, List).

Fun is fun rpn/2

Acc0 is []

List is ["10","10","20","0.5","prod"]

Now the function for "10","10","20","0.5" is rpn(X, Stack) -> [read(X)|Stack].

So we're basically going to push these numbers on to Stack (aka AccIn).

> Stack [0.5, 20, 10, 10]

Now we got to "prod" in the list.

With "prod" we pattern match to rpn("prod", Stack) -> [lists:foldl(fun erlang:'*'/2, 1, Stack)]; and get:

rpn("10 10 20 0.5 prod") when true -> [Res] = lists:foldl(fun rpn/2,[], ["10","10","20","0.5","prod"]), Res. rpn("prod", [0.5, 20, 10, 10]) -> [lists:foldl(fun erlang:'*'/2, 1, [0.5, 20, 10, 10])];

Nice! Let's concentrate on this:

rpn("prod", [0.5, 20, 10, 10]) -> [lists:foldl(fun erlang:'*'/2, 1, [0.5, 20, 10, 10])];

1> c(calc.erl). {ok, calc} 2> calc:rpn("10 10 20 0.5 prod"). 1.0e3 3> calc:rpn("10 prod"). 10 4> calc:rpn("prod"). 1 5> calc:rpn("10 2 prod"). 20

Reverse Polish Notation Calculator

Parsing

1> string:tokens("10 4 3 + 2 * -", " "). ["10","4","3","+","2","*","-"]

Stack

Using the cons (|) operator in [Head|Tail] effectively behaves the same as pushing Head on top of a stack (Tail, in this case). Using a list for a stack will be good enough.--book

Erlang's list will represent our stack.

To read the expression, we just have to do the same as we did when solving the problem by hand. Read each value from the expression, if it's a number, put it on the stack. If it's a function, pop all the values it needs from the stack, then push the result back in. To generalize, all we need to do is go over the whole expression as a loop only once and accumulate the results. Sounds like the perfect job for a fold!--book

So the stack logic can be implemented via fold

We'll write the function responsible for all the looping and also the removal of spaces in the expression--book

-module(calc). -export([rpn/1]). rpn(L) when is_list(L) -> [Res] = lists:foldl(fun rpn/2, [], string:tokens(L, " ")), Res.

Alright what does this do?

rpn/1 takes a list and put it in a fold, (lists:foldl/3 a left fold to be precise). The three parameters are as follow:

First parameter (fun rpn/2): is a function that will apply to each element of the list.

Second parameter ([]): is an accumulator, something to store our computation for tail recursion.

Third parameter (string:tokens(L, "http://erldocs.com/R15B/stdlib/lists.html#foldl/3")): is the list we wish to fold.

Parsing the head of the stack.

rpn(X, Stack) -> [read(X)|Stack].

Converting the numbers in head value to either integer or float.

read(N) -> case string:to_float(N) of {error,no_float} -> list_to_integer(N); {F,_} -> F end.

Parsing the operators too.

rpn("+", [N1,N2|S]) -> [N2+N1|S]; rpn(X, Stack) -> [read(X)|Stack].

The rest of the operators...

rpn("+", [N1,N2|S]) -> [N2+N1|S]; rpn("-", [N1,N2|S]) -> [N2-N1|S]; rpn("*", [N1,N2|S]) -> [N2*N1|S]; rpn("/", [N1,N2|S]) -> [N2/N1|S]; rpn("^", [N1,N2|S]) -> [math:pow(N2,N1)|S]; rpn("ln", [N|S]) -> [math:log(N)|S]; rpn("log10", [N|S]) -> [math:log10(N)|S]; rpn(X, Stack) -> [read(X)|Stack].

Sum operator

rpn("sum",L) -> lists:sum(L);

Omg, I'm glad list have a sum function.

Book's code

rpn("sum", Stack) -> [lists:sum(Stack)];

What I did wrong, I should have return a list, [], not just the value.

Prod operator

rpn("prod",L) -> [foldl(*,[],L)];

... stuck. I want to fold each and every item in the current list and apply the multiplication.

Book's code

rpn("prod", Stack) -> [lists:foldl(fun erlang:'*'/2, 1, Stack)];

Wut?

No really what the flying hell?

Code Review, breaking it down for prod.

rpn("prod", Stack) -> [lists:foldl(fun erlang:'*'/2, 1, Stack)];

Above is the original function.

Instead of fun erlang:'*'/2 can I replace it with * this?

Wait let me test if the book's code works first.

Yup works.

lists:foldl(*, 1, Stack) & lists:foldl('*', 1, Stack) does not work.

Time to look up the function fun erlang:'*'/2.

Online document doesn't show it... and the man page on unix doesn't come up with anything.

Assumption: fun erlang:'*'/2 is just an operator like -,+,/,etc....

Assuming that is true, let's try: fun erlang:'+'/2:

rpn("prod", Stack) -> [lists:foldl(fun erlang:'+'/2, 1, Stack)];

19> calc:rpn("10 10 20 0.5 prod"). 41.5

Oooooh it seems that my assumption is correct! Let's try - and /.

rpn("prod", Stack) -> [lists:foldl(fun erlang:'-'/2, 1, Stack)];

19> calc:rpn("10 10 20 0.5 prod"). 20.5 20> 10-10-20-0.5. -20.5 21> 0.5-20-10-10. -39.5

FML, the sign is different for -. Why...? Let's see / now before investigating that.

rpn("prod", Stack) -> [lists:foldl(fun erlang:'/'/2, 1, Stack)];

19> calc:rpn("10 10 20 0.5 prod"). 40 20> 10/10/20/0.5. 0.1

Fml. The orders in - & / matters compare to + & * perhaps that is why the answers is funky.

Why is the second parameter in prod is 1 instead of []?

Let's try: rpn("prod", Stack) -> [lists:foldl(fun erlang:'*'/2, [], Stack)];.

Nope. ERROR.

Let's try: rpn("prod", Stack) -> [lists:foldl(fun erlang:'*'/2, 0, Stack)];.

0.0

Let's try: rpn("prod", Stack) -> [lists:foldl(fun erlang:'*'/2, 2, Stack)];.

2000

HMMM... the accumulator eh.

Trying:

rpn("prod", Stack) -> [lists:foldl(fun erlang:'/'/2, H, [H|T])];

FML. Doesn't work, the H,T are unbounded.