@ La réponse de Fyodor explique pourquoi votre approche actuelle ne fonctionnera pas.
Une façon courante d'y parvenir dans les langages fonctionnels utilise zippers (à ne pas confondre avec zip
ou fonctions connexes).
L'idée est que la fermeture à glissière est une représentation de la structure de données focalisée sur une partie particulière (par exemple, une cellule dans la grille). Vous pouvez appliquer des transformations à la fermeture à glissière pour "déplacer" ce focus autour, et vous pouvez appliquer différentes transformations pour interroger ou "muter" la structure de données par rapport au focus. Les deux types de transformations sont purement fonctionnels - ils agissent sur une fermeture à glissière immuable et juste créer une nouvelle copie.
Ici, vous pouvez commencer par une fermeture à glissière pour une liste infinie avec des informations de position :
data Zipper a = Zipper [a] a Int [a] deriving (Functor)
-- Zipper ls x n rs represents the doubly-infinite list (reverse ls ++
-- [x] ++ rs) viewed at offset n
instance (Show a) => Show (Zipper a) where
show (Zipper ls x n rs) =
show (reverse (take 3 ls)) ++ " " ++ show (x,n) ++ " " ++ show (take 3 rs)
Ce Zipper
est destiné à être une représentation d'une liste doublement infinie (c.-à-une liste qui est infini les deux directions). Un exemple serait:
> Zipper [-10,-20..] 0 0 [10,20..]
[-30,-20,-10] (0,0) [10,20,30]
Ceci a pour but de représenter la liste de tous (positives et négatives) multiples entiers de dix porté à la valeur 0
, la position 0
et il utilise en fait deux listes infinies Haskell, un pour chaque direction.
Vous pouvez définir des fonctions pour déplacer le focus vers l'avant ou l'arrière:
back, forth :: Zipper a -> Zipper a
back (Zipper (l:ls) x n rs) = Zipper ls l (n-1) (x:rs)
forth (Zipper ls x n (r:rs)) = Zipper (x:ls) r (n+1) rs
de telle sorte que:
> forth $ Zipper [-10,-20..] 0 0 [10,20..]
[-20,-10,0] (10,1) [20,30,40]
> back $ back $ Zipper [-10,-20..] 0 0 [10,20..]
[-50,-40,-30] (-20,-2) [-10,0,10]
>
Maintenant, un Grid
peut être représentée par une fermeture à glissière de lignes, chaque ligne a fermeture éclair des valeurs:
newtype Grid a = Grid (Zipper (Zipper a)) deriving (Functor)
instance Show a => Show (Grid a) where
show (Grid (Zipper ls x n rs)) =
unlines $ zipWith (\a b -> a ++ " " ++ b)
(map show [n-3..n+3])
(map show (reverse (take 3 ls) ++ [x] ++ (take 3 rs)))
avec un ensemble de fonctions en mouvement mise au point:
up, down, right, left :: Grid a -> Grid a
up (Grid g) = Grid (back g)
down (Grid g) = Grid (forth g)
left (Grid g) = Grid (fmap back g)
right (Grid g) = Grid (fmap forth g)
Vous pouvez définir un getter et setter pour l'élément ciblé:
set :: a -> Grid a -> Grid a
set y (Grid (Zipper ls row n rs)) = (Grid (Zipper ls (set' row) n rs))
where set' (Zipper ls' x m rs') = Zipper ls' y m rs'
get :: Grid a -> a
get (Grid (Zipper _ (Zipper _ x _ _) _ _)) = x
et il peut être pratique d'ajouter une fonction qui déplace le focus Retour à l'origine à des fins d'affichage:
recenter :: Grid a -> Grid a
recenter [email protected](Grid (Zipper _ (Zipper _ _ m _) n _))
| n > 0 = recenter (up g)
| n < 0 = recenter (down g)
| m > 0 = recenter (left g)
| m < 0 = recenter (right g)
| otherwise = g
Enfin, une fonction qui crée une grille False
tout-:
falseGrid :: Grid Bool
falseGrid =
let falseRow = Zipper falses False 0 falses
falses = repeat False
falseRows = repeat falseRow
in Grid (Zipper falseRows falseRow 0 falseRows)
vous pouvez faire des choses comme:
> let (&) = flip ($)
> let testGrid = falseGrid & set True & right & set True & recenter
> testGrid
-3 [False,False,False] (False,0) [False,False,False]
-2 [False,False,False] (False,0) [False,False,False]
-1 [False,False,False] (False,0) [False,False,False]
0 [False,False,False] (True,0) [True,False,False]
1 [False,False,False] (False,0) [False,False,False]
2 [False,False,False] (False,0) [False,False,False]
3 [False,False,False] (False,0) [False,False,False]
> testGrid & right & left & get
True
> testGrid & left & right & get
True
> testGrid & get
True
>
L'exemple complet:
{-# LANGUAGE DeriveFunctor #-}
module Grid where
data Zipper a = Zipper [a] a Int [a] deriving (Functor)
-- Zipper ls x n rs represents the doubly-infinite list (reverse ls ++
-- [x] ++ rs) viewed at offset n
instance (Show a) => Show (Zipper a) where
show (Zipper ls x n rs) =
show (reverse (take 3 ls)) ++ " " ++ show (x,n) ++ " " ++ show (take 3 rs)
back, forth :: Zipper a -> Zipper a
back (Zipper (l:ls) x n rs) = Zipper ls l (n-1) (x:rs)
forth (Zipper ls x n (r:rs)) = Zipper (x:ls) r (n+1) rs
newtype Grid a = Grid (Zipper (Zipper a)) deriving (Functor)
instance Show a => Show (Grid a) where
show (Grid (Zipper ls x n rs)) =
unlines $ zipWith (\a b -> a ++ " " ++ b)
(map show [n-3..n+3])
(map show (reverse (take 3 ls) ++ [x] ++ (take 3 rs)))
up, down, right, left :: Grid a -> Grid a
up (Grid g) = Grid (back g)
down (Grid g) = Grid (forth g)
left (Grid g) = Grid (fmap back g)
right (Grid g) = Grid (fmap forth g)
set :: a -> Grid a -> Grid a
set y (Grid (Zipper ls row n rs)) = (Grid (Zipper ls (set' row) n rs))
where set' (Zipper ls' x m rs') = Zipper ls' y m rs'
get :: Grid a -> a
get (Grid (Zipper _ (Zipper _ x _ _) _ _)) = x
recenter :: Grid a -> Grid a
recenter [email protected](Grid (Zipper _ (Zipper _ _ m _) n _))
| n > 0 = recenter (up g)
| n < 0 = recenter (down g)
| m > 0 = recenter (left g)
| m < 0 = recenter (right g)
| otherwise = g
falseGrid :: Grid Bool
falseGrid =
let falseRow = Zipper falses False 0 falses
falses = repeat False
falseRows = repeat falseRow
in Grid (Zipper falseRows falseRow 0 falseRows)
(&) = flip ($)
testGrid :: Grid Bool
testGrid = falseGrid & set True & right & set True & recenter
main = do
print $ testGrid & get
print $ testGrid & left & get
print $ testGrid & left & right & get
print $ testGrid & right & left & get
Lorsque vous 'set val true', vous n'êtes pas modifier en place, mais la création d'une copie . 'makeGrid' construit une grille où tout est' False', y compris 'center -> right -> left'. Lorsque vous fixez la valeur True au centre, vous créez une copie 'center'' où' val center '== True', mais '_right center' == _right center', et donc' _left $ _right center ' == _left $ _right centre == Faux'. –
@FyodorSoikin Cela mérite d'être la réponse; c'est ce que je commençais à écrire. – Cirdec
@cirdec Je n'avais pas l'impression que cela répondait à la question, puisque la question était «comment fais-tu ça?», Pas «pourquoi ma tentative n'a-t-elle pas fonctionné? Mais vu comment vous avez supprimé votre réponse, je vais faire mon commentaire en un. :-) –