हास्केल में डेटा संरचना जैसे अनंत ग्रिड कैसे बनाते हैं?

Question

मैं गाँठ बांधकर डेटा संरचना जैसे अनंत ग्रिड बनाने की कोशिश कर रहा हूं।

यह मेरा दृष्टिकोण है:

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 

किसी कारण के लिए, यह काम नहीं कर रहा। जैसा कि यहां देखा गया है:

*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 

मैं गलत कहां जा रहा हूं?

Answer 1

मुख्य अंतर्दृष्टि है: जब आप set val True, आप जगह में संशोधन नहीं कर रहे हैं, लेकिन एक प्रति बना रहे हैं।

makeGrid एक ग्रिड बनाता है जहां सब कुछ False है, जिसमें _left $ _right center शामिल है। पर center पर, आप एक प्रतिलिपि बना रहे हैं center' जहां val center' == True।

_right center' == _right center 

और इसलिए:

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

ताकि:

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

बहरहाल, यह प्रति अब भी एक ही _right, जो बारी में अब भी वही _left को इंगित करता है, दूसरे शब्दों में के लिए अंक

Answer 2

@ फ्योडोर का जवाब बताता है कि आपका वर्तमान दृष्टिकोण क्यों काम नहीं करेगा। कार्यात्मक भाषाओं में इस पूरा करने की

एक सामान्य तरीका zippers उपयोग कर रहा है (zip या संबंधित कार्यों के साथ भ्रमित होने की नहीं)।

विचार यह है कि जिपर डेटा संरचना का एक विशेष भाग (उदाहरण के लिए, ग्रिड में एक सेल) पर केंद्रित है। आप इस फोकस को "फोकस" करने के लिए जिपर में परिवर्तन लागू कर सकते हैं, और आप फोकस के सापेक्ष डेटा संरचना क्वेरी या "उत्परिवर्तित" करने के लिए विभिन्न परिवर्तन लागू कर सकते हैं। दोनों प्रकार के परिवर्तन पूरी तरह से कार्यात्मक हैं - वे एक अपरिवर्तनीय जिपर पर कार्य करते हैं और केवल एक नई प्रतिलिपि बनाते हैं।

यहाँ, आप स्थिति जानकारी के साथ एक अनंत सूची के लिए एक ज़िपर के साथ शुरू कर सकते हैं:

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) 

यह Zipper एक दोगुना अनंत सूची का प्रतिनिधित्व (होना है यानी, कि में अनंत है एक सूची दोनों दिशाओं में)। एक उदाहरण होगा:

> Zipper [-10,-20..] 0 0 [10,20..] 
[-30,-20,-10] (0,0) [10,20,30] 

यह (सकारात्मक और नकारात्मक) दस मूल्य 0, स्थिति 0 पर ध्यान केंद्रित की पूर्णांक गुणकों सभी की सूची का प्रतिनिधित्व करने का इरादा है और यह वास्तव में दो हास्केल अनंत सूची, एक के लिए उपयोग करता है प्रत्येक दिशा।

आप फोकस आगे बढ़ने या वापस करने के लिए कार्यों को परिभाषित कर सकते हैं:

> 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] 
> 

अब, एक Grid प्रत्येक पंक्ति के साथ, पंक्तियों की एक ज़िपर के रूप में प्रतिनिधित्व किया जा सकता है:

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 

और यह एक समारोह है कि फोकस बढ़ता रहता है जोड़ने के लिए सुविधाजनक हो सकता है फोकस से चलती कार्यों का एक सेट के साथ एक साथ 0,403,210 वापस प्रदर्शन प्रयोजनों के लिए मूल करने के लिए:

recenter :: Grid a -> Grid a 
recenter g@(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 

अंत में, एक समारोह है कि एक सब False ग्रिड बनाता है के साथ:

falseGrid :: Grid Bool 
falseGrid = 
    let falseRow = Zipper falses False 0 falses 
     falses = repeat False 
     falseRows = repeat falseRow 
    in Grid (Zipper falseRows falseRow 0 falseRows) 

आप की तरह कर सकते हैं:

> 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 
> 

पूर्ण उदाहरण:

{-# 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 g@(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