2017-10-18 16 views
5

J'essaye de former une grille infinie comme la structure de données en attachant le noeud.Comment construisez-vous une structure infinie comme la structure de données dans Haskell?

Ceci est mon approche:

import Control.Lens 

data Grid a = Grid {_val :: a, 
        _left :: Grid a, 
        _right :: Grid a, 
        _down :: Grid a, 
        _up :: Grid a} 

makeLenses ''Grid 

makeGrid :: Grid Bool -- a grid with all Falses 
makeGrid = formGrid Nothing Nothing Nothing Nothing 

formGrid :: Maybe (Grid Bool) -> Maybe (Grid Bool) -> Maybe (Grid Bool) -> Maybe (Grid Bool) -> Grid Bool 
formGrid ls rs ds us = center 
    where 
    center = Grid False leftCell rightCell downCell upCell 
    leftCell = case ls of 
       Nothing -> formGrid Nothing (Just center) Nothing Nothing 
       Just l -> l 
    rightCell = case rs of 
       Nothing -> formGrid (Just center) Nothing Nothing Nothing 
       Just r -> r 
    upCell = case us of 
       Nothing -> formGrid Nothing Nothing (Just center) Nothing 
       Just u -> u 
    downCell = case ds of 
       Nothing -> formGrid Nothing Nothing Nothing (Just center) 
       Just d -> d 

Pour une raison quelconque, cela ne fonctionne pas. Comme vu ici:

*Main> let testGrid = (set val True) . (set (right . val) True) $ makeGrid 
*Main> _val $ _right $ _left testGrid 
False 
*Main> _val $ _left $ _right testGrid 
False 
*Main> _val $ testGrid 
True 

Où est-ce que je vais mal?

+1

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'. –

+0

@FyodorSoikin Cela mérite d'être la réponse; c'est ce que je commençais à écrire. – Cirdec

+0

@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. :-) –

Répondre

3

L'idée clé est: lorsque vous set val True, vous ne modifiez pas en place, mais en créant une copie.

makeGrid construit une grille où tout est False, y compris _left $ _right center. Lorsque vous set val True sur le center, vous créez une copie center'val center' == True. Cependant, cette copie pointe toujours à la même _right, ce qui souligne encore la même _left, autrement dit:

_right center' == _right center 

et donc:

_left $ _right center' == _left $ _right center == center 

de sorte que:

_val . _left $ _right center' == _val . _left $ _right center == False 
+0

Y at-il un moyen de le faire correctement en mettant à jour les voisins de manière appropriée, ou quelque chose comme ça? –

+0

@Agnishom Si vous mettez à jour les voisins, vous aurez le même problème avec les voisins des voisins plus éloignés, et ainsi de suite. Les structures de données avec des "références arrière" comme celle-ci sont une douleur avec des types immuables, pour exactement cette raison. Vous pourriez être en mesure d'obtenir ce travail avec la paresse, au prix d'accumuler des thunks dans * chaque * cellule que vous apportez des modifications, mais c'est juste une peine de travailler avec. Nous utilisons généralement différentes techniques. – Ben

5

@ 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