हास्केल - सूची मोनैड

Question

के साथ टिक टैक पैर की अंगुली खेल में अगली चाल कैसे उत्पन्न करें I Haskell में n * n बोर्ड के लिए एक टिक टैक पैर गेम लागू कर रहा हूं और मुझे अगले बोर्ड से सभी बोर्ड कॉन्फ़िगरेशन जेनरेट करने की आवश्यकता है।

मैं बोर्ड के रूप में परिभाषित किया है इस प्रकार है:

data Cell = E 
     | X 
     | O 
     deriving (Eq,Show) 

type Row a = [a] 
type Board = Row (Row Cell) 

iniBoard :: Int -> Board 
iniBoard n = let row = replicate n E in replicate n row 

मैं निर्धारित कर सकते हैं, यह देखते हुए बोर्ड विन्यास खिलाड़ी x के लिए जीत रहा है, तो मैं

win :: Cell -> Board -> Bool 
win E _ = False 
win x brd = any full $ diags brd ++ rows brd ++ cols brd 
where 
    diags brd = mainDiag : [secondDiag] 
    mainDiag = zipWith (!!) brd [0..] 
    secondDiag = zipWith (!!) revBrd [0..] 
    revBrd = do 
     xs <- brd 
     return (reverse xs) 
    rows = id 
    cols = transpose 
    full xs = all (==x) xs 

है लेकिन मुझे पता नहीं, कैसे करने के लिए है कि क्या सभी बोर्ड कॉन्फ़िगरेशन उत्पन्न करें जो खिलाड़ी x अगले कदम के रूप में बना सकते हैं।

मैं समझता हूं कि मुझे सभी कोशिकाओं को पार करने और जांचने की आवश्यकता है, यदि सेल खाली है, तो मैं यहां चिह्न डाल सकता हूं और नई कॉन्फ़िगरेशन वापस कर सकता हूं। मैं पहले से ही विन्यास जीतने की है, तो वहाँ कोई अगला कदम है, और मैं खाली सूची

लौटना चाहिए मैं इस तरह एक कोड है:

nxt :: Cell -> Board -> [Board] 
nxt x brd = do 
if (win x brd || win (switch x) brd) 
    then 
     [] 
    else 
     undefined 

कैसे मैं यह कर सकता, सूची इकाई का उपयोग कर? मदद के लिए धन्यवाद!

Answer 1

picks :: [x] -> [([x], x, [x])] 
picks [] = [] 
picks (x : xs) = ([] , x, xs) : [(x : sy, y, ys) | (sy, y, ys) <- picks xs] 

साथ

(this के ट्वीक संस्करण है), के लिए सभी संभव अगले बोर्डों

import Data.List.Split (chunksOf) 

next :: Int -> Cell -> Board -> [Board] 
next n who b = 
    picks (concat b) >>= \(sy, y, ys) -> 
      case y of E -> [chunksOf n $ sy ++ [who] ++ ys] ; 
         _ -> [] 

जहां whoX या O, या पाठ्यक्रम में से एक है कर रहे हैं।

यह खाली रखने के लिए फ़िल्टर से अधिक कुछ नहीं है, और एक ही समय में फ़िल्टर किए गए लोगों पर एक नक्शा है। यह सूची comprehensions साथ भी सरल

next n who b = [ chunksOf n $ sy ++ [who] ++ ys 
       | (sy, E, ys) <- picks $ concat b ] 

picks समारोह, हर संभव कोशिकाओं, एक के बाद एक, श्रेणीबद्ध पंक्तियों में लेती है जबकि यह भी एक उपसर्ग और प्रत्यय संरक्षण है; chunksOf n एक पंक्ति में n कोशिकाओं के हिस्सों में, कोशिकाओं की एक लंबी पंक्ति से बोर्ड का पुनर्निर्माण करता है। तो समग्र प्रभाव सभी संभावित बोर्डों की एक सूची है जहां Ewho के साथ बदल दिया गया है।

अधिक कुशल picks इसके उपसर्ग (sy) को उल्टा क्रम में बनाएगा; "ज़िप्पर" के रूप में जाना जाने वाला एक सूची बनाना। फिर पुनर्निर्माण पर उन्हें संगत रूप से उलट जाना होगा।

संपादित करें: के रूप में सूची समझ से पता चलता है, यह हो सकता है के साथ लिखा गया है पहली जगह में अंकन कार्य करें:

next n who b = do 
    (sy, E, ys) <- picks $ concat b 
    return (chunksOf n $ sy ++ [who] ++ ys]) 

do में अंकन एक पैटर्न बेमेल fail के लिए एक कॉल, में अनुवाद किया है जो , सूची मोनैड में, तत्व को छोड़ने का कारण बनता है जबकि पूर्ण रूप से गणना पूरी तरह विफल रहता है।

EDIT2: एक Data.List आधारित कोड जो इनपुट के ऊपर एक पास में यह होता है, है

import Data.List (mapAccumL) 

-- mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y]) 
next who b = concat . snd $ mapAccumL f (id, drop 1 xs) xs 
    where 
    xs = concat b 
    n = length b 
    f (k,r) x = ((k.(x:), drop 1 r) , [chunksOf n $ k (who:r) | x==E]) 

धन्यवाद चर्चा के लिए ברקן גלעד करने के लिए।

Answer 2

अगर हम >>= के लिए प्रकार हस्ताक्षर को देखो हम देखते हैं कि यह

(>>=) :: Monad m => m a -> (a -> m b) -> m b 

है आप "श्रृंखला" अपने nxt समारोह, बाँध के लिए पूरे प्रकार हस्ताक्षर होना चाहिए करने में सक्षम होना चाहते हैं:

[Board] -> (Board -> [Board]) -> [Board] 

तो nxt में Board -> [Board] टाइप होना चाहिए। अब हमें खुद से पूछना चाहिए कि वास्तव में nxt क्या करता है: यह बोर्ड लेता है और वर्तमान बोर्ड से सभी संभावित चाल देता है। संयोग से, nxt के लिए प्रकार बिल्कुल >>= की आवश्यकता है: Board -> [Board]। लेकिन रुकें। हम कैसे जानते हैं कि यह किसकी बारी है? जैसा कि आपने पहले ही किया है, हम वर्तमान चिह्न को पैरामीटर के रूप में स्थानांतरित कर सकते हैं, लेकिन यह प्रकार हस्ताक्षर को भी बदल देता है: Cell -> Board -> [Board]। क्या हम अभी भी इस समारोह को चेन कर सकते हैं? हां हम कर सकते हैं। आंशिक आवेदन का उपयोग करना, हम पहले से ही पहले से ही इसे पारित और फिर जिसके परिणामस्वरूप समारोह जुड़ कर रखने के लिए अगले मार्कर लागू कर सकते हैं:

nxt :: Cell -> Board -> [Board] 
nxt X ::   Board -> [Board] 

अब सब हम क्या करना है हर क्षेत्र पार है और जाँच करें कि क्या यह खाली है। यदि यह है, तो हम इसे अपने निशान से बदलते हैं और अन्य क्षेत्रों को पार करते हैं। :

nxt :: Cell -> Board -> [Board] 
nxt _ []   = [] 
nxt mark (row:rest) = map (:rest) (replaceAll mark row) ++ (map (row:) $ nxt mark rest) 
    where 
    replaceAll _ [] = [] 
    replaceAll m (x:xs) 
     | x == E = (m:xs) : (map (x:) $ replaceAll m xs) 
     | otherwise = map (x:) $ replaceAll m xs 

अब आप कर सकते हैं इस तरह श्रृंखला चाल:

iniState 3 >>= nxt X >>= nxt O 

मैं अनुकरण समारोह और वास्तविक कदम अधिक से अधिक उपयोग के प्रयोजनों के लिए समारोह की खोज को अलग करने की सलाह देंगे।

winner :: Cell -> Int -> [Board] 
winner who size = filter (win who) 
       $ foldr (>=>) return (take (n*n) $ cycle [nxt O, nxt X]) 
       $ initBoard n 

मैं खेल एक व्यायाम के रूप भूमिका निभा लागू करने के लिए आप के लिए छोड़ देगा: उदाहरण के लिए, इस तरह आप आसानी से एक समारोह है जो सभी बोर्डों जो एक विशिष्ट आकार और एक विशिष्ट खिलाड़ी के लिए जीतेंगे रिटर्न लिख सकते हैं।

Answer 3

अन्य उत्तरों में सीधा समाधान शामिल है। यहां मैं lens समाधान प्रस्तुत करता हूं, क्योंकि यह कार्य के लिए अच्छी तरह से लागू है।

lens के साथ हम अलग से निम्नलिखित दो बातें निर्दिष्ट कर सकते हैं:

• कौन सा एक डेटा संरचना हम पर काम करना चाहते हैं के कुछ हिस्सों।
• हम उन हिस्सों पर क्या संचालन करना चाहते हैं।

हम बोर्ड की खाली कोशिकाओं को लक्ष्य के रूप में इंगित करना चाहते हैं। Traversal' Board Cell इंगित करता है कि समग्र डेटा संरचना में Board टाइप किया गया है, जबकि लक्ष्य Cell टाइप करते हैं।

import Control.Lens 

emptyCells :: Traversal' Board Cell 
emptyCells = each . each . filtered (==E) 

अब हम emptyCells के साथ विभिन्न प्रकार के संचालन कर सकते हैं।

board = iniBoard 3 

-- get the number of targets: 
lengthOf emptyCells board -- 9 

-- return a flat list of the targets 
toListOf emptyCells board -- [E,E,E,E,E,E,E,E,E] 

-- set all targets to a value 
set emptyCells X board -- [[X,X,X],[X,X,X],[X,X,X]] 

-- set the nth target to a value 
set (elementOf emptyCells 2) X board -- [[E,E,X],[E,E,E],[E,E,E]] 

-- get the nth target, if it exists 
preview (elementOf emptyCells 2) board -- Just E 

हम भी बड़े करीने से nextemptyCells और holesOf समारोह का उपयोग कर लागू कर सकते हैं। holesOf emptyCells बोर्ड के "छेद" की सूचियां देता है। प्रत्येक छेद में अनिवार्य रूप से Cell और एक फ़ंक्शन होता है जो Cell तर्क लेता है और आपूर्ति की गई Cell एक निश्चित स्थिति में प्लग किए गए एक नया Board देता है।

दुर्भाग्य से, छेद को अमूर्त रूप से कार्यान्वित किया जाता है, और holesOf emptyCells में एक अनौपचारिक Board ->[Control.Lens.Internal.Context.Pretext (->) Cell Cell Board] प्रकार है। हमें बस याद रखना चाहिए कि Control.Comonad.Store छेद के साथ काम करने के लिए एक इंटरफ़ेस प्रदान करता है। pos एक छेद का फोकस तत्व देता है (यहां यह Cell है), जबकि peek छेद में एक नया तत्व प्लग करता है और परिणामी डेटा संरचना देता है।

nxt x board के लिए, हमें x में खाली सेल के साथ प्रत्येक स्थिति में प्लग करने की आवश्यकता है। इसे ध्यान में रखते, nxt बस हो जाता है:

import Control.Comonad.Store 

nxt :: Cell -> Board -> [Board] 
nxt x = map (peek x) . holesOf emptyCells 

Answer 4

यहाँ एक संस्करण है कि बोर्ड को पार करता है और जब एक E का सामना कर केवल एक संभव कदम जोड़ता है:

nxt' :: Cell -> Board -> [Board] 
nxt' x brd = do (E,i) <- zip b [0..] 
       return (chunksOf l $ (take i b) ++ [x] ++ (drop (i + 1) b)) 
       where l = length brd 
        b = concat brd