Как работает рекурсивное выравнивание списков? - PullRequest
Новая
       26

Как работает рекурсивное выравнивание списков?

9 голосов
/ 27 августа 2011

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

Кевин:

Учитывая некоторую вложенную структуру: List[List[...List[T]]] что такоелучший (желательно типобезопасный) способ сплющить его до List[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)

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

Ответы [ 2 ]

11 голосов
/ 27 августа 2011

Ого, это старый!Я начну с небольшой очистки кода и приведения его в соответствие с текущими идиоматическими соглашениями: 

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

Затем, без лишних слов, разбиваем код.Во-первых, у нас есть класс Flat: 

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

Это не что иное, как именованная оболочка для функции T => List[U], которая будет создавать List[U] при задании экземпляра типа T.Обратите внимание, что T здесь также может быть List[U], или U, или List[List[List[U]]] и т. Д. Обычно такая функция может быть непосредственно указана в качестве типа параметра.Но мы собираемся использовать его косвенно, поэтому именованная оболочка позволяет избежать любого риска неявного конфликта.

Затем, работая в обратном направлении от recFlatten: 

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

ThisМетод возьмет xs (List[T]) и преобразует его в U.Чтобы достичь этого, он находит неявный экземпляр Flat[T,U] и вызывает вложенную функцию fn

Затем настоящая магия: 

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

Это удовлетворяет неявному параметру, требуемому дляrecFlatten, также требуется другой неявный параметр.Наиболее важно:

  • recFlattenFn может выступать в качестве своего собственного неявного параметра
  • , он возвращает Flat [Список [X], X], поэтому recFlattenFn будет разрешено только неявнокак Flat[T,U], если T - это List
  • , то неявное f может вернуться к значению по умолчанию, если неявное разрешение не удается (т. е. T НЕ является List)

Возможно, это лучше всего понять в контексте одного из примеров: 

recFlatten(List(List(1, 2, 3), List(4, 5)))
  • Тип T выводится как List[List[Int]]
  • неявныйпопытка поиска выполняется для `Flat [List [List [Int]], U]
  • , которому соответствует рекурсивно определенный recFlattenFn

В широком смысле: 

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

Обратите внимание, что recFlattenFn будет соответствовать неявному поиску только для Flat[List[X], X], а параметры типа [Int,_] не будут соответствовать этому совпадению, поскольку Int не является List.Это то, что вызывает откат к значению по умолчанию.

Вывод типа также работает в обратном направлении по этой структуре, разрешая параметр U на каждом уровне рекурсии: 

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

Это просто вложенность Flat экземпляров, каждый из которых (кроме самого внутреннего) выполняет операцию flatMap, чтобы развернуть один уровень вложенной структуры List.Внутренний Flat просто оборачивает все отдельные элементы в один List.

QED

2 голосов
/ 27 августа 2011

Может быть хорошим решением будет попытаться посмотреть, как типы выводятся.Чтобы избежать двусмысленности, давайте переименуем дженерики: 

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)

В первом случае res0, тип T3 равен Int, вы еще не можете вывести тип U3, новы знаете, что вам понадобится объект Flat[List[Int, U3]], который будет предоставлен неявно.Существует только один «неявный кандидат»: результат функции recFlattenFn и ее тип Flat[List[T2], List[U2]].Таким образом, T2 = Int и U2 = U3 (что нам еще нужно сделать вывод).

Теперь, если мы хотим использовать recFlatten, мы должны предоставить ему параметрf. Вот трюк .Вы можете использовать неявный тип Flat[Int, U2] или значение по умолчанию типа Int => List[Int].Давайте посмотрим на возможные последствия.Как объяснялось ранее, recFlattenFn может предоставить Flat[List[T2], U2] (для нового T2 и U2) объект.Это не соответствует ожидаемой подписи f на данный момент.Таким образом, неявные не являются хорошим кандидатом здесь, и мы должны использовать аргумент по умолчанию.Поскольку тип аргумента по умолчанию - Int => List [Int], U2 и U3 равны Int, и мы идем.

Надеюсь, что эта длинная проза поможет.Я оставляю вас с разрешением res1 и res2.

...