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\$

3 Answers 3

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
    Commented Mar 2, 2013 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
    Commented Mar 2, 2013 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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.