CODEWITHSUNDEEP
listerlang
Vayn
Vayn

Reputation: 2717

Flatten a list of nested lists in Erlang

I'm working on the exercises in Erlang Programming.

The question is

Write a function that, given a list of nested lists, will return a flat list.

Example: flatten([[1,[2,[3],[]]], [[[4]]], [5,6]]) ⇒ [1,2,3,4,5,6].

Hint: use concatenate to solve flatten.

And here is my concatenate function

%% concatenate([[1,2,3], [], [4, five]]) ⇒ [1,2,3,4,five].
concatenate([X|Xs]) -> concat(X, Xs, []).
concat([X|Xs], T, L) -> concat(Xs, T, [X|L]);
concat([], [X|Xs], L) -> concat(X, Xs, L);
concat([], [], L) -> reverse(L).

I really want to know an elegant way to implement flatten. I've spent hours solving this exercise.

UPDATE: I forget most important prerequisite. Is it possible solving this problem with only recursion and pattern matching?

Upvotes: 6

Views: 7558

Answers (6)

Márcia Matias
Márcia Matias

Reputation: 1

Here's another option, no accumulator and with Erlang list append operation (++):

flatten([[_|_]=R | Tail]) -> flatten(R)++flatten(Tail);
flatten([V|Tail]) -> flatten(V)++flatten(Tail);
flatten([])->[];
flatten(V)->[V].

Upvotes: 0

Pantalones
Pantalones

Reputation: 21

concatenate/1 as defined in the book works as a flatten function which flattens down only one level. ([[1],[2]] becomes [1,2], [[[1]],[[2]]] becomes [[1],[2]], etc.) The strategy suggested in the hint is to flatten completely not by defining new logic in flatten/1 but by using concatenate/1 in flatten/1's recursive calls.

concatenate(Ls) ->
    reverse(concatenate(Ls, [])).

concatenate([], Acc) ->
    Acc;
concatenate([[]|Rest], Acc) ->
    concatenate(Rest, Acc);
concatenate([[H|T]|Rest], Acc) ->
    concatenate([T|Rest], [H|Acc]);
concatenate([H|T], Acc) ->
    concatenate(T, [H|Acc]).

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

flatten([], Acc) ->
    Acc;
flatten(L, Acc) ->
    Concatted = concatenate(L),
    [Non_lists|Remainder] = find_sublist(Concatted),
    flatten(Remainder, concatenate([Acc, Non_lists])).

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

find_sublist([], Acc) ->
    reverse(Acc);
find_sublist(L = [[_|_]|_], Acc) ->
    [reverse(Acc)|L];
find_sublist([H|T], Acc) ->
    find_sublist(T, [H|Acc]).

tests() ->
    [1,2,3,4,4,5,6,7,8] = flatten([[1,[2,[3],[]]], [[[4,[4]]]], [[5],6], [[[]]], [], [[]], [[[7, 8]]]]),
    [1,2] = flatten([[1,2]]),
    [1,2,3] = flatten([[1],[2],[3]]),
    [1,2,3,4,5,6] = flatten([[1,[2,[3],[]]], [[[4]]], [5,6]]),
    tests_successful.

Upvotes: 2

Hynek -Pichi- Vychodil
Hynek -Pichi- Vychodil

Reputation: 26121

Pretty concise and straightforward version:

append([H | T], L) -> [H | append(T, L)];
append([], L) -> L.

flatten([[_|_]=H|T]) -> append(flatten(H), flatten(T));
flatten([[]|T]) -> flatten(T);
flatten([H|T]) -> [H|flatten(T)];
flatten([]) -> [].

Upvotes: 2

rvirding
rvirding

Reputation: 20916

Some different solutions, getting smarter and smarter:

%% Lift nested lists to the front of the list.
flatten1([[H|T1]|T2]) -> flatten1([H,T1|T2]);
flatten1([[]|T]) -> flatten1(T);
flatten1([E|T]) -> [E|flatten1(T)];
flatten1([]) -> [].

or

%% Keep a list of things todo and put tails onto it.
flatten2(L) -> flatten2(L, []).

flatten2([H|T], Todo) ->
    flatten2(H, [T|Todo]);
flatten2([], [H|Todo]) -> flatten2(H, Todo);
flatten2([], []) -> [];
flatten2(E, Todo) -> [E|flatten2(Todo, [])].

or

%% Work from the back and keep a tail of things done.
flatten3(L) -> flatten3(L, []).

flatten3([H|T], Tail) ->
    flatten3(H, flatten3(T, Tail));
flatten3([], Tail) -> Tail;
flatten3(E, Tail) -> [E|Tail].

These are all with only pattern matching and recursion, but they can be improved with some guard type tests. Using ++ is inefficient as it copies the list every time. The lists module uses a version of the last one with a guard type test instead of the last clause.

Upvotes: 6

Odobenus Rosmarus
Odobenus Rosmarus

Reputation: 5998

I would try this way

flatten(X) -> lists:reverse(flatten(X,[])).

flatten([],Acc) -> Acc;
flatten([H|T],Acc) when is_list(H) -> flatten(T, flatten(H,Acc));
flatten([H|T],Acc) -> flatten(T,[H|Acc]).

testing

my:flatten([[1,[2,[3],[]]], [[[4]]], [5,6]]).
[1,2,3,4,5,6]

UPD: or this way, without guards and reverse, only recursive calls and pattern matching.

flatten(X)               -> flatten(X,[]).

flatten([],Acc)          -> Acc;
flatten([[]|T],Acc)      -> flatten(T, Acc);
flatten([[_|_]=H|T],Acc) -> flatten(T, flatten(H,Acc));
flatten([H|T],Acc)       -> flatten(T,Acc++[H]) .

Upvotes: 17

Chen Yu
Chen Yu

Reputation: 4077

The question's key is "divide and conquer".

Another extra function "lists:reverse" and an operator "++" are used for saving programing time.



my_flat([],Result)->
    lists:reverse(Result);
my_flat([H|T],Result) when is_atom(H) ->
    case T of
    []-> 
        my_flat([],[H|Result]);
    _Else ->
        my_flat(T,[H|Result])
    end;
my_flat([H|T],Result) when is_number(H)->
    case T of
    []->
        my_flat([],[H|Result]);
    _Else ->
        my_flat(T,[H|Result])
    end;
my_flat([H|T],Result) ->
my_flat(H,Result)++my_flat(T,[]).

for your test: test:my_flat([[1,[2,[3],[]]], [[[4]]], [5,6]],[]).

Upvotes: 0

Related Questions