Bu özyinelemeli liste düzleştirme nasıl çalışır?

Question

bir geri this was asked and answered Scala posta listesinde ise:

Kevin:

Verilen bazı içiçe yapı: Bir List[T]

bunu düzleştirmek için en iyi (tercihen tip-güvenli) yolu ne List[List[...List[T]]]

Jesper: impl arasında

bir kombinasyon icits ve varsayılan argümanlar çalışır:

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) 

Örnekler: Bir süre bu kodu bakarak edilmiştir

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) 

. Nasıl çalıştığını anlayamıyorum. Bazı özyinelemelerin olduğu görünüyor ... Kimse biraz ışık tutabilir mi? Bu örüntüün başka örnekleri var mı ve bir ismi var mı?

Answer 1

Vay be, bu eski bir! Ben kodu biraz temizlemeye ve güncel deyimsel sözleşmeleri ile uyumlu içine çekerek başlayacağız:

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 

Sonra fazla uzatmadan, kod yıkmak.

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

Bu işlevin T => List[U] için adlandırılmış sarıcı daha hiçbir şey, tip T bir örneğini verildiğinde bir List[U] inşa edecek bir işlevdir: Birincisi, bizim Flat sınıf var. Burada T'un da bir List[U] veya U veya List[List[List[U]]] vb. Olabileceğini unutmayın. Normal olarak, böyle bir işlev doğrudan bir parametre tipi olarak belirtilebilir. Ancak, bunu örtük olarak kullanacağız, bu nedenle adlandırılmış sarmalayıcı örtük bir çakışma riskini önler. recFlatten geriye çalışan sonra

:

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

Bu yöntem sunar xs (a List[T]) ve U dönüştürecektir.

Bu recFlatten gerektirdiği örtük parametreyi tatmin

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

, o da başka bir örtülü parametrenin yeni sürer: Bunu başarmak için, o sonra gerçek büyü fn

Flat[T,U] örtülü bir örneğini bulur ve kapalı işlevini çağırır . En önemlisi: bir Flat[T,U] eğer T bir List olduğu gibi

• recFlattenFn kendi örtük parametre olarak hareket edebilir bir Düz döndürür
• [List [X], X], bu yüzden recFlattenFn yalnızca kesin olarak çözülecektir örtülü çözünürlük başarısız olursa
• örtük f

Perha (yani T bir List dEĞİLDİR) varsayılan değer çare olabilir PS bu en iyi örneklerinden biri bağlamında anlaşılmalıdır:

örtülü arama bir 'Düz [Listesi için denenir tip TList[List[Int]] olarak anlaşılmaktadır

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

• [Liste [Uluslararası]],
  : Bu tarafından eşleştirilir
• U] yinelemeli konuşma Genel olarak

recFlattenFn tanımlandığı Int bir List olmadığından [Int,_] bu maçı başarısız parametreler recFlattenFn sadece Flat[List[X], X] için örtük bir arama ve türüyle uyumlu olacak

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

Not. Bu, varsayılan değere geri dönüşü tetikleyen şeydir.

Tip çıkarsama da özyineleme her seviyede U param çözme, o yapının kadar geriye çalışır:

Flat durumlarda sadece bir yuvalama olup

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

, bir flatMap performans (en içteki hariç) her biri iç içe geçmiş List yapısının bir düzeyini açmak için işlem. En içteki Flat tüm tek tek elemanları tek bir List içerisinde yedekler.

Q.E.D.

Answer 2

İyi bir çözüm, türlerin nasıl çıkarıldığına bakmaya çalışmaktır. Belirsizliği önlemek için bize Generics'i adlandırmak alalım: İlk durumda, res0 yılında

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) 

, T3 türü, U3 henüz türünü tahmin edemediği Int, ama bir Flat[List[Int, U3]] nesne gerektiğini biliyoruz örtülü olarak sağlanacaktır. Yalnızca bir "örtülü aday" var: recFlattenFn işlevinin sonucu ve türü Flat[List[T2], List[U2]]. Böylece T2 = Int ve U2 = U3 (yine de çıkarmamız gereken).

Şimdi, recFlatten'u kullanamayacak olursak, f parametresini sağlamalıyız. İşte hileler. Ya Flat[Int, U2]veya türündeki bir örtülü değeri Int => List[Int] türünün varsayılan değerini kullanabilirsiniz. Mevcut implikasyonlara bakalım. recFlattenFn'dan önce açıklandığı gibi Flat[List[T2], U2] (yeni bir T2 ve U2) nesnesi sağlayabilir. Bu noktada f'un beklenen imzasına uymuyor. Dolayısıyla, burada hiçbir dolaylı iyi bir aday değildir ve varsayılan argümanı kullanmalıyız. Varsayılan argümanın türü Int => List [Int], U2 ve U3 ise Int ve işte başlıyoruz.

Bu uzun düzyazıların yardımcı olacağını umuyorum. Seni res1 ve res2 çözünürlüğüyle bırakıyorum.