Qu'est-ce que Banana Split and Fusion dans la programmation fonctionnelle?

Ces termes ont été mentionnés dans mon cours universitaire. La recherche rapide sur Google m'a indiqué des articles universitaires, mais je cherche une explication simple.

Même si 2 réponses ont déjà été fournies, je ne pense pas que le "split banane" ait été expliqué ici.

Il est en effet défini dans "Programmation fonctionnelle avec bananes, lentilles, enveloppes et barbelés, Erik Meijer Maarten Fokkinga, Ross Paterson, 1991"; cet article est difficile à lire (pour moi) en raison de son utilisation intensive de Squiggol. Cependant, "Un tutoriel sur l'universalité et l'expressivité du pli, Graham Hutton, 1999" contient une définition plus facile à analyser:

Comme premier exemple simple de l'utilisation de fold pour générer des tuples, considérons la fonction sumlength qui calcule la somme et la longueur d'une liste de nombres:

sumlength :: [Int] → (Int,Int)
sumlength xs = (sum xs, length xs)

En combinant directement les définitions des fonctions somme et longueur en utilisant le pli donné précédemment, la fonction sommelongueur peut être redéfinie comme une seule application de pli qui génère une paire de nombres à partir d'une liste de nombres:

sumlength = fold (λn (x, y) → (n + x, 1 + y)) (0, 0)

Cette définition est plus efficace que la définition d'origine, car elle ne fait qu'une seule traversée sur la liste d'arguments, plutôt que deux traversées distinctes. En généralisant à partir de cet exemple, n'importe quelle paire d'applications de fold à la même liste peut toujours être combinée pour donner une seule application de fold qui génère une paire, en faisant appel à la propriété dite de `` banana split '' de fold (Meijer, 1992) . Le nom étrange de cette propriété provient du fait que l' opérateur de pliage est parfois écrit à l'aide de crochets (| |) qui ressemblent à des bananes, et l'opérateur d'appariement est parfois appelé split. Par conséquent, leur combinaison peut être qualifiée de banane fendue!

Il s'agit donc en fait d'une référence à un article de Meijer et de quelques autres intitulé " Programmation fonctionnelle avec des bananes, des lentilles, des enveloppes et des barbelés ", l'idée de base est que nous pouvons prendre n'importe quel type de données récursives, comme par exemple

 data List = Cons Int List | Nil

et nous pouvons factoriser la récursivité dans une variable de type

 data ListF a = Cons Int a | Nil

la raison pour laquelle j'ai ajouté cela Fparce que c'est maintenant un foncteur! Cela nous permet également d'imiter des listes, mais avec une torsion: pour construire des listes, nous devons imbriquer le type de liste

type ThreeList = ListF (ListF (ListF Void)))

Pour récupérer notre liste d'origine, nous devons continuer à l'imbriquer indéfiniment . Cela nous donnera un type ListFFoù

  ListF ListFF == ListFF

Pour ce faire, définissez un "type de point fixe"

  data Fix f = Fix {unfix :: f (Fix f)}
  type ListFF = Fix ListF

En tant qu'exercice, vous devriez vérifier que cela satisfait notre équation ci-dessus. Maintenant, nous pouvons enfin définir ce que sont les bananes (catamorphismes)!

  type ListAlg a = ListF a -> a

ListAlgs sont le type "d'algèbres de liste", et nous pouvons définir une fonction particulière

  cata :: ListAlg a -> ListFF -> a
  cata f = f . fmap (cata f) . unfix

En outre

  cata :: ListAlg a -> ListFF -> a
  cata :: (Either () (Int, a) -> a) -> ListFF -> a
  cata :: (() -> a) -> ((Int, a) -> a) -> ListFF -> a
  cata :: a -> (Int -> a -> a) -> ListFF -> a
  cata :: (Int -> a -> a) -> a -> [Int] -> a

Semble familier? cataest exactement le même que les plis droits!

Ce qui est vraiment intéressant, c'est que nous pouvons faire cela plus que de simples listes, tout type qui est défini avec ce "point fixe d'un foncteur" a un cataet pour les accomder, il suffit de relâcher la signature de type

  cata :: (f a -> a) -> Fix f -> a

Ceci est en fait inspiré d'un morceau de théorie des catégories sur lequel j'ai écrit , mais c'est la viande du côté Haskell.

Bien que jozefg ait fourni une réponse, je ne sais pas s'il a répondu à la question. La "loi de fusion" est expliquée dans l'article suivant:

Un tutoriel sur l'universalité et l'expressivité du pli, GRAHAM HUTTON, 1999

Fondamentalement, il dit que dans certaines conditions, vous pouvez combiner ("fusionner") la composition d'une fonction et la plier en un seul pli, donc en gros

h · pli gw = pli fv

Les conditions de cette égalité sont

hw = v
h (gxy) = fx (hy)

La "loi banane split" ou "banana split law" est tirée de l'article

Programmation fonctionnelle avec des bananes, des lentilles, des enveloppes et des barbelés, Erik Meijer Maarten Fokkinga, Ross Paterson, 1991

Malheureusement, l'article est très difficile à déchiffrer car il utilise le formalisme Bird – Meertens, je ne pouvais donc pas en faire la tête ou la queue. Pour autant que je comprenne la "loi du partage des bananes", cela dit que si vous avez 2 plis opérant sur le même argument, ils peuvent être fusionnés en un seul pli.