1
\$\begingroup\$

I'm new to Erlang and I'm trying to port my Project Euler solutions in C# to Erlang. I have a priority queue implementation with unit tests.

I'm wondering if I'm missing something(I probably do) if I was writing serious Erlang code.

priority_queue.hrl

-record(heap_node, { item :: any(), children :: [#heap_node{}] }).
-type heap_node() :: #heap_node{}.

-record(priority_queue, { root :: heap_node() | nil, comparer :: comparer() }).
-type priority_queue() :: #priority_queue{}.

-type comparer() :: fun((any(), any()) -> less | equal | greater).

priority_queue.erl

-module(priority_queue).
-export([new/1, is_empty/1, peek/1, enqueue/2, dequeue/1]).
-include_lib("priority_queue.hrl").

-spec new(comparer()) -> priority_queue().
new(Comparer) -> #priority_queue{ root = nil, comparer = Comparer}.

-spec is_empty(priority_queue()) -> true | false.
is_empty(#priority_queue{ root = nil }) -> true;
is_empty(_) -> false.

-spec peek(priority_queue()) -> {ok, any()} | error.
peek(#priority_queue{root = nil}) -> error;
peek(#priority_queue{root = #heap_node{ item = Item}}) -> {ok, Item}.

-spec createHeapNode(any()) ->heap_node().
createHeapNode(Item) -> #heap_node{ item = Item, children = []}.

-spec enqueue(any(), priority_queue()) -> priority_queue().
enqueue(Item, #priority_queue{ root = nil } = Source) -> 
  Root = createHeapNode(Item),
  Source#priority_queue{ root = Root};
enqueue(Item, #priority_queue{ root = Root, comparer =  Comparer} = Source) ->
  NewRoot = merge(Root, createHeapNode(Item), Comparer),
  Source#priority_queue{ root = NewRoot}.

-spec merge(heap_node(), heap_node(), comparer()) -> heap_node().
merge(#heap_node{ item = Item1, children = Children1} = Node1,
      #heap_node{ item = Item2, children = Children2} = Node2,
      Comparer) ->
  case Comparer(Item1, Item2) of
    less -> Node1#heap_node{ children = [Node2 | Children1]};
    _    -> Node2#heap_node{ children = [Node1 | Children2]}
  end.

-spec dequeue(priority_queue()) -> {ok, any(), priority_queue()} | error.
dequeue(#priority_queue{ root = nil }) -> error;
dequeue(#priority_queue{ root = #heap_node{ item = Item, children = Children}, comparer = Comparer } = Source) ->
  NewRoot = pair(Children, Comparer),
  {ok, Item, Source#priority_queue{ root = NewRoot} }.

-spec pair([heap_node()], comparer()) -> heap_node() | nil.
pair([], _) -> nil;
pair([HeapNode], _) -> HeapNode;
pair([HeapNode1 , HeapNode2], Comparer) -> merge(HeapNode1, HeapNode2, Comparer);
pair([HeapNode | Rest], Comparer) -> merge(HeapNode, pair(Rest, Comparer), Comparer).

priority_queue_tests.erl

-module(priority_queue_tests).
-compile(export_all).
-include_lib("eunit/include/eunit.hrl").

is_empty_test() -> 
  Pq1 = create_new_priority_queue(),
  ?assert(priority_queue:is_empty(Pq1)),
  Pq2 = priority_queue:enqueue(5, Pq1),
  ?assertNot(priority_queue:is_empty(Pq2)).

peek_test() ->
  Pq1 = create_new_priority_queue(),
  ?assertEqual(error, priority_queue:peek(Pq1)),
  Pq2 = priority_queue:enqueue(5, Pq1),
  ?assertEqual({ok, 5}, priority_queue:peek(Pq2)).

enqueue_and_dequeue_test() ->
  Pq1 = create_new_priority_queue(),
  ?assertEqual(error, priority_queue:dequeue(Pq1)),
  Pq2 = enqueue([8, 3, 5, 4, 9, 0], Pq1),
  {Items, Pq3} = dequeue(6, Pq2),
  [0, 3, 4, 5, 8, 9] = Items,
  ?assertEqual(error, priority_queue:dequeue(Pq3)).



compare(X, X) -> equal;
compare(X, Y) when X < Y -> less;
compare(_, _) -> greater.

create_new_priority_queue() -> priority_queue:new(fun compare/2).

enqueue([], Pq) -> Pq;
enqueue([Current | Rest], Pq) -> enqueue(Rest, priority_queue:enqueue(Current, Pq)).

dequeue(Count, Pq) -> dequeue(Count, Pq, []).
dequeue(0, Pq, Acc) -> { lists:reverse(Acc), Pq};
dequeue(Count, Pq, Acc) -> 
  {ok, Current, NewPq} = priority_queue:dequeue(Pq),
  dequeue(Count-1, NewPq, [Current | Acc]).

A few of points I specifically want to know:

  • Usage of records/types/specs
  • Returning errors on peek and dequeue methods
  • Pattern matching on merge and dequeue methods. They seems a bit complicated to me
  • Using pattern matching for assertions in unit tests
  • Having variable names like Pq1, Pq2, Pq3 and so on

I tried make it as simple as I could but if it can be improved, please let me know. Any styling tips are also welcome.

\$\endgroup\$
1
\$\begingroup\$

The code look good for me, just one comment - not need explicit export function in test module:

-compile(export_all). %%<-not need

About your questions.

  1. Better - read corresponding section of documentation

  2. Traditionally result value have form {ok,Result} | {error,Reason} if function not use name prefix for explicit notice(for example is_empty from your code)

  3. Explicit the extraction looks even worse.

  4. Macros assertEqual is provided more full information about errors. You can check it by example. For wrong match pattern matching:

    13> eunit:test(priority_queue).
    priority_queue_tests: enqueue_and_dequeue_test...*failed*
    in function priority_queue_tests:enqueue_and_dequeue_test/0     (priority_queue_test
    s.erl, line 22)
    **error:{badmatch,[0,3,4,5,8,9]}
      output:<<"">>
    ...
    

    assertEqual macros:

    17> eunit:test(priority_queue).
    priority_queue_tests: enqueue_and_dequeue_test...*failed*
    in function priority_queue_tests:'-enqueue_and_dequeue_test/0-fun-1-'/2 (priorit
    y_queue_tests.erl, line 24)
    in call from priority_queue_tests:enqueue_and_dequeue_test/0 (priority_queue_tes
    ts.erl, line 24)
    **error:{assertEqual,[{module,priority_queue_tests},
                  {line,24},
                  {expression,"Items"},
                  {expected,[0,3,4,5,1,9]},
                  {value,[0,3,4,5,8,9]}]}
      output:<<"">>
    ...
    
  5. Leave a link to a detailed answer in the chat (thanks @zxq9).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.