JS - rekursion för att hitta matchande element i array med arrayer

Permalänk
Medlem

JS - rekursion för att hitta matchande element i array med arrayer

Hej

Har lite problem med en js-funktion för att hitta ett element i en array som kan ha underarrayer. Började tänka på lite försent, kanske har nån nattsuddare en bättre förståelse.

const findCat = function findCat(catName, catArray) { if (catArray.filter(cat => cat.get('name') === catName)[0]) { // case (1) where there's a name match return catArray.filter(cat => cat.get('name') === catName)[0]; // return the name match object } else if (catArray.filter(cat => cat.get('type') === 'group')[0]) { // case (2) there's at least one group of cats const groupcatArray = catArray.filter(cat => cat.get('type') === 'GROUP'); // all groups of cats groupcatArray.map(groupCat => { return findCat(catName, groupCat.get('cats')}); // recurse on every group of cats } else { // case 3) there's no matching case nor group of cats at this level return false; } } -- let myCat = findCat('Nemo', getAllCatsArray());

Meningen är att en kattArray kan ha bara katter, den kan även ha eller eller flera grupper med katter (underarrayer) som i sin tur..likadant, så att det blir ett träd potentiellt. Problemet är att när en match sker och jag skriver till konsollen vad den tänker returnera i case 1 (basfallet) så returneras det ändock ej. myCat remains undefined.

Om jag i case 2 säger "return findCat(catName, catArray.filter(cat => cat.get('type') === 'group')[0]" så returneras en matchande katt så länge den ligger i den första gruppen. Logiskt behöver man kolla samtliga grupper ..det där det där att kombinera en iteration över en array med en return i det rekursiva anropet som jag int helt begrip så här på nattkvist.

Tar tacksamt emot råd

Permalänk
Medlem

Du returnerar inget i case 2. På arrayen kör du en funktion för varje element (map), men du returnerar aldrig något returvärde. Utan att testat kan du säkert byta ut groupcatArray-raden till:

return groupcatArray.some(groupCat => findCat(catName, groupCat.get('cats')));

Permalänk
Medlem
Skrivet av Johan_S:

Du returnerar inget i case 2. På arrayen kör du en funktion för varje element (map), men du returnerar aldrig något returvärde. Utan att testat kan du säkert byta ut groupcatArray-raden till:

return groupcatArray.some(groupCat => findCat(catName, groupCat.get('cats')));

Hej, tack för svaret.

Om jag gör så, sätter return framför array-metoden snarare än varje rekursivt anrop så returnerar funktionen vid en namn-match istället för ett kattobjekt (eller inget) värdet true.

Har inte hittills funnit något exempel på just foreach-liknande rekursivt anrop i steg 2; man kan kanske förenkla hela funktionen så den slipper det och bara gör ett anrop i steg 2 men det hade varit lite snyggt om det här hade funkat.

Edit. Provade en for-loop för att iterera över groupCatArray istället för en högre nivå-metod:

for (let step = 0; step < groupCatArray.length; step++) { return findCat(catName, groupCatArray[step].get('cats'))

vilket gör det jag tänker mig, dvs den returnerar ett kattobjekt vid en träff. Min fråga blir då snarast: Går det att använd en airbnb-kosher metod för detta? Vill inte returnera det forEach()(inget) eller map()(array) eller some(bool) returnerar, vill bara starta det rekursiva anropet med varje objekt i en array. Tror jag, men jag har inte riktigt högre nivås tänkande än : )

justerat mål
Permalänk
Medlem
Skrivet av Kolsvart Katt:

for (let step = 0; step < groupCatArray.length; step++) { return findCat(catName, groupCatArray[step].get('cats'))

Att ha en return utan villkor runt i en loop ringer varningsklockor hos mig.

Det där betyder – om jag inte är helt ute och cyklar – i praktiken:

if (groupCatArray.length > 0) { return findCat(catName, groupCatArray[0].get('cats'))

---

Om det finns flera katter med samma namn, vilken katt ska funktionen då välja? Jag tycker personligen att en depth-first search är enklare att implementera rekursivt än en breadth-first search, så om du kan komma undan med det kan det hjälpa.

Permalänk
Medlem
Skrivet av lydell:

Att ha en return utan villkor runt i en loop ringer varningsklockor hos mig.

Det där betyder – om jag inte är helt ute och cyklar – i praktiken:

if (groupCatArray.length > 0) { return findCat(catName, groupCatArray[0].get('cats'))

---

Om det finns flera katter med samma namn, vilken katt ska funktionen då välja? Jag tycker personligen att en depth-first search är enklare att implementera rekursivt än en breadth-first search, så om du kan komma undan med det kan det hjälpa.

Hej, du har rätt, och varningsklockor där är rimligt. I tänkt användande gör antagande att varje katt har ett unikt namn. Något är fel tidigare så att säga om två katter har samma namn.

Ska läsa på lite om breadth-first vs depth-first, tack för rådet. Osäker på om det påverkar frågeställningen ovan men det är en värdefull sak att begrunda ändå för prestanda.

Permalänk
Medlem

Ett smidigt sätt att hitta den första träffen på något i en array är Array.prototype.find. Här är ett försök med att använda det (depth-first):

function findCat(catName, items) { return items.find((item) => { switch (item.get("type")) { case "cat": return item.get("name") === catName; case "group": return findCat(catName, item.get("cats")); } }); }

Det funkar bra när katten vi söker ligger direkt i arrayen, men när den ligger i en grupp returnerar funktionen hela gruppen som innehåller katten istället för bara katten.

Detta är en begränsning av .find – du kan hitta en befintlig sak (Cat | Group) i listan men inte byta typ (Cat).

En del språk (men inte JavaScript) har en .findMap-funktion för detta. Istället för att returnera en boolean i callbacken, så returnerar man undefined för en icke-träff och valfritt annat värde vid träff. Det slutgilitga värdet blir antingen det valfria värdet eller undefined.

Här är findCat med findMap:

function findCat(catName, items) { return findMap(items, (item) => { switch (item.get("type")) { case "cat": return item.get("name") === catName ? item : undefined; case "group": return findCat(catName, item.get("cats")); } }); }

Så här kan man implementera findMap:

function findMap(items, f) { for (const item of items) { const value = f(item); if (value !== undefined) { return value; } } return undefined; }

Om du absolut inte vill använda en for-loop någonstans kan man göra något i den här stilen istället:

function findMap(items, f) { return findMapHelper(items, f, 0); } function findMapHelper(items, f, index) { if (index >= items.length) { return undefined; } const item = items[index]; const value = f(item); return value !== undefined ? value : findMapHelper(items, f, index + 1); }

Permalänk
Medlem

Hej, oj, tack! "The more you know the more you know you don't know"
Har fått en del att tänka på.
Splendid exempel på depth-first.