¿Cómo funciona este apilamiento recursivo de Lista?

Question

Hace un tiempo this was asked and answered en la lista de correo Scala:

Kevin:

Dada una estructura anidada: List[List[...List[T]]] ¿cuál es la mejor manera (de tipo seguro de preferencia) para aplanarlo a un List[T]

Jesper:

Una combinación de impl icits y argumentos por defecto funciona:

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) 

Ejemplos:

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) 

He estado buscando en este código por un tiempo. No puedo entender cómo funciona. Parece que hay alguna recursión involucrada ... ¿Alguien puede arrojar algo de luz? ¿Hay otros ejemplos de este patrón y tiene un nombre?

Answer 1

¡Oh, guau, esta es una vieja! Voy a empezar por la limpieza del código un poco y tirando de él en línea con las convenciones idiomáticas actuales:

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 

Entonces, sin más preámbulos, descomponen el código.En primer lugar, tenemos nuestra clase Flat:

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

Esto no es nada más que un envoltorio lleva el nombre de la función T => List[U], una función que va a construir una List[U] cuando se les da una instancia de tipo T. Tenga en cuenta que T aquí también podría ser un List[U], o un U, o un List[List[List[U]]], etc. Normalmente, dicha función se podría especificar directamente como el tipo de un parámetro. Pero vamos a usar este en implicits, por lo que el contenedor con nombre evita cualquier riesgo de un conflicto implícito.

Entonces, trabajando hacia atrás desde recFlatten:

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

Este método se llevará a xs (un List[T]) y convertirlo en un U. Para lograr esto, se localiza una instancia implícita de Flat[T,U] e invoca la función cerrada, fn

Entonces, la verdadera magia:

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

Esto satisface el parámetro implícito requerido por recFlatten, sino que también da un parámetro de implícita . Lo más crucial:

• recFlattenFn puede actuar como su propio parámetro implícito
• devuelve un plano [Lista [X], X], por lo recFlattenFn sólo se pueden resolver de forma implícita como Flat[T,U] si T es una List
• lo implícito f se repliegue a un valor por defecto si falla la resolución implícita (es decir, no es un TList)

Perha ps esta se entiende mejor en el contexto de uno de los ejemplos:

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

• El tipo T se infiere como List[List[Int]]
• de búsqueda implícita se intenta para un `Flat [Lista [Lista [Int]], U]
• este se corresponde con una forma recursiva define recFlattenFn

términos generales:

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

Tenga en cuenta que recFlattenFn sólo igualará una búsqueda implícita para una Flat[List[X], X] y el tipo params [Int,_] fallan este partido porque Int no es un List. Esto es lo que desencadena el retorno al valor predeterminado.

La inferencia de tipos también trabaja hacia atrás hasta que la estructura, la resolución del parámetro U en cada nivel de recursividad:

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

que es sólo un anidamiento de Flat casos, cada uno de ellos (excepto el más interno) realizar una flatMap operación para desenrollar un nivel de la estructura anidada List. El Flat más interno simplemente envuelve todos los elementos individuales en una sola copia List.

Q.E.D.

Answer 2

Puede ser una buena solución tratar de ver cómo se integran los tipos. Para evitar la ambigüedad, vamos a cambiar el nombre del genéricos:

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) 

En el primer caso, res0, el tipo de T3 es Int no se puede inferir sin embargo, el tipo de U3, pero ya se sabe que necesitará un objeto Flat[List[Int, U3]] que se proporcionará implícitamente. Solo hay un "candidato implícito": el resultado de la función recFlattenFn y su tipo es Flat[List[T2], List[U2]]. Por lo tanto, T2 = Int y U2 = U3 (que aún debemos inferir).

Ahora, si queremos poder usar recFlatten debemos proporcionarle un parámetro f. Aquí está el truco. Puede utilizar un implícito de tipo Flat[Int, U2]o el valor predeterminado de tipo Int => List[Int]. Veamos las implicaciones disponibles. Como se explicó antes, recFlattenFn puede proporcionar un objeto Flat[List[T2], U2] (para un nuevo T2 y U2). No se ajusta a la firma esperada de f en este punto. Por lo tanto, ningún candidato implícito es un buen candidato aquí y debemos usar el argumento predeterminado. Como el tipo del argumento predeterminado es Int => Lista [Int], U2 y U3 son Int y ahí vamos.

Espero que esta larga prosa ayude. Los dejo con la resolución de res1 y res2.