CODEWITHSUNDEEP
erlang
Chris Snow
Chris Snow

Reputation: 24596

how to efficiently build erlang lists in natural order?

In the Programming Erlang book, there is some example pseudo code that shows a pattern for efficiently adding elements to the head of a list:

some_function([H|T], ..., Result, ...) ->
    H1 = ... H ...,
    some_function(T, ..., [H1|Result], ...);
some_function([H|T], ..., Result, ...) ->
    {..., Result, ...}.

I'm still getting used to functional programming so the above example is a little too abstract for me to understand at the moment.

I think it will be easier to understand if there is a concrete implementation of the pattern that I could dissect.

Question: Is there a simple concrete implementation of this pattern that someone can provide?

Upvotes: 0

Views: 159

Answers (3)

R. Carbone
R. Carbone

Reputation: 71

This takes a factorized list, i.e.

[[],[2],[3],[2,2],[5],[2,3],[7],[2,2,2],etc...]

and removes all the primes.

remove_primes([HD|TL], Results) -> 

    case length(HD) of
           0 -> % You're at 1
                  remove_primes (TL , Results);
           1 -> % Its a prime, remove it, and keep going
                  remove_primes( TL , Results) ;
           _ -> % its not prime, leave it in and keep going.  
                  remove_primes(TL, [ HD | Results]) 
    end;

remove_primes([], Result) -> 
                 {Result}.

The structure Joe Armstrong was alluding too, is the standard structure of walking a list and applying a function to each element on the list. In this case, I desired to treat each element differently depending on its contents.

In practice, it is much easier to to use maps, filters and such, so I believe you will see that much more often - but as you seem to know, understanding the basics is vital to becoming a proficient functional programmer.

In hopes centralize information pertaining to 'building lists in natural order', does anyone know why pattern matching at the function level, works, 'but unpacking' a variable does not? (compare this)(it does not work)

remove_primes(Factorized_List, Results) -> 
    [HD|TL] = Factorized_List, % unpack the list   <-------------

        case length(HD) of
               0 -> % You're at 1
                  remove_primes (TL , Results);
           1 -> % Its a prime, remove it, and keep going
                  remove_primes( TL , Results) ;
           _ -> % its not prime, leave it in and keep going.  
                  remove_primes(TL, [HD|Results]) 
        end;

remove_primes([], Result) -> 
                 {Result}.

I believe this leads to more readable code, but it does not seem to work.

-rC

Upvotes: 2

7stud
7stud

Reputation: 48599

Here is the only way I can get your pattern to execute:

some_func([H|T], 4, Result, 4) -> 
    H1 = H * 2,
    some_func(T, 3, [H1|Result], 4); 
some_func([H|T], 3, Result, _) ->
    {H, Result, T}.

--output:--

25> a:some_func([1, 2, 3], 4, [], 4).  
{2,[2],[3]}

...which does nothing useful.

The pattern in the pseudo code makes no sense to me, so I'll join you in your confusion.

Here is another attempt:

some_func([H|T], [_|T2], Result, Y) -> 
    H1 = H * Y,
    some_func(T, T2, [H1|Result], Y); 
some_func([H|T], [], Result, _) ->
    {H, Result, T}.


--output:--
34> a:some_func([1, 2, 3, 4], [one, two, three], [], 2).
{4,[6,4,2],[]}

Upvotes: 1

erszcz
erszcz

Reputation: 1660

Let's say that we want a function which behaves a like the uniq command. The function takes a list of elements and returns a list with all consecutive occurrences of an element substituted with a single occurrence of that element. One of the possible approaches is presented below:

uniq(L) ->
    uniq(L, []).

uniq([], Acc) ->
    lists:reverse(Acc);
uniq([H, H | T], Acc) ->
    uniq([H | T], Acc);
uniq([H | T], Acc) ->
    uniq(T, [H | Acc]).

We build up an accumulator, by inserting new elements at the head of the Acc list (cheapest insertion cost) and once we're done, we reverse the whole list to get the initial order of elements back.

We "visit" some of the elements of the initial list twice, but the total cost is still linear, i.e. only dependent on the number of elements of the initial list.

Upvotes: 2

Related Questions