Spiegare Traverse [Elenco] implementazione in scalaz-sette

Question

Sto cercando di capire il traverseImpl implementazione in scalaz-seven:

def traverseImpl[F[_], A, B](l: List[A])(f: A => F[B])(implicit F: Applicative[F]) = { 
    DList.fromList(l).foldr(F.point(List[B]())) { 
    (a, fbs) => F.map2(f(a), fbs)(_ :: _) 
    } 
} 

qualcuno può spiegare come l'List interagisce con il Applicative? In definitiva, mi piacerebbe essere in grado di implementare altre istanze per Traverse.

Answer 1

Un applicativo consente di applicare una funzione in un contesto a un valore in un contesto. Ad esempio, è possibile applicare some((i: Int) => i + 1) a some(3) e ottenere some(4). Dimentichiamo quello per ora. Tornerò su dopo.

L'elenco ha due rappresentazioni, è Nil o head :: tail. Si può essere utilizzato per ripiegare su di esso utilizzando foldLeft Ma c'è un altro modo per piegare su di esso:

def foldr[A, B](l: List[A], acc0: B, f: (A, B) => B): B = l match { 
    case Nil => acc0 
    case x :: xs => f(x, foldr(xs, acc0, f)) 
} 

Dato List(1, 2) pieghiamo sulla lista applicando la funzione a partire dal lato destro - anche se abbiamo davvero decostruire la lista dalla parte di sinistra!

f(1, f(2, Nil)) 

Questo può essere utilizzato per calcolare la lunghezza di un elenco. Dato List(1, 2):

foldr(List(1, 2), 0, (i: Int, acc: Int) => 1 + acc) 
// returns 2 

Questo può essere utilizzato anche per creare un altro elenco:

foldr[Int, List[Int]](List(1, 2), List[Int](), _ :: _) 
//List[Int] = List(1, 2) 

Quindi dato un elenco vuoto e la funzione :: siamo stati in grado di creare un altro elenco.Cosa succede se i nostri elementi si trovano in uno contesto? Se il nostro contesto è un applicativo, allora possiamo ancora applicare i nostri elementi e :: in quel contesto. Proseguendo con List(1, 2) e Option come nostro applicativo. Iniziamo con some(List[Int]())) per applicare la funzione :: nel contesto Option. Questo è ciò che fa F.map2. Prende due valori nel loro contesto Option, inserisce la funzione fornita di due argomenti nel contesto Option e li applica insieme.

Quindi al di fuori del contesto abbiamo (2, Nil) => 2 :: Nil

Nel contesto abbiamo: (Some(2), Some(Nil)) => Some(2 :: Nil)

Tornando alla domanda iniziale:

// do a foldr 
DList.fromList(l).foldr(F.point(List[B]())) { 
    // starting with an empty list in its applicative context F.point(List[B]()) 
    (a, fbs) => F.map2(f(a), fbs)(_ :: _) 
    // Apply the `::` function to the two values in the context 
} 

io non sono sicuro perché è utilizzata la differenza DList. Quello che vedo è che usa trampolini così speranzosi che faccia funzionare questa implementazione senza far esplodere lo stack, ma non l'ho provato quindi non lo so.

La parte interessante sull'implementazione della piega destra in questo modo è che penso che fornisca un approccio per implementare la traversa per i tipi di dati algebrici utilizzando catamorphisms.

Per esempio dato:

trait Tree[+A] 
object Leaf extends Tree[Nothing] 
case class Node[A](a: A, left: Tree[A], right: Tree[A]) extends Tree[A] 

piegatura sarebbe definito come questo (che è in realtà seguendo lo stesso approccio per List):

def fold[A, B](tree: Tree[A], valueForLeaf: B, functionForNode: (A, B, B) => B): B = { 
    tree match { 
    case Leaf => valueForLeaf 
    case Node(a, left, right) => functionForNode(a, 
     fold(left, valueForLeaf, functionForNode), 
     fold(right, valueForLeaf, functionForNode) 
    ) 
    } 
} 

ed attraversare userebbero che fold con F.point(Leaf) e applicalo a Node.apply. Sebbene non ci sia il numero F.map3, potrebbe essere un po 'macchinoso.

Answer 2

Questo non è qualcosa di così facile da capire. Raccomando di leggere l'articolo collegato all'inizio di my blog post on the subject.

Ho anche fatto una presentazione sull'argomento durante l'ultimo incontro di programmazione funzionale a Sydney e potete trovare le diapositive here.

Se posso cercare di spiegare in poche parole, traverse sta per attraversare ogni elemento della lista uno per uno, poi ri-costruire la lista (_ :: _) ma accumulando/esecuzione di una sorta di "effetti" come proposta dal F Applicative. Se F è State, tiene traccia di alcuni stati. Se F è l'applicativo corrispondente a Monoid, aggrega un tipo di misura per ciascun elemento dell'elenco.

L'interazione principale della lista e l'applicativo è con l'applicazione map2 dove riceve un elemento F[B] e fissano ai altri F[List[B]] elementi di definizione di F come Applicative e l'uso del List costruzione :: come specifica funzione da applicare.

Da lì si vede che l'implementazione di altre istanze di Traverse è solo di circa apply i costruttori di dati della struttura dati che si desidera attraversare. Se dai un'occhiata alla presentazione in powerpoint collegata, vedrai alcune diapositive con un attraversamento ad albero binario.

Answer 3

List#foldRight blows lo stack per elenchi di grandi dimensioni. Prova questo in un REPL:

List.range(0, 10000).foldRight(())((a, b) =>()) 

genere, è possibile invertire la lista, utilizzare foldLeft, poi invertire il risultato per evitare questo problema. Ma con traverse dobbiamo davvero elaborare gli elementi nell'ordine corretto, per assicurarci che l'effetto sia trattato correttamente. DList è un modo conveniente per farlo, in virtù del trampolino.

Alla fine, questi test devono superare:

https://github.com/scalaz/scalaz/blob/scalaz-seven/tests/src/test/scala/scalaz/TraverseTest.scala#L13 https://github.com/scalaz/scalaz/blob/scalaz-seven/tests/src/test/scala/scalaz/std/ListTest .scala # L11 https://github.com/scalaz/scalaz/blob/scalaz-seven/core/src/main/scala/scalaz/Traverse.scala#L76