Comme je l'ai indiqué dans un commentaire, la récursivité est la primitive de bouclage dans Haskell. Cependant, Haskell nous donne beaucoup de pouvoir pour construire des abstractions plus conviviales au lieu d'utiliser la récursivité directement. Comme l'a mentionné @Lazersmoke, Comonad est une bonne abstraction lorsque vous mettez à jour chaque valeur individuelle d'une collection en fonction d'autres valeurs de la collection, telles que les voisins de la valeur.
Il y a quelques exemples de la classe Comonad sur le web, mais elle est malheureusement éclipsée par Monad. Alors, voici ma tentative pour égaliser un peu le score.
Cela va être un long post, alors laissez-moi commencer par les résultats. Cela vient de GHCi:
λ display example
[[A,A,A],[B,B,A],[A,A,B]]
λ display (transition example)
[[B,B,A],[A,B,B],[B,B,A]]
Ok, maintenant passons aux choses sérieuses. Tout d'abord quelques choses administratives:
module Main where
import Control.Comonad -- from the comonad package
Je vais essayer d'expliquer chaque pièce avec soin, mais il peut prendre un certain temps avant que la plus grande image devient apparente. Tout d'abord, nous allons créer une structure de données intéressante souvent appelée fermeture à glissière et implémenter une instance de Functor pour cela.
data U x = U [x] x [x] deriving Functor
instance Functor U where
fmap f (U as x bs) = U (fmap f as) (f x) (fmap f bs)
Cette structure de données ne semble pas si spéciale. C'est ainsi que nous utilisons U qui le rend cool. Parce que Haskell est paresseux, nous pouvons utiliser des listes infinies avec le constructeur U. Par exemple, i1 = U [-1,-2..] 0 [1,2..] représente tous les entiers. Ce n'est pas tout, cependant. Il y a un autre élément d'information: un point central à 0. Nous aurions pu également représenter tous les entiers sous la forme i2' = U [0,-1..] 1 [2,3..]. Ces valeurs sont presque les mêmes; ils sont simplement décalés d'un. Nous pouvons, en effet, créer des fonctions qui vont transformer l'une dans l'autre.
rightU (U a b (c:cs)) = U (b:a) c cs
leftU (U (a:as) b c) = U as a (b:c)
Comme vous pouvez le voir, nous pouvons slide un U à gauche ou à droite, juste par des éléments réorganisés. Faisons une instance Show pour U, puis vérifions que rightU et leftU fonctionnent. Nous ne pouvons évidemment pas imprimer des listes infinies, donc nous allons prendre 3 éléments de chaque côté.
instance Show x => Show (U x) where
show (U as x bs) = (show . reverse . take 3) as ++ (show x) ++ (show . take 3) bs
λ i1
[-3,-2,-1]0[1,2,3]
λ leftU i2
[-3,-2,-1]0[1,2,3]
λ i2
[-2,-1,0]1[2,3,4]
λ rightU i1
[-2,-1,0]1[2,3,4]
Passons en revue notre but ultime. Nous voulons avoir une structure de données où nous pouvons mettre à jour chaque valeur en fonction de tous ses voisins. Voyons comment faire cela avec notre structure de données U. Supposons que nous voulions remplacer chaque nombre par la somme de ses voisins. Tout d'abord, nous allons écrire une fonction qui calcule les voisins de la position actuelle d'un U:
sumOfNeighbors :: U Int -> Int
sumOfNeighbors (U (a:_) _ (b:_)) = a + b
Et juste pour vérifier que cela fonctionne:
λ sumOfNeighbors i1
0
λ sumOfNeighbors i2
2
Malheureusement, cela ne nous donne un résultat unique. Nous voulons appliquer cette fonction à toutes les positions possibles. Eh bien U a une instance Functor, donc nous pouvons fmap une fonction sur elle. Cela fonctionnerait bien si notre fonction avait un type comme Int -> Int, mais c'est en fait U Int -> Int. Mais que se passerait-il si nous pouvions transformer notre U Int en un U (U Int)? Alors fmap sumOfNeighbors ferait exactement ce que nous voulons!
Préparez-vous à la structuration de données au niveau de la création. Nous allons prendre notre U Int et créer un U (U Int) qui ressemblera à ceci:
-- not real Haskell. just for illustration
U [leftU u, (leftU . leftU) u, (leftU . leftU . leftU) u..] u [rightU u, (rightU . rightU) u, (rightU . rightU . rightU) u..]
Ce centre de ce nouveau U (U a) est le U a d'origine. Lorsque nous glissons à gauche, nous obtenons l'original U a glissé à gauche, et de même glisser à droite. En d'autres termes, la nouvelle U (U a) contient toutes les diapositives gauche et droite de la U a originale est ici comment nous le faisons:
duplicate :: U a -> U (U a)
duplicate u = U lefts u rights
where lefts = tail $ iterate leftU u
rights = tail $ iterate rightU u
Nous pouvons utiliser duplicate pour écrire la fonction que nous voulons:
extend :: (U a -> b) -> U a -> U b
extend f = fmap f . duplicate
Essayons.
λ extend sumOfNeighbors i1
[-6,-4,-2]0[2,4,6]
Cela ressemble à ça. Ces noms de fonctions, duplicate et extend n'ont pas été choisis arbitrairement (par moi, au moins). Ces fonctions font partie de la classe de type Comonad. Nous l'avons implémenté pour notre type de données U.
class Functor w => Comonad w where
extract :: w a -> a
duplicate :: w a -> w (w a)
extend :: (w a -> b) -> w a -> w b
La seule chose qui manque est extract qui est trivial pour U:
extract (U _ x _) = x
Il est probablement ne voit pas comment cette classe est encore utile. Passons à autre chose et voyons comment gérer le cas bidimensionnel. Nous pouvons faire 2 dimensions avec une fermeture à glissière de fermetures à glissière. C'est-à-dire, U (U a) où se déplacer à gauche et à droite décale les fermetures à glissière intérieures, et se déplacer vers le haut et vers le bas décale la fermeture à glissière extérieure.
newtype V a = V { getV :: U (U a) }
instance Functor V where
fmap f = V . (fmap . fmap) f . getV
-- shift the 'outer' zipper
up :: V a -> V a
up = V . leftU . getV
down :: V a -> V a
down = V . rightU . getV
-- shift the 'inner' zippers
left :: V a -> V a
left = V . fmap leftU .getV
right :: V a -> V a
right = V . fmap rightU . getV
Voici ce que Comonad ressemble à V:
instance Comonad V where
extract = extract . extract . getV
duplicate = fmap V . V . dup . dup . getV
where dup u = U (lefts u) r (right u)
lefts u = tail $ iterate (fmap leftU) u
rights u = tail $ iterate (fmap rightU) u
La fonction extract est assez simple; il creuse juste à travers deux couches de fermetures à glissière pour saisir la valeur actuelle. D'autre part, duplicate est une sorte de monstre. En ignorant le nouveau type V, son type serait duplicate :: U (U a) -> U (U (U (U a))). Le but de la fonction auxiliaire dup est d'ajouter une couche U. Il est invoqué deux fois. Ensuite, nous enveloppons cela dans V pour obtenir un V (U (U a)). Puis fmap V enveloppe le U (U a) interne pour faire le résultat V (V a). Oh, au fait, si vous vous demandez où se trouve extend, nous n'avons pas besoin de l'écrire. La définition donnée ci-dessus est sa valeur par défaut.
C'était beaucoup de travail, mais maintenant nous serons en mesure de résoudre facilement le problème original! Regarde ça. Je vais faire une structure de données qui comprend vos A et B valeurs, et aussi une valeur que nous ne nous soucions pas, C:
data Token = A | B | C deriving (Eq,Show)
Et voici quelques trucs pour rendre la construction et l'affichage d'un V plus facile .
-- a list of U's containing nothing but x's
filled x = repeat $ U (repeat x) x (repeat x)
type Triple a = (a,a,a)
-- create a U with the middle values a, b, and c, and all the other values the defaulted to d
toU :: a -> Triple a -> U a
toU d (a,b,c) = U (a : repeat d) b (c : repeat d)
-- create a V centered on the 9 given values and default all other values to d
toV :: a -> Triple (Triple a) -> V a
toV d (as, bs, cs) = V (U x y z)
where x = (toU d as) : filled d
y = toU d bs
z = (toU d cs) : filled d
display :: Show a => V a -> [[a]]
display v = fmap g [ [up . left, up, up . right]
, [left, id, right]
, [down . left, down , down . right] ]
where g = fmap (extract . ($ v))
Voici ce que l'exemple ressemble à:
example = toV C ((A,A,A)
,(B,B,A)
,(A,A,B))
Et la règle est mise en œuvre par:
-- move into each neighboring position and get the value in that position
neighbors :: V a -> [a]
neighbors v = fmap (extract . ($ v)) positions
where positions = [ up . left
, up
, up . right
, left
, right
, down . left
, down
, down . right ]
numberOfBs :: V Token -> Int
numberOfBs = length . filter (==B) . neighbors
rule :: V Token -> Token
rule v = case extract v of
C -> C -- C's remain C's forever
_ -> if numberOfBs v >= 2 then B else A
Enfin, nous pouvons appliquer rule à chaque valeur à l'aide extend:
transition = extend rule
λ display (transition example)
[[B,B,A],[A,B,B],[B,B,A]]
Cette règle est ennuyeuse. Tout devient rapidement B's.
λ take 10 $ fmap display (iterate transition example)
[[[A,A,A],[B,B,A],[A,A,B]],[[B,B,A],[A,B,B],[B,B,A]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]]]
La création d'une règle différente est facile.
rule2 :: V Token -> Token
rule2 v = case extract v of
C -> C
A -> if numberOfBs v >= 2 then B else A
B -> if numberOfBs v >= 4 then A else B
λ take 10 $ fmap display (iterate (extend rule2) example)
[[[A,A,A],[B,B,A],[A,A,B]],[[B,B,A],[B,B,B],[B,B,B]],[[B,A,B],[A,A,A],[B,A,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,A,B],[A,A,A],[B,A,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,A,B],[A,A,A],[B,A,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,A,B],[A,A,A],[B,A,B]],[[B,B,B],[B,B,B],[B,B,B]]]
Cool, n'est-ce pas? Une dernière chose que je veux mentionner. Avez-vous remarqué que nous n'avons pas écrit de cas particuliers pour gérer les bords? Puisque la structure de données est infinie, nous avons juste rempli les choses hors de la gamme dont nous ne nous soucions pas avec la valeur C et l'avons ignoré en considérant les voisins.
La réponse simple est d'utiliser la récursivité. Je recommande deux choses pour améliorer cette question: 1) mieux définir le problème (par exemple, qu'est-ce qu'un voisin?) 2) essayer quelque chose et montrer votre tentative – user2297560
Vous pouvez commencer par faire une fonction "un pas", qui aura le même tapez comme 'f'. Pensez à comment 'f' peut utiliser cette fonction * plusieurs fois *, jusqu'à ce que certaines conditions soient atteintes. – Euge
C'est le cas parfait d'utilisation parfait pour un Comonad. Pas débutant amical, bien sûr, mais la façon la plus élégante de mettre en œuvre ce serait comme [Comonad] (https://hackage.haskell.org/package/comonad-5/docs/Control-Comonad.html#v:-61 --62--61-) instance (avec un type de données incluant chaque "cellule" et ses voisins). La solution conviviale pour les débutants utiliserait une carte sur chaque couche de la liste qui met à jour chaque cellule individuelle en fonction de ses voisins. – Lazersmoke