Kérem, vezessen végig ezen az Erlang programozási rekurzív mintán

Ezt a függvényt először hívják:

merge(Xs,Ys) -> lists:reverse(mergeL(Xs,Ys,[])).

A mergeL-nek átadott üres lista [] az akkumulátor – innen jön a válasz. Ne feledje, hogy az első függvény a mergeL-t hívja meg - a bal oldali merge.

Tegyük fel, hogy ezt a függvényt így hívják:

merge([1, 2, 3], [a, b, c])

Két azonos hosszúságú lista. Ez az első függvény ezután meghívja a mergeL-t:

mergeL([X|Xs],Ys,Zs) ->  mergeR(Xs,Ys,[X|Zs]);
mergeL([],[],Zs) ->  Zs.

A bal oldali összevonásban 2 kitétel található. Az argumentumokkal rendelkező mergeL hívás felülről lefelé sorrendben egyezik meg ezekkel a záradékokkal.

E záradékok közül a másodiknak három paramétere van – ezek közül az első kettő üres lista []. Azonban amikor először mergeL-nek hívják, ez a két lista nem üres, hanem az Xs és Ys listák, tehát az első záradék egyezik.

Törjük szét a meccseket. Ez az egyesítés felhívása:

mergeL([1, 2, 3], [a, b, c], [])

és a következő módon illeszkedik az első tagmondathoz:

X = 1
Xs = [2, 3]
Ys = [a, b, c]
Zs = []

Ennek oka a lista speciális formája:

[X | Xs]

Ez azt jelenti, hogy az X-et a lista elejére kell illeszteni (egy egyedi elemre), és az X-eket a lista (lista) végére kell állítani.

Ezután felállítjuk az új függvényhívást. Hozzáadhatjuk az X értéket a Zs lista elejéhez, ugyanúgy, ahogy a mintával párosítottuk, így megkapjuk az első mergeR hívást:

mergeR([2, 3], [a, b, c], [1])

Az utolsó argumentum egy egyelemes lista, amelyet egy üres lista élére adunk.

Ez a cipzár a végéig.

Valójában a mergeL utolsó kitétele redundáns. Ez a funkció definíció szerint kimerül a mergeR utolsó záradékában (de ezt meghagyom gyakorlatnak az olvasó számára).

lépj át rajta

merge([1,2],[3,4])
reverse(mergeL([1,2],[3,4],[]))
reverse(mergeR([2],[3,4],[1]))
reverse(mergeL([2],[4],[3,1]))
reverse(mergeR([], [4], [2,3,1]))
reverse(mergeL([], [], [4,2,3,1]))
reverse([4,2,3,1])
[1,3,2,4]

Mindig jó ezeket a funkciókat kézzel dolgozni egy papírlapon, kis bemenettel, ahol megpróbálja kitalálni. Gyorsan látni fogja, hogyan működik.

A példa azt jelenti, hogy meghatároz néhány állapotot, amelyeken a rekurzió keresztül fog menni. Három „függvény” van meghatározva: merge, mergeL és mergeR.

Az összevonandó listák az X-ek és az Y-k, míg a Z-k az egyesítés eredménye.

Az összevonás a „merge” meghívásával és két lista megadásával kezdődik. Az első lépés a mergeL meghívása a két összevonandó listával és egy üres eredménykészlettel.

Az [X|Xs] a lista első elemét veszi fel (nagyon úgy, mint az array_shift). Ez az elem hozzáadódik az eredményhalmaz fejéhez ([X|Zs] ezt teszi). Ezt az eredményhalmazt (amely most egy elemet tartalmaz) átadja a következő hívásnak, a mergeR-nek. A mergeR ugyanezt teszi, csak vesz egy elemet a második listából. Ez a viselkedés mindaddig folytatódik, amíg a mergeL vagy mergeR számára betáplált listák nem üresek.

Ha a mergeL vagy mergeR meghívása két üres listával ([]) és egy eredménykészlettel (Zs) történik, akkor az eredményhalmazt adja vissza (és nem hajt végre újabb futást, így leállítja a rekurziót).

Összegzés:

A rekurzió eleje az első sor, amely meghatározza az „egyesítést”. Ez az indítás elindítja az egészet az első mergeL meghívásával.

A rekurzió törzse a 2. és 4. sor, amelyek meghatározzák a viselkedést, vagy a mergeL és mergeR, amelyek mindketten hívják egymást.

A rekurzió stopját a 3. és 5. sor határozza meg, amelyek alapvetően elmondják az egésznek, hogy mit kell tenni, ha nincs több elem a tömbben.

Remélem ez segít!

Mindig azokat a függvényeket keresem, amelyek először leállítják a rekurziót, ebben az esetben:

mergeL([],[],Zs) ->  Zs.

és

mergeR([],[],Zs) ->  Zs.

mindkettő alapvetően befejezi az "egyesítést", amikor az első két paraméter üres lista.

Tehát akkor megnézem a függvény első hívását:

merge(Xs,Ys) -> lists:reverse(mergeL(Xs,Ys,[])).

Ha egy másodpercre figyelmen kívül hagyja a fordítottját, látni fogja, hogy az utolsó paraméter egy üres lista. Tehát azt várnám, hogy a különböző mergeL és mergeR függvények áthelyezik a tömb elemeit a végső paraméterbe - és amikor mindegyiket áthelyezik, akkor a függvény lényegében leáll (bár végül természetesen a fordított függvény meghívása)

És pontosan ezt teszik a többi funkciók:

mergeL([X|Xs],Ys,Zs) ->  mergeR(Xs,Ys,[X|Zs]);

veszi X első elemét, és behelyezi a Z tömbbe, és

mergeR(Xs,[Y|Ys],Zs) ->  mergeL(Xs,Ys,[Y|Zs]);

veszi Y első elemét, és behelyezi a Z tömbbe. A mergeR meghívása a mergeL-ből és fordítva az interleave részt végzi.

Érdekes látni (és könnyen javítható), hogy az X és Y tömböknek azonos hosszúságúaknak kell lenniük, különben a mergeL vagy mergeR függvényt egy üres tömbbel fogja meghívni X-ben vagy Y-ben – és ez sem fog egyezni [ X | Xs] vagy [ Y | Ys].

A fordított oka pedig egyszerűen az [ X | relatív hatékonysága körül keresendő Zs] vs [ Zs | X]. Az előbbi sokkal hatékonyabb.