哈斯克爾單子功能

我經歷一個Haskell教程和我給這一段代碼做象棋移動騎士：哈斯克爾單子功能

import Control.Monad 

type KnightPos = (Int,Int) 

moveKnight :: KnightPos -> [KnightPos] 
moveKnight (c,r) = do 
    (c',r') <- [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1) 
       ,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2) 
       ] 
    guard (c' `elem` [1..8] && r' `elem` [1..8]) 
    return (c',r') 

in3 :: KnightPos -> [KnightPos] 
in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight 

canReachIn3 :: KnightPos -> KnightPos -> Bool 
canReachIn3 start end = end `elem` in3 start

的鍛鍊是修改功能，使canReachIn3告訴你什麼如果有可能達到目標位置，您可以採取措施達到最終位置。

本教程基本上沒有練習，所以我遇到了這樣的基本問題......我想將所有3個函數的返回值更改爲[[KnightPos]]，其中1個大列表包含每一個可能的移動順序。這可能會涉及再有moveKnight一個[KnightPos]參數而不是KnightPos之一，那麼這會破壞單子右側的整點？

任何幫助/想法將不勝感激，謝謝。「

來源

2011-12-06 Michael

這可能有助於思考這個代碼的時候，如果你發現普通的舊錶操作對於你更自然的步驟從單子概念回來了一點。所以，你可以重寫代碼示例（與清理的可讀性的一點點）爲：

type KnightPos = (Int,Int) 

moveKnight :: KnightPos -> [KnightPos] 
moveKnight (c,r) = filter legal candidates where 
    candidates = [(c+2,r-1), (c+2,r+1), (c-2,r-1), (c-2,r+1), 
        (c+1,r-2), (c+1,r+2), (c-1,r-2), (c-1,r+2)] 
    legal (c',r') = c' `elem` [1..8] && r' `elem` [1..8] 

in3 :: KnightPos -> [KnightPos] 
in3 start = concatMap moveKnight (concatMap moveKnight (moveKnight start)) 

canReachIn3 :: KnightPos -> KnightPos -> Bool 
canReachIn3 start end = end `elem` in3 start

的祕訣是concatMap。您可能已經知道，它與List單元中的>>=同義，但現在可能更有幫助，將其視爲將KnightPos -> [KnightPos]類型的函數映射到列表[KnightPos]以產生列表[[KnightPos]]，然後展開列表結果返回到單個列表中。

好吧，現在我們已經放棄了monads，讓我們回頭看看這個難題...假設您的初始KnightPos是(4,4)，並且您想跟蹤該位置所有可能的移動序列。因此，定義另一種類型的同義詞：

type Sequence = [KnightPos]

然後你想要moveKnight對這些序列進行操作，發現從序列中的最後一個位置的所有可能的行動：

moveKnight :: Sequence -> [Sequence]

因此，從一個序列[(4,4)]開始，我們會得到序列列表：[[(4,4), (6,3)], [(4,4), (6,5)], [(4,4), (2,3)], ... ]。然後，我想只有你需要做出in3的變化相應地修改它的類型簽名：

in3 :: Sequence -> [Sequence]

我不認爲在實際執行的變化。最後，你要canReachIn3看起來是這樣的：

canReachIn3 :: KnightPos -> KnightPos -> [Sequence]

我要離開的實現細節在這裏的目的，因爲我不想完全毀了謎題給你，但我希望我這裏已經闡明瞭關於列表，列表或任何列表沒有任何特別「特殊」的一點。我們所做的只是用類型Sequence -> [Sequence]的新功能替換了類型KnightPos -> [KnightPos]的功能 - 幾乎相同的形狀。因此，使用任何風格感覺自然的方式填寫每個函數的實現，然後一旦你有它的工作，回到一元風格，用>>=等替換concatMap。

來源

2011-12-06 07:54:12 mergeconflict

謝謝。 –

」那可能會涉及到moveKnight有[KnightPos]參數，而不是KnightPos ......「不，你不會這麼做的。儘可能保持基本功能。

「......然後將戰勝單子右側的整點？」好吧，如果你希望所有排序中移動，你就別在一舉一動使用join在>>=暗示。您可以定義一個函數從給定的起點，在這裏我們可以實現的路徑，傳遞，用於以相反的順序效率的原因的位置的列表返回長度ň的所有路徑的列表。

waysFrom :: KnightPos -> Int -> [[KnightPos]]

首先用於一個移動（或零）

waysFrom start 0 = [[start]] 
waysFrom start 1 = map (\t -> [t, start]) $ moveKnight start

，然後用於移動任意數，在該點可以再次使用使用>>=加入從簡單的遞歸產生的字典樹狀結構以招名單列表：

waysFrom start n = waysFrom start (n-1) >>= (\w -> [t:w | t<-moveKnight$head w])

有可能是一個更好的方式來做到這一點，但實際上不會「敗」單子整點。

來源

2011-12-06 07:44:04 leftaroundabout

我會建議作出KnightPos的數據結構能夠容納不僅是當前的藥水，還以爲它來自KnightPos：

data KnightPos = KnightPos {history :: Maybe KnightPos, position :: (Int,Int) }

然後，您需要實現EQ和顯示類，並修復moveKnight使其返回這個結構與它的歷史正確設置：

moveKnight :: KnightPos -> [KnightPos] 
moveKnight [email protected]{position = (c,r)} = do 
    (c',r') <- [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1) 
       ,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2) 
       ] 
    guard (c' `elem` [1..8] && r' `elem` [1..8]) 
    return $ KnightPos (Just p) (c',r')

確保你理解這個函數的最後一行。

函數in3現在應該可以不加修改地工作。我寫了一個新函數pathIn3 :: KnightPos -> KnightPos -> [[KinghtPos]]，它返回3個一元語句中從start到end的所有可能路徑。

尾翼警報

pathIn3 :: KnightPos - > KnightPos - > [[KnightPos]]
pathIn3開始端=做
p < - IN3啓動
後衛（p ==結束）
回報$ getHistory p你給了我足夠讓我堅持自己

來源

2011-12-07 03:04:57

哈斯克爾單子功能

回答

相關問題