1
\$\begingroup\$

I wrote a tail-recursive list-flattening function, but I'm not too happy with it.

a) Is tail-recursion necessary here, or will the function be optimized without it?
b) It's ugly how many clauses there are, and that I have to call out to flatten in the expression of the first clause of flatten_acc

So, how could I do better?

(To be clear, this is a function that completely flattens the list -- e.g. flatten([foo, [[[bar]], [baz]]]) == [foo, bar, baz])

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

flatten_acc([[[H|T0]|T1]|T2], Acc) ->
    flatten_acc([flatten([[H|T0]|T1])|T2], Acc);
flatten_acc([[H|T0]|T1], Acc) ->
    flatten_acc([T0|T1], [H|Acc]);
flatten_acc([[]|T], Acc) ->
    flatten_acc(T, Acc);
flatten_acc([H|T], Acc) ->
    flatten_acc(T, [H|Acc]);
flatten_acc([], Acc) ->
    Acc.

Thanks!

\$\endgroup\$
2
\$\begingroup\$

Little smaller than yours.

% flatten a list
my_flatten([])->
    [] ;
my_flatten([[]|T])->
    my_flatten(T);
my_flatten([[H|T]|T2])->
    my_flatten([H|[T|T2]]);
my_flatten([H|T])->
    [H|my_flatten(T)].

http://erlang99.wordpress.com/2009/01/19/p07-flatten-a-nested-list-structure/

my_flatten_rec(L)->
    lists:reverse(my_flatten_rec([],L)).
my_flatten_rec(Acc,[[]|T])->
    my_flatten_rec(Acc,T);
my_flatten_rec(Acc,[[H|T]|T2])->
    my_flatten_rec(Acc,[H|[T|T2]]);
my_flatten_rec(Acc,[H|T])->
    my_flatten_rec([H|Acc],T);
my_flatten_rec(Acc,[])->
    Acc.
\$\endgroup\$
2
  • \$\begingroup\$ So, this isn't tail-recursive. Does it not need to be? \$\endgroup\$ – amindfv Mar 2 '13 at 19:13
  • \$\begingroup\$ Tail recursion is really only necessary when the recursion could go on indefinitely. In this case, unless it's a list of staggering size/depth, hard to see how you'd blow up the stack. \$\endgroup\$ – macintux Mar 2 '13 at 20:54
2
\$\begingroup\$

I think if you're serious about learning the best way to do this, you should take a look at the source:

%% flatten(List)
%% flatten(List, Tail)
%%  Flatten a list, adding optional tail.

-spec flatten(DeepList) -> List when
      DeepList :: [term() | DeepList],
      List :: [term()].

flatten(List) when is_list(List) ->
    do_flatten(List, []).

-spec flatten(DeepList, Tail) -> List when
      DeepList :: [term() | DeepList],
      Tail :: [term()],
      List :: [term()].

flatten(List, Tail) when is_list(List), is_list(Tail) ->
    do_flatten(List, Tail).

do_flatten([H|T], Tail) when is_list(H) ->
    do_flatten(H, do_flatten(T, Tail));
do_flatten([H|T], Tail) ->
    [H|do_flatten(T, Tail)];
do_flatten([], Tail) ->
    Tail.
\$\endgroup\$
1
\$\begingroup\$

How about this:

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

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

The tail recursion is not necessary in this case but makes it much more easy to read and clarity is king.

\$\endgroup\$
0

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.