CODEWITHSUNDEEP
listerlangtail-recursion
Bert Smith
Bert Smith

Reputation: 27

Erlang, finding the number of occurrences of a number in a list

I am new to Erlang and trying to write a program that will take a list of numbers like this [1,5,4,5,3,2,2,8,11] as an input parameter of a function. The function should return a list of tuples that records the number and it's number of appearances in the list like so.

[{1,1},{2,2},{3,1},{4,1},{5,1},{8,1},{11,1}].

I have the following code

list([]) ->
  [];
list([First | Rest])  ->  
  [{First,+1} | list(Rest)].

But I dont understand how it is that I can do the counting operation? Thanks

Upvotes: 1

Views: 826

Answers (3)

7stud
7stud

Reputation: 48599

See maps:update_with/4:

frequencies(List) ->
    frequencies(List, #{}).

frequencies([], Freqs) ->
    maps:to_list(Freqs);
frequencies([H|T], Freqs) ->
    Incrementer = fun(Count) -> Count+1 end,
    NewFreqs = maps:update_with(H, Incrementer, _Default=1, Freqs),
    frequencies(T, NewFreqs).

In the shell:

1> a:frequencies([1,5,4,5,3,2,2,8,11]).
[{1,1},{2,2},{3,1},{4,1},{5,2},{8,1},{11,1}]

Do you mind explaining how this code works step by step

This part:

frequencies(List) ->
    frequencies(List, #{}).

let's you call the frequencies/1 function by passing it just a list. The list is then relayed to the frequencies/2 function along with an empty map to store the results.

This part:

frequencies([H|T], Freqs) ->
    Incrementer = fun(Count) -> Count+1 end,
    NewFreqs = maps:update_with(H, Incrementer, _Default=1, Freqs),
    frequencies(T, NewFreqs).

uses pattern matching to remove the first number from the List, H, then calls the function maps:update_with/4 passing the first number as the Key that should be updated in the map. The other arguments for maps:update_with/4 are the map to be updated,Freqs, and a function, Incrementer, which receives the Value associated with the Key in the map as an argument. The return value of the Incrementer function is the new Value that should be inserted for the Key in the map. If the Key does not exist in the map, then a new Key is entered into the map with the _Default Value.

maps:update_with/4 returns the updated map, NewFreqs, which is passed as an argument to the recursive function call:

frequencies(T, NewFreqs).

The first argument, T, is a List containing the remaining numbers. When all the numbers in the List have been removed, then the recursive function call will be:

frequencies([], #{ results in this map })

That function call will match this function clause:

frequencies([], Freqs) ->
    maps:to_list(Freqs);

and maps:to_list/1 converts a map to a list of {Key, Value} tuples. Because there is no recursive function call in the body of that function clause, the recursion ends, and the list of tuples is returned.

Maybe different variable names would make the code easier to follow:

frequencies(List) ->
    frequencies(List, _ResultsMap=#{}).

frequencies([Key|Keys], ResultsMap) ->
    Incrementer = fun(Value) -> Value+1 end,
    NewResultsMap = maps:update_with(Key, Incrementer, _Default=1, ResultsMap),
    frequencies(Keys, NewResultsMap);
frequencies([], ResultsMap) ->
    maps:to_list(ResultsMap).

Upvotes: 2

tonys
tonys

Reputation: 3984

You can do it as a one-liner, but breaking it down into steps:

List  = [1,5,4,5,3,2,2,8,11].
Keys  = lists:usort(List).
Count = fun(V,L) -> length(lists:filter(fun(E) -> E == V end, L)) end.

> lists:map(fun(K) -> { K, Count(K,List) } end, Keys).

Result:

[{1,1},{2,2},{3,1},{4,1},{5,2},{8,1},{11,1}]

Upvotes: 3

choroba
choroba

Reputation: 241828

Probably not the fastest (use a map instead of a tuple list if speed is a concern):

count([]) ->
    [];
count([H|T]) ->
    count2([H|T], []).

count2([H|T], L) ->
    case lists:keyfind(H, 1, L) of
        {H, X} ->
            L2 = lists:append(lists:delete({H, X}, L), [{H,X+1}]) ;
        false ->
            L2 = lists:append(L, [{H, 1}])
    end,
    count2(T, L2);
count2([], L) ->
    L.

With maps, the code would be simpler:

count([]) ->
    #{};
count(L) ->
    count2(L, #{}).

count2([H|T], M) ->
    Y = case maps:is_key(H, M) of
            true  -> #{H := X} = M,
                     X + 1;
            false -> 1
        end,
    count2(T, M#{H => Y});
count2([], M) ->
    M.

Upvotes: 3

Related Questions