[erlang-questions] wierd outome on my match method

Steve Vinoski vinoski@REDACTED
Sat Jan 31 17:18:04 CET 2015


On Sat, Jan 31, 2015 at 9:31 AM, Roelof Wobben <r.wobben@REDACTED> wrote:

> Thanks,
>
> Everything is working now.
> Finnaly I have solved the whole exercise like this :
>
> -module(db).
>
> -export([new/0, destroy/1, write/3, read/2, delete_key/3, delete/2,
> match/2, match_key/3]).
>
> new() ->
>   [].
>
> destroy(_Db) ->
>   ok.
>
> write(Key, Element, Db) ->
>    [ {Key, Element} | Db ].
>
> read(_Key, []) ->
>   {error, "Instance"};
>
> read(Key, [Head | List]) ->
>   case element(1, Head) of
>     Key -> {ok, element(2, Head)};
>     _ -> read(Key, List)
>   end.
>
> delete_key( _Key, [] , List2) ->
>   List2 ;
>
> delete_key( Key, [Head | Tail], List3 ) ->
>   case element(1, Head) of
>     Key -> delete_key(Key, Tail, List3 );
>     _ -> delete_key(Key, Tail, [Head | List3] )
>    end.
>
> delete( _Key, [] ) ->
>   {error, "Instance"};
>
> delete(Key, List) ->
>   match_key (Key, List, []).
>
> match_key( _Key, [] , List) ->
>   List ;
>
> match_key( Key, [Head | Tail], List ) ->
>   case element(1, Head) of
>     Key -> match_key(Key, Tail, [element(2,Head) | List] );
>     _ -> match_key(Key, Tail,  List )
>    end.
>
> match( Key, [] ) ->
>   {error, "Instance"};
>
> match(Key, List) ->
>   match_key (Key, List, []).
>
>
> Now I have 2 questions :
>
> 1) Is this a good solution.
>

Does it work? If it works, then it's potentially a good solution. But you
should think about including test code so you can refactor with confidence,
and to make it easier for others to provide the help you're seeking.


> 2) Can I somewhere hide my helper functions (match_key, delete_key) and do
> not get a warning about unused.


If you're getting warnings about unused functions, there's a chance the way
you're calling them doesn't match their definitions. Assuming you're
working from example 3-4 of "Erlang Programming", it wants new/0,
destroy/1, write/3, delete/2, read/2, and match/2 to comprise the API. So
let's make that change:

-export([new/0, destroy/1, write/3, delete/2, read/2, match/2]).

Compiling your code with this change yields:

/private/tmp/db.erl:23: Warning: function delete_key/3 is unused
/private/tmp/db.erl:47: Warning: variable 'Key' is unused

Why is this delete_key/3 unused? The reason is that the only place that
calls it is the delete_key/3 function itself. If it's not exported, then
only functions in the same module can call it, and of no other functions in
the module call it, it's unused. As pointed out previously, the bug is here:

delete(Key, List) ->
  match_key (Key, List, []).

which should be:

delete(Key, List) ->
  delete_key (Key, List, []).

If we make that change, and add a leading underscore to Key on line 47, the
code compiles without warning. But does it work? Let's add an exported
test/0 function based on the sample session in the book to see:

test() ->
    Db = db:new(),
    Db1 = db:write(francesco, london, Db),
    Db2 = db:write(lelle, stockholm, Db1),
    {ok, london} = db:read(francesco, Db2),
    Db3 = db:write(joern, stockholm, Db2),
    {error, instance} = db:read(ola, Db3),
    [joern, lelle] = db:match(stockholm, Db3),
    Db4 = db:delete(lelle, Db3),
    [joern] = db:match(stockholm, Db4),
    ok.

Then run it:

5> db:test().
** exception error: no match of right hand side value {error,"Instance"}
     in function  db:test/0 (/private/tmp/db.erl, line 59)

Line 59 is:

    {error, instance} = db:read(ola, Db3),

The error is a failure to match the return value of read/2 against the
expected {error, instance}. The problem is here:

read(_Key, []) ->
  {error, "Instance"};

Let's change that:

read(_Key, []) ->
  {error, instance};

Also change the failing clauses for match/2 and delete/2 the same way. Now
recompile and rerun the test:

7> db:test().
** exception error: no match of right hand side value []
     in function  db:test/0 (/private/tmp/db.erl, line 60)

Line 60 is:

    [joern, lelle] = db:match(stockholm, Db3),

Looks like match/2 doesn't work, since it's returning an empty list. Why?
match/2 just calls match_key/3:

match_key( _Key, [] , List) ->
  List ;

match_key( Key, [Head | Tail], List ) ->
  case element(1, Head) of
    Key -> match_key(Key, Tail, [element(2,Head) | List] );
    _ -> match_key(Key, Tail,  List )
   end.

The problem is the call to element(1, Head) returns the Name element of the
tuple, not the Location. You have your calls to element(1, Head) and
element(2, Head) in the wrong places in this function. Let's swap them:

match_key( Key, [Head | Tail], List ) ->
  case element(2, Head) of
    Key -> match_key(Key, Tail, [element(1,Head) | List] );
    _ -> match_key(Key, Tail,  List )
   end.

Recompile and re-test:

9> db:test().
** exception error: no match of right hand side value [lelle,joern]
     in function  db:test/0 (/private/tmp/db.erl, line 60)

The test expects [joern,lelle] but match/2 now returns [lelle,joern]. Why?
The reason is here, on line 43:

    Key -> match_key(Key, Tail, [element(1,Head) | List] );

