CODEWITHSUNDEEP
functional-programmingerlang
GuessBurger
GuessBurger

Reputation: 478

Sublists of N length function in Erlang style

I've been learning Erlang and tried completing some practise functions. I struggled making one function in particular and think it might be due to me not thinking "Erlang" enough.

The function in question takes a list and a sublist size then produces a list of tuples containing the number of elements before the a sublist, the sublist itself and the number of elements after the sublist. For example

sublists(1,[a,b,c])=:=[{0,[a],2}, {1,[b],1}, {2,[c],0}].
sublists(2,[a,b,c])=:=[{0,[a,b],1}, {1,[b,c],0}].

My working solution was

sublists(SubListSize, [H | T]) ->
    Length = length(1, T),
    sublists(SubListSize, Length, Length-SubListSize, [H|T], []).
sublists(_, _, -1, _, Acc) -> lists:reverse(Acc);
sublists(SubSize, Length, Count, [H|T], Acc) ->
    Sub = {Length-SubSize-Count, grab(SubSize, [H|T],[]),Count},
    sublists(SubSize, Length, Count-1, T, [Sub|Acc]).

length(N, []) -> N;
length(N, [_|T]) -> length(N+1, T).

grab(0, _, Acc) -> lists:reverse(Acc);
grab(N, [H|T], Acc) -> grab(N-1, T, [H|Acc]).

but it doesn't feel right and I wondered if there was a better way?

There was an extension that asked for the sublists function to be re-implemented using a list comprehension. My failed attempt was 

sublist_lc(SubSize, L) ->
    Length = length(0, L),
    Indexed = lists:zip(L, lists:seq(0, Length-1)),
    [{I, X, Length-1-SubSize} || {X,I} <- Indexed, I =< Length-SubSize].

As I understand it, list comprehensions can't see ahead so I was unable to use my grab function from earlier. This again makes me thing there must be a better way of solving this problem.

Upvotes: 1

Views: 779

Answers (1)

Steve Vinoski
Steve Vinoski

Reputation: 20014

I show a few approaches below. All protect against the case where the requested sublist length is greater than the list length. All use functions from the standard lists module.

The first one uses lists:split/2 to capture each sublist and the length of the remaining tail list, and uses a counter C to keep track of how many elements precede the sublist. The length of the remaining tail list, named Rest, gives the number of elements that follow each sublist.

sublists(N,L) when N =< length(L)  ->
    sublists(N,L,[],0).
sublists(N,L,Acc,C) when N == length(L) ->
    lists:reverse([{C,L,0}|Acc]);
sublists(N,[_|T]=L,Acc,C) ->
    {SL,Rest} = lists:split(N,L),
    sublists(N,T,[{C,SL,length(Rest)}|Acc],C+1).

The next one uses two lists of counters, one indicating how many elements precede the sublist and the other indicating how many follow it. The first is easily calculated by simply counting from 0 to the length of the input list minus the length of each sublist, and the second list of counters is just the reverse of the first. These counter lists are also used to control recursion; we stop when each contains only a single element, indicating we've reached the final sublist and can end the recursion. This approach uses the lists:sublist/2 call to obtain all but the final sublist.

sublists(N,L) when N =< length(L) ->
    Up = lists:seq(0,length(L)-N),
    Down = lists:reverse(Up),
    sublists(N,L,[],{Up,Down}).
sublists(_,L,Acc,{[U],[D]}) ->
    lists:reverse([{U,L,D}|Acc]);
sublists(N,[_|T]=L,Acc,{[U|UT],[D|DT]}) ->
    sublists(N,T,[{U,lists:sublist(L,N),D}|Acc],{UT,DT}).

And finally, here's a solution based on a list comprehension. It's similar to the previous solution in that it uses two lists of counters to control iteration. It also makes use of lists:nthtail/2 and lists:sublist/2 to obtain each sublist, which admittedly isn't very efficient; no doubt it can be improved.

sublists(N,L) when N =< length(L) ->
    Up = lists:seq(0,length(L)-N),
    Down = lists:reverse(Up),
    [{U,lists:sublist(lists:nthtail(U,L),N),D} || {U,D} <- lists:zip(Up,Down)].

Oh, and a word of caution: your code implements a function named length/2, which is somewhat confusing because it has the same name as the standard length/1 function. I recommend avoiding naming your functions the same as such commonly-used standard functions.

Upvotes: 3

Related Questions