Haskell以'do'表示法递归

Question

我正在阅读本教程http://learnyouahaskell.com/a-fistful-of-monads并偶然发现了这个定义:

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 = do   
    first <- moveKnight start  
    second <- moveKnight first  
    moveKnight second  

我有一个关于函数的问题in3(它在棋盘上获取一对坐标(Int,Int)并产生一个字段列表[(Int,Int)],可以从骑士的3个移动中从该字段到达).

是否有可能(如果是这样 - 如何做)将该函数重新制作
inNMoves :: (Num a) => KnightPos -> a -> [KnightPos]
成为一个参数,而不是被绑定到3个跳跃？

Answer 1

由于这个练习是关于List Monad的,所以尽量不要考虑你对列表的了解,但要限制自己的monad结构.那就是

move :: Monad m => Pos -> m Pos

也就是说,在一些monadic环境中,move拿一个Pos并给你一些关于Pos事物的东西m.(在列表的情况下,"上下文"是"任意多重性+排序".但是尽量不要考虑它).

另外,我们不要在do这里讨论哪种只是使用的语法糖(>>=).出于本说明的目的,您需要知道如何使用转换为表达式(>>=).

(>>=)有签名m a -> (a -> m b) -> m b.我们需要的实例m Pos -> (Pos -> m Pos) -> m Pos.你看我们都实例化a,并b在这里Pos.您还可以识别中间部分(Pos -> m Pos)被move这里的签名.因此,使用(>>=)并move作为第二个参数,我们可以创建一个类型的函数m Pos -> m Pos.

moveM :: Monad m => m Pos -> m Pos
moveM mp = mp >>= move

monad内同胚的组成

显然,m Pos -> m Pos可以按照您希望的顺序执行,因为它是从类型到自身的函数(我认为可以称为monad内同态,因为类型是monad).

让我们写一个做两个动作的函数.

move2M :: Monad m => m Pos -> m Pos
move2M mp = moveM (moveM (mp))

或者以无点样式(仅考虑转换,而不是转换对象):

move2M :: Monad m => m Pos -> m Pos
move2M = moveM . moveM

对于一般情况(由整数参数化的移动数n),我们只需要moveM通过函数链接运算符连接一些s ..所以如果n是3,我们想要moveM . moveM . moveM.以下是以编程方式执行此操作的方法:

nmoveM :: Monad m => Int -> m Pos -> m Pos
nmoveM n = foldr1 (.) (replicate n moveM)  -- n "moveM"s connected by (.)

这里出现一个问题:移动0次的结果是什么？foldr1对于n<= 0的值是未定义的.定义nmoveM 0为"无所事事" 是非常有意义的.换句话说,身份功能,id.

nmoveM :: Monad m => Int -> m Pos -> m Pos
nmoveM n = foldr (.) id (replicate n moveM)

在这里,我们使用foldr而不是foldr1需要额外的"基本案例",id.

现在我们基本上拥有我们想要的东西,但类型签名不适合100%:我们有m Pos -> m Pos,但我们想要Pos -> m Pos.这意味着,给定a Pos,我们首先必须将其嵌入上下文中m,然后执行nMoveM.这个嵌入运算符(我认为它可以称为初始代数)是return(类型Monad m => a -> m a)

nmoves :: Monad m => Int -> Pos -> m Pos
nmoves n = nmoveM n . return

让我们一下子写下所有这些,这样你就可以欣赏到它充满光彩的简洁.

nmoves :: Monad m => Int -> Pos -> m Pos
nmoves n = foldr (.) id (replicate n move) . return

箭头的组成

使用(>>=)实际上通常有点不洁,因为它是如此不对称:它需要一个m a和一个a -> m b.换句话说,它对转换的对象有点过于关注,而只关注我们案例的转换.这使得组合转换变得不必要地困难.这就是为什么我们必须坚持. return:它是从初始转换Pos到m Pos,所以我们可以自由组合任意数量的m Pos -> m Pos.

使用(>>=)以下模式的结果:

ma >>= f_1 >>= f_2 >>= ... >>= f_n

哪里ma是monad的东西,f_i是类型的"箭头" a -> m b(通常a = b).

有一个更好的变体,(>=>)它a -> m b在一个序列中组合了两个类型的箭头,并返回另一个箭头.

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

在这里,我们并没有不必要地关注转换的对象,而只关注转换及其组成.

现在让我们同意这move实际上是一个箭头(Pos -> m Pos).所以

move >=> move >=> move >=> move >=> move

是一个仍然是类型的有效表达式Pos -> m Pos.使用时,monad的可组合性质变得更加明显(>=>).

我们可以重新写nmoves使用(>=>)像这样:

nmoves :: Monad m => Int -> Pos -> m Pos
nmoves n = foldr1 (>=>) (replicate n move)  -- n "move"s connected by >=>

再次,我们使用了foldr1,我们问"什么给了0次连续移动"？它必须是同一类型,Pos -> m Pos答案是return.

nmoves :: Monad m => Int -> Pos -> m Pos
nmoves n = foldr (>=>) return (replicate n move)

与此相比,我们前面的定义nmoves在单子同态世界:与其职能联合(.)和基本情况id,现在我们结合了箭头(>=>)和基本情况return.好处是我们不必注入给定Pos的m Pos.

更有意义的取决于你的情况,但往往比(>=>)更清洁(>>=).