7
votes

Expliquez la mise en œuvre de la traverse [liste] dans Scalaz-sept

J'essaie de comprendre le traverseimpl code> implémentation dans 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)(_ :: _)
  }
}

scala applicative typeclass traversal scalaz

0 commentaires

3 Réponses :

6
votes

Ce n'est pas si facile à saisir. Je recommande de lire l'article relié au début de Mon article de blog sur le sujet .

J'ai également fait une présentation sur le sujet lors de la dernière réunion de programmation fonctionnelle à Sydney et vous pouvez trouver les diapositives ici .

Si je peux essayer d'expliquer en quelques mots, traverse va traverser chaque élément de la liste une par une, à la ré-construire éventuellement la ré-construisant la liste (_ :: _) mais accumule / exécutant une sorte de "effets" comme indiqué par le f applicatif . Si f est état Il garde une trace de certains états. Si f est l'application correspondant à un monoïde il s'agit d'une sorte de mesure pour chaque élément de la liste.

L'interaction principale de la liste et de l'application est avec l'application map2 où il reçoit un élément f [b] et joignez-le à l'autre f [Liste [B]] Éléments par définition de f en tant que applicatif et à l'utilisation de la liste list constructeur : : comme fonction spécifique à appliquer.

à partir de là, vous voyez que la mise en œuvre d'autres instances de traverse est uniquement environ appliquer ing les constructeurs de données de la structure de données que vous souhaitez traverser. Si vous souhaitez regarder la présentation PowerPoint liée, vous verrez des diapositives avec une traversée d'arbre binaire.



                                                                    
                                    
                                    
                                        3 commentaires
                                        
                                                                                            
                                                    En effet, votre article de votre blog et vos diapositives sont utiles!                                                
                                                
                                                                                            
                                                    Grandes diapositives! Pourriez-vous faire un pdf? J'ai eu des problèmes ennuyeux avec les polices et l'alignement.                                                
                                                
                                                                                            
                                                    J'ai téléchargé les diapositives PDF ici:  Slideshare.net/ettorreborre / ...


                        
                                            
                            
                                
                                    9
 votes
                                
                            
                            
                                
                                     Un applicateur vous permet d'appliquer une fonction dans un contexte à une valeur dans un contexte. Donc, par exemple, vous pouvez appliquer  certains ((i: int) => i + 1)  code> à  certains (3)  code> et obtenir  certains (4)  code>. Oublions ça pour l'instant. Je reviendrai à cela plus tard. 
 liste a deux représentations, soit  nil  code> ou  tête :: queue  code>. Vous pouvez être utilisé pour le replier à l'aide de  repliolft  code> mais il y a un autre moyen de se replier:  p>  xxx  pré> 
 liste  (1, 2)  code> Nous replions la liste en appliquant la fonction à partir du côté droit - même si nous déconstruisons vraiment la liste du côté gauche!  P>  xxx  pré> 
 Ceci peut être utilisé pour calculer la longueur d'une liste. Compte tenu de la liste  (1, 2)  code>:  p>  xxx  pré> 
 Ceci peut également être utilisé pour  créer  em> une autre liste:  p > 
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)
      )
  }
}

                                

                                                                    
                                    
                                    
                                        1 commentaires
                                        
                                                                                            
                                                    Superbe réponse qui ne nécessite aucune connaissance externe                                                
                                                
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    2
 votes
                                
                            
                            
                                
                                      Liste # pliard  code> souffle la pile pour les grandes listes. Essayez ceci dans un repli: 
List.range(0, 10000).foldRight(())((a, b) => ())

                                

                                                                    
                                    
                                    
                                        0 commentaires