Как работает это рекурсивное сглаживание списков?

Некоторое время назад в списке рассылки Scala спросили и ответили :

Кевин:

Учитывая некую вложенную структуру: Список [Список [... Список [T]]] какой лучший (предпочтительно безопасный по типу) способ свести его к списку [T]

Jesper:

Комбинация имплицитов и аргументов по умолчанию работает:

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) 

Примеры:

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) 

Я был некоторое время смотрю на этот код. Я не могу понять, как это работает. Кажется, здесь есть какая-то рекурсия ... Кто-нибудь может пролить свет? Есть ли другие примеры этого шаблона и есть ли у него имя?

10
задан huynhjl 27 August 2011 в 07:28
поделиться