在Erlang中展平嵌套列表的列表

Question

我正在研究Erlang编程中的练习.

问题是

编写一个函数,给定一个嵌套列表列表,将返回一个平面列表.

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

提示:concatenate用来解决flatten.

这是我的concatenate功能

%% 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).

我真的想知道一种优雅的实施方式flatten.我花了好几个小时来解决这个问题.

更新:我忘记了最重要的先决条件.只有递归和模式匹配才能解决这个问题吗？

Answer 1

我会这样试试

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]).

测试

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

UPD:或者这样,没有防护和反向,只有递归调用和模式匹配.

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]) .

Answer 2

一些不同的解决方案,变得更聪明,更聪明:

%% 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([]) -> [].

要么

%% 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, [])].

要么

%% 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].

这些都只有模式匹配和递归,但可以通过一些保护类型测试来改进它们.使用++效率很低,因为它每次都会复制列表.该lists模块使用最后一个版本的版本,带有保护类型测试而不是最后一个子句.