Сгладить список вложенных списков в 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

Ключ вопроса - «делить и побеждать».

Еще одна дополнительная функция «списки: обратная» и оператор «++» используются для сохранения времени программирования.

 

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

для теста: тест: my_flat ([[1, [2, [3], []]], [[[4]]], [5,6]], []) ,

Answer 3

Некоторые различные решения, становятся умнее и умнее:

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

Это все только сопоставления с образцом и рекурсии, но они могут быть улучшены wi th некоторые проверки типа защиты. Использование ++ неэффективно, поскольку оно копирует список каждый раз. Модуль lists использует версию последнего с тестом типа защиты вместо последнего предложения.

Answer 4

Довольно лаконичный и простой вариант:

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

Answer 5

конкатенации/1, как это определено в книге работает как Свести функции, которая выравнивается вниз только один уровень. ([[1],[2]] становится [1,2], [[[1]],[[2]]] становится [[1],[2]] и т. Д.). Стратегия, предложенная в подсказке, заключается в том, чтобы полностью сгладить, не определяя новую логику в flatten/1, а используя concatenate/1 в рекурсивных вызовах flatten/1.

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.