Every time we find a match, we push the result onto the head of our
accumulator list passed to the next iteration. That means the last result
we find will be first in the results. This is a common issue with
accumulator-based recursive functions, and normally you'd fix it by calling
lists:reverse/1 to reverse the final result at line 39:

match_key( _Key, [] , List) ->
  lists:reverse(List);

But the book says no calls to the lists module are allowed, so we can't do
this. Another approach is to append to the accumulator list instead, at
line 43:

    Key -> match_key(Key, Tail, List ++ [element(1,Head)]);

With this change in place, let's recompile and rerun the tests:

11> db:test().
ok

Yay, the test works. Now, can we improve the code?

One thing that sticks out are the calls to element/2. Those can be replaced
with tuple pattern matching. For example, read/2 looks like this:

read(Key, [Head | List]) ->
  case element(1, Head) of
    Key -> {ok, element(2, Head)};
    _ -> read(Key, List)
  end.

Let's get rid of those element/2 calls. The case is simply doing a match of
the first element of each tuple against Key. We can do that right in the
function head, like this:

read(Key, [{Key,Location} | List]) ->
    {ok, element(2, Head)};

And since element(2,Head) is just Location, we can just make it this:

read(Key, [{Key,Location} | _List]) ->
    {ok, Location};

OK, that works if Key matches the name in the head tuple. But what if Key
doesn't match? We need another read/2 clause, originally handled by the
second clause of the case statement:

read(Key, [_Head | List]) ->
    read(Key, List).

With these changes in place, do our tests still pass?

16> db:test().
ok

Yep. Now, where else do we call element/2? In delete_key/3:

delete_key( Key, [Head | Tail], List3 ) ->
  case element(1, Head) of
    Key -> delete_key(Key, Tail, List3 );
    _ -> delete_key(Key, Tail, [Head | List3] )
   end.

We can change this roughly the same way we changed read/2, like this:

delete_key(Key, [{Key,_Location} | Tail], List3) ->
    delete_key(Key, Tail, List3);
delete_key(Key, [Head | Tail], List3) ->
    delete_key(Key, Tail, [Head | List3]).

and rerun the tests:

18> db:test().
ok

BTW, notice that delete_key/3 also reverses the result list. For
consistency, change it to use append instead, like we did earlier for
match_key/3:

delete_key(Key, [{Key,_Location} | Tail], List3) ->
    delete_key(Key, Tail, List3);
delete_key(Key, [Head | Tail], List3) ->
    delete_key(Key, Tail, List3 ++ [Head]).

And the tests still pass. The other use of element/2 is in match_key/3, so
let's fix that the same way:

match_key(Key, [{Name,Key} | Tail], List) ->
    match_key(Key, Tail, List ++ [Name]);
match_key(Key, [_Head | Tail], List) ->
    match_key(Key, Tail,  List).

The difference here from previous matches is the Key matches element 2
rather than element 1. The tests still pass with this change:

22> db:test().
ok

One problem with the code is that the write/2 function unconditionally adds
the name/location without checking to see if name is already there. Most
people can't be in multiple locations at once, so get rid of any matching
name/location first:

write(Name, Location, Db) ->
    NewDb = case read(Name, Db) of
                {ok,_Location} ->
                    delete(Name, Db);
                {error,instance} ->
                    Db
            end,
    [{Name, Location} | NewDb].

We first read to see if the name is present; if so, we delete it and used
the modified db to write. If not found, we just use the db passed in to
write. And the tests still pass with this change, which isn't too
surprising since we're not specifically testing this case.

At this stage, another improvement is to rename the *_key functions --
there's no need for the _key suffix, they can instead just be named delete
and match because they have arity 3, unlike their exported counterparts,
which have arity 2. The arity difference prevents them from clashing. I
would also stop using Key and Element as parameter names and use Name and
Location instead, as they're more descriptive for the problem.

With these final changes in place, the whole refactored module looks like
this:

-module(db).

-export([new/0, destroy/1, write/3, delete/2, read/2, match/2, test/0]).

new() ->
    [].

destroy(_Db) ->
    ok.

write(Name, Location, Db) ->
    NewDb = case read(Name, Db) of
                {ok,_Location} ->
                    delete(Name, Db);
                {error,instance} ->
                    Db
            end,
    [{Name, Location} | NewDb].

read(_Name, []) ->
    {error, instance};

read(Name, [{Name,Location} | _List]) ->
    {ok, Location};
read(Name, [_Head | List]) ->
    read(Name, List).

delete(_Name, [] , List) ->
    List;

delete(Name, [{Name,_Location} | Tail], List) ->
    delete(Name, Tail, List);
delete(Name, [Head | Tail], List) ->
    delete(Name, Tail, List ++ [Head]).

delete(_Name, []) ->
    {error, instance};

delete(Name, List) ->
    delete(Name, List, []).

match( _Name, [] , List) ->
    List;

match(Location, [{Name,Location} | Tail], List) ->
    match(Location, Tail, List ++ [Name]);
match(Location, [_Head | Tail], List) ->
    match(Location, Tail,  List).

match(_Location, []) ->
    {error, instance};
match(Location, List) ->
    match(Location, List, []).

test() ->
    Db = db:new(),
    Db1 = db:write(francesco, london, Db),
    Db2 = db:write(lelle, stockholm, Db1),
    {ok, london} = db:read(francesco, Db2),
    Db3 = db:write(joern, stockholm, Db2),
    {error, instance} = db:read(ola, Db3),
    [joern, lelle] = db:match(stockholm, Db3),
    Db4 = db:delete(lelle, Db3),
    [joern] = db:match(stockholm, Db4),
    ok.

Study all these changes and make sure you understand the reasoning behind
them.

--steve
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20150131/8550874a/attachment.htm>


More information about the erlang-questions mailing list