Haskell Monad函数

Question

我正在通过一个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,然后就会击败monad的整个点？

任何帮助/想法将不胜感激,谢谢.

Answer 1

如果您发现普通的旧列表操作对您来说更自然,那么在考虑此代码时,从Monad概念中退一步可能会有所帮助.因此,您可以重写示例代码(通过一点清理以获得易读性):

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.正如您可能已经知道的那样,它>>=在Listmonad中是同义词,但现在可能更有帮助的是将其视为KnightPos -> [KnightPos]在列表[KnightPos]上映射类型函数以生成列表列表[[KnightPos]],然后将结果展平为单个名单.

好吧,现在我们暂时放弃了monad,让我们回顾一下这个难题......让我们说你的初始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]

我故意将实施细节留在这里,因为我不想完全毁掉你的谜题,但我希望我在这里说明了一个关于列表没有特别"特殊"的观点. ,或列表清单,或其他.我们真正做的就是用类型KnightPos -> [KnightPos]的新函数替换类型的函数Sequence -> [Sequence]- 几乎相同的形状.因此,使用任何感觉自然的方式填写每个函数的实现,然后一旦你有它工作,回到monadic样式,替换concatMap为>>=等等.