Erlang

Question

में नेस्टेड सूचियों की एक सूची फ़्लैट करें मैं एरलांग प्रोग्रामिंग में अभ्यास पर काम कर रहा हूं।

सवाल

एक समारोह है कि, नेस्टेड सूचियों की एक सूची दी गई, एक फ्लैट सूची प्रदान करेगा लिखें है।

उदाहरण: 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] 

युपीडी: या इस तरह से, गार्ड के बिना और रिवर्स, केवल पुनरावर्ती कॉल और पैटर्न मिलान।

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

ये केवल पैटर्न मिलान और प्रत्यावर्तन के साथ सभी कर रहे हैं, लेकिन वे वाई में सुधार किया जा सकता है कुछ गार्ड प्रकार परीक्षण। ++ का उपयोग अक्षम है क्योंकि यह हर बार सूची की प्रतिलिपि बनाता है। 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

CONCATENATE/1 के रूप में किताब में परिभाषित एक समतल समारोह जो केवल एक ही स्तर नीचे सपाट रूप में काम करता है। ([[1],[2]][1,2] बन जाता है, [[[1]],[[2]]][[1],[2]], आदि बन जाता है) संकेत में सुझाई गई रणनीति फ़्लैटन/1 में नए तर्क को परिभाषित करके पूरी तरह से फ़्लैट करना नहीं है बल्कि फ्लैटन/1 की रिकर्सिव कॉल में कॉन्सटेनेट/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.