Question Exemples d'histomorphismes dans Haskell


J'ai lu récemment [1] et [2], qui traitent de l'histomorphisme (et des dynamorphismes), qui sont des schémas de récursion pouvant exprimer, par ex. programmation dynamique. Malheureusement, les articles ne sont pas accessibles si vous ne connaissez pas la théorie des catégories, même s'il y a du code qui ressemble à Haskell.

Quelqu'un pourrait-il expliquer les histomorphismes avec un exemple qui utilise du vrai code Haskell?

  1. Histo- et Dynamorphismes revisités
  2. Schémas de récursivité pour la programmation dynamique

26
2017-07-22 10:08


origine


Réponses:


Commençons par définir un type de données que nous utiliserons comme exemple:

data Nat = S Nat | Z

Ce type de données code les nombres naturels dans le style Peano. Cela signifie que nous avons 0 et un moyen de produire le successeur de tout nombre naturel.

Nous pouvons construire de nouveaux nombres naturels à partir d'entiers facilement:

-- Allow us to construct Nats
mkNat :: Integer -> Nat
mkNat n | n < 0 = error "cannot construct negative natural number"
mkNat 0 = Z
mkNat n = S $ mkNat (n-1)

Maintenant, nous allons d'abord définir un catamorphisme pour ce type, car un histomorphisme lui est assez similaire et un catamorphisme est plus facile à comprendre.

Un catamorphisme permet de "plier" ou de "démolir" une structure. Il n'attend qu'une fonction qui sait comment plier la structure quand tous les termes récursifs ont déjà été pliés. Définissons un tel type, similaire à Nat, mais avec toutes les instances récursives remplacées par une valeur de type a:

data NatF a = SF a | ZF -- Aside: this is just Maybe

Maintenant, nous pouvons définir le type de notre catamorphisme pour Nat:

cata :: (NatF a -> a)
     -> (Nat -> a)

Étant donné une fonction qui sait comment plier la structure non récursive NatF a à un a, cata transforme cela en une fonction pour plier un tout Nat.

L'implémentation de cata est assez simple: pliez d'abord le sous-terme récursif (s'il y en a) et appliquez notre fonction:

cata f Z = f ZF -- No subterm to fold, base case
cata f (S subterm) = f $ SF $ cata f subterm -- Fold subterm first, recursive case

Nous pouvons utiliser ce catamorphisme pour convertir Nats retour à Integers, comme ceci:

natToInteger :: Nat -> Integer
natToInteger = cata phi where
  -- We only need to provide a function to fold
  -- a non-recursive Nat-like structure
  phi :: NatF Integer -> Integer
  phi ZF = 0
  phi (SF x) = x + 1

Donc avec cata, nous avons accès à la valeur du sous-terme immédiat. Mais imaginons que nous aimions aussi accéder aux valeurs des sous-termes transitifs, par exemple lors de la définition d’une fonction fibonacci. Ensuite, il faut non seulement accéder à la valeur précédente, mais aussi à la valeur précédente. C'est là que les histomorphismes entrent en jeu.

Un histomorphisme (histo ressemble beaucoup à "l'histoire") nous permet d'accéder tout valeurs précédentes, pas seulement les plus récentes. Cela signifie que nous obtenons maintenant une liste de valeurs, pas seulement une seule, de sorte que le type d’histomorphisme est le suivant:

-- We could use the type NatF (NonEmptyList a) here.
-- But because NatF is Maybe, NatF (NonEmptyList a) is equal to [a].
-- Using just [a] is a lot simpler
histo :: ([a] -> a)
      -> Nat -> a
histo f = head . go where
  -- go :: Nat -> [a]  -- This signature would need ScopedTVs
  go Z = [f []]
  go (S x) = let subvalues = go x in f subvalues : subvalues

Maintenant, nous pouvons définir fibN comme suit:

-- Example: calculate the n-th fibonacci number
fibN :: Nat -> Integer
fibN = histo $ \x -> case x of
 (x:y:_) -> x + y
 _       -> 1

Mis à part: même si cela peut paraître ainsi, histo n'est pas plus puissant que cata. Vous pouvez le voir vous-même en implémentant histo en termes de cata et inversement.


Ce que je n'ai pas montré dans l'exemple ci-dessus, c'est que cata et histo peut être implémenté très généralement si vous définissez votre type comme un point fixe d'un foncteur. Notre Nat le type est juste le point fixe du foncteur NatF.

Si vous définissez histo de manière générique, alors vous devez également trouver un type comme le NonEmptyList dans notre exemple, mais pour tout foncteur. Ce type est précisément Cofree f, où f est le foncteur dont vous avez pris le point fixe. Vous pouvez voir que cela fonctionne pour notre exemple: NonEmptyListest juste Cofree Maybe. Voici comment vous obtenez le type générique de histo:

histo :: Functor f 
      => (f (Cofree f a) -> a)
      -> Fix f  -- ^ This is the fixed point of f
      -> a

Vous pouvez penser à f (Cofree f a) comme une sorte de pile, où avec chaque "couche", vous pouvez voir une structure moins pliée. En haut de la pile, chaque sous-terme immédiat est plié. Ensuite, si vous allez plus loin dans une couche, le sous-terme immédiat n'est plus plié, mais les sous-sous-termes sont tous déjà pliés (ou évalués, ce qui pourrait être plus judicieux dans le cas des AST). Vous pouvez donc essentiellement voir "la séquence de réductions" qui a été appliquée (= l'historique).


19
2017-07-22 16:22



On peut y voir un continuum de généralisation de cata à histo à dyna. Dans la terminologie de recursion-schemes:

Foldable t => (Base t a -> a)                                  -> (t -> a) -- (1)
Foldable t => (Base t (Cofree (Base t) a) -> a)                -> (t -> a) -- (2)
Functor  f => (f      (Cofree f        a) -> a) ->  (t -> f t) -> (t -> a) -- (3)

où (1) est cata, (2) est histoet (3) est dyna. Un aperçu de haut niveau de cette généralisation est que histo améliore cata en conservant l’histoire de tous les "plis droits" partiels et dyna améliore histo en laissant fonctionner n'importe quel type t tant que nous pouvons faire un f-coalgebra pour cela, pas seulement le Foldable ceux (qui ont universel Base t-coalgebras as Foldable témoins que les types de données sont des coalgebras finales).

Nous pouvons presque lire leurs propriétés en regardant simplement ce qu'il faut pour remplir leurs types.

Par exemple, une utilisation classique de cata est de définir foldr

data instance Prim [a] x = Nil | Cons a x
type instance Base [a] = Prim [a]

instance Foldable [a] where
  project []     = Nil
  project (a:as) = Cons a as

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr cons nil = cata $ \case
  Nil      -> nil
  Cons a b -> cons a b

surtout, nous notons que foldr génère la valeur de pliage à droite partielle "suivante" en utilisant exclusivement la valeur de pliage à droite "précédente". C'est pourquoi il peut être implémenté en utilisant cata: il n'a besoin que du résultat du pli partiel le plus immédiatement précédent.

Comme histo généralise cata nous devrions pouvoir faire la même chose avec elle. Voici un histo-basé foldr

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr cons nil = histo $ \case
  Nil             -> nil
  Cons a (b :< _) -> cons a b

nous pouvons voir que nous ne sommes plus immédiatement avoir le résultat du pli immédiatement précédent, mais doivent plutôt atteindre le premier Cofree pour le trouver. Mais Cofree est un flux et contient potentiellement une infinité de "valeurs de pli précédentes" et nous pouvons creuser aussi profondément que nous le souhaitons. C'est ce qui donne histo son pouvoir "historique". Par exemple, nous pouvons écrire un document assez direct tail en utilisant histo ce qui est plus difficile à faire avec cata seul:

tail :: [a] -> Maybe [a]
tail = histo $ \case
  Nil             -> Nothing -- empty list
  Cons _ (b :< x) -> case x of
    Nil       -> Just [] -- length 1 list
    Cons a _ -> fmap (a:) b

Le style est un peu indirect, mais essentiellement parce que nous pouvons revenir sur le passé deux étapes nous pouvons répondre aux listes de longueur-1 différemment des listes de longueur-0 ou de longueurn listes.

Prendre la dernière étape pour généraliser histo à dyna nous remplaçons simplement la projection naturelle par tout Coalgebra. Nous pourrions donc mettre en œuvre histo en terme de dyna plutôt facilement

histo phi = dyna phi project -- project is from the Foldable class

Alors maintenant, nous pouvons appliquer histo se plie à n'importe quel type qui peut même être partiellement vu comme une liste (enfin, tant que nous conservons l'exemple courant et Prim [a] comme le Functor, f).

(Théoriquement, il y a une restriction que cette coalgebra éventuellement s'arrête, par exemple. nous ne pouvons pas traiter des flux infinis, mais cela a plus à voir avec la théorie et l'optimisation que l'utilisation. En utilisation, une telle chose doit simplement être paresseuse et assez petite pour se terminer.)

(Cela reflète l’idée de représenter les algèbres initiales par leur capacité à project :: t -> Base t t. Si c'était vraiment un type inductif total, vous ne pouviez projeter que plusieurs fois avant d'atteindre la fin.

Pour reproduire l'instance des numéros catalans à partir du papier lié, nous pouvons créer des listes non vides.

data NEL  a   = Some  a | More  a (NEL a)
data NELf a x = Somef a | Moref a x deriving Functor

et créer la coalgebra sur les nombres naturels appelés natural qui, convenablement déplié, produit un compte à rebours NEL

natural :: Int -> NELf Int Int
natural 0 = Somef 0
natural n = Moref n (n-1)

alors nous appliquons un histo-style se plier à la NELf-vue d'un nombre naturel pour produire le nNuméro Catalan.

-- here's a quick implementation of `dyna` using `recursion-schemes`

zcata
  :: (Comonad w, Functor f) =>
     (a -> f a) -> (f (w (w c)) -> w b) -> (b -> c) -> a -> c
zcata z k g = g . extract . c where
  c = k . fmap (duplicate . fmap g . c) . z

dyna :: Functor f => (f (Cofree f c) -> c) -> (a -> f a) -> a -> c
dyna phi z = zcata z distHisto phi

takeC :: Int -> Cofree (NELf a) a -> [a]
takeC 0 _                 = []
takeC n (a :< Somef v)    = [a]
takeC n (a :< Moref v as) = a : takeC (n-1) as

catalan :: Int -> Int
catalan = dyna phi natural where
  phi :: NELf Int (Cofree (NELf Int) Int) -> Int
  phi (Somef 0) = 1
  phi (Moref n table) = sum (zipWith (*) xs (reverse xs))
    where xs = takeC n table

12
2017-07-22 18:42