W jaki sposób działa spłaszczanie listy cyklicznej?

Question

Jakiś czas temu this was asked and answered na liście mailingowej Scala:

Kevin:

Biorąc pod uwagę niektóre zagnieżdżone struktury: List[List[...List[T]]] jaki jest najlepszy (najlepiej wpisać bezpieczny) sposób spłaszczyć go do List[T]

Jesper:

połączenie iMPL icits i domyślne argumenty działa:

case class Flat[T, U](fn : T => List[U]) 

implicit def recFlattenFn[T, U](implicit f : Flat[T, U] = Flat((l : T) 
=> List(l))) = 
    Flat((l : List[T]) => l.flatMap(f.fn)) 

def recFlatten[T, U](l : List[T])(implicit f : Flat[List[T], U]) = f.fn(l) 

Przykłady:

scala> recFlatten(List(1, 2, 3)) 
res0: List[Int] = List(1, 2, 3) 

scala> recFlatten(List(List(1, 2, 3), List(4, 5))) 
res1: List[Int] = List(1, 2, 3, 4, 5) 

scala> recFlatten(List(List(List(1, 2, 3), List(4, 5)), List(List(6, 7)))) 
res2: List[Int] = List(1, 2, 3, 4, 5, 6, 7) 

czekałem na ten kod na chwilę. Nie wiem, jak to działa. Wydaje się, że w grę wchodzi pewna rekurencja ... Czy ktoś może rzucić trochę światła? Czy są inne przykłady tego wzoru i czy ma on nazwę?

Answer 1

Och, wow, to jest stare! Zacznę od czyszczenia kod trochę i pociągnięcie go do aktualnych konwencji idiomatyczne:

case class Flat[T, U](fn: T => List[U]) 

implicit def recFlattenFn[T, U](
    implicit f: Flat[T, U] = Flat((xs: T) => List(xs)) 
) = Flat((xs: List[T]) => xs flatMap f.fn) 

def recFlatten[T, U](xs: List[T3])(implicit f: Flat[List[T], U]) = f fn xs 

Następnie, bez dalszej zwłoki, załamać kod.Po pierwsze, mamy Flat Klasa:

case class Flat[T, U](fn: T => List[U]) 

to nic więcej niż o nazwie wrapper dla funkcji T => List[U], to funkcja, która wybuduje List[U] gdy dana instancja typu T. Zauważ, że tutaj T może być również List[U] lub U lub List[List[List[U]]] itd. Zwykle taka funkcja może być bezpośrednio określona jako typ parametru. Ale zamierzamy używać tego w implikacjach, więc nazwany wrapper unika ryzyka niejawnego konfliktu.

Następnie działa wstecz od recFlatten:

def recFlatten[T, U](xs: List[T])(implicit f: Flat[List[T], U]) = f fn xs 

Metoda ta odbędzie xs (a List[T]) i przekształcić go w U. Aby to osiągnąć, lokalizuje niejawny wystąpienie Flat[T,U] i wywołuje funkcję zamknięty, fn

Następnie prawdziwą magię:

implicit def recFlattenFn[T, U](
    implicit f: Flat[T, U] = Flat((xs: T) => List(xs)) 
) = Flat((xs: List[T]) => xs flatMap f.fn) 

ten spełnia parametr niejawny wymaganych recFlatten, ale również bierze udział niejawny paramater . Co najważniejsze:

• recFlattenFn może działać jako własnej niejawnym parametrem
• zwraca płaską [Lista [x] X], więc recFlattenFn zostaną niejawnie rozwiązany tylko jako Flat[T,U] jeśli T jest List
• niejawny f może awaryjne na wartość domyślną, jeśli nie powiedzie się niejawna rozdzielczości (tj T NIE jest List)

Perha ps ta jest najlepiej rozumiana w kontekście jednego z przykładów:

recFlatten(List(List(1, 2, 3), List(4, 5))) 

• Typ T jest wywnioskować jak List[List[Int]]
• niejawna odnośnika próby dla `Flat [Lista [List [Int]] U]
• to jest dopasowane przez zdefiniowane rekurencyjnie recFlattenFn

Ogólnie mówiąc:

recFlattenFn[List[List[Int]], U] (f = 
    recFlattenFn[List[Int], U] (f = 
    Flat[Int,U]((xs: T) => List(xs)) //default value 
) 
) 

Zauważ, że recFlattenFn będzie pasował tylko niejawnego poszukiwania Flat[List[X], X] oraz rodzaj params [Int,_] nie ten mecz, ponieważ Int nie jest List. To właśnie powoduje powrót do wartości domyślnej.

Rodzaj wnioskowanie działa również wstecz się tej struktury, rozwiązywaniu U param na każdym poziomie rekurencji:

recFlattenFn[List[List[Int]], Int] (f = 
    recFlattenFn[List[Int], Int] (f = 
    Flat[Int,Int]((xs: T) => List(xs)) //default value 
) 
) 

Który jest po prostu zagnieżdżanie Flat przypadkach, każdy z nich (oprócz najgłębsza) przeprowadzenie flatMap operacja, aby rozwinąć jeden poziom zagnieżdżonej struktury List. Najbardziej wewnętrzna Flat po prostu opakowuje wszystkie pojedyncze elementy z powrotem w pojedynczym List.

Q.E.D.

Answer 2

Może być dobrym rozwiązaniem jest próba sprawdzenia, w jaki sposób typy są wnioskowane. Aby uniknąć niejasności, niech nam zmieniać nazw rodzajowych:

case class Flat[T, U](fn : T => List[U]) 

implicit def recFlattenFn[T2, U2](implicit f : Flat[T2, U2] = 
            Flat((l : T2) => List(l))) = 
    Flat((l : List[T2]) => l.flatMap(f.fn)) 

def recFlatten[T3, U3](l : List[T3])(implicit f : Flat[List[T3], U3]) = f.fn(l) 

W pierwszym przypadku, res0, rodzaj T3 jest Int nie można wywnioskować, jeszcze typ U3, ale wiesz, że będziesz potrzebował Flat[List[Int, U3]] obiekt, który będą dostarczane bezwarunkowo. Jest tylko jeden "ukryty kandydat": wynik funkcji recFlattenFn, a jej typ to Flat[List[T2], List[U2]]. Zatem T2 = i (), które musimy jeszcze wywnioskować).

Teraz, jeśli chcemy korzystać z recFlatten, musimy podać mu parametr f. Oto podstęp. Można użyć domyślnej wartości domyślnej typu Int => List[Int] typu Flat[Int, U2]lub. Spójrzmy na dostępne implikacje. Jak wyjaśniono wcześniej, recFlattenFn może dostarczyć obiekt Flat[List[T2], U2] (dla nowego obiektu T2 i U2). Nie pasuje on do oczekiwanego podpisu f w tym momencie. Tak więc, żaden domniemany nie jest tutaj dobrym kandydatem i musimy użyć domyślnego argumentu. Ponieważ typem domyślnego argumentu jest Int => Lista [Int], U2 i U3 są Int i tam jedziemy.

Mam nadzieję, że ta długa proza ​​pomoże. Zostawiam cię z rozdzielczością res1 i res2.