在IO monad中进行递归

Question

我一直试图弄清楚如何在IO monad中进行递归.我熟悉使用纯函数进行递归,但是无法将这些知识传递给IO monad.

使用纯函数递归
我很喜欢用纯函数进行递归,例如foo下面的函数.

foo (x:y:ys) = foo' x y ++ foo ys

一个带有IO [String]输出
的函数我做了一个像goo下面这样的函数,它可以满足我的需求并具有IO输出.

goo :: String -> String -> IO [String]
goo xs ys = goo' xs ys 

试图在IO monad中获取递归
当我尝试在IO monad中进行递归时(例如,"主"函数)我不能.我抬头一看liftM,replicateM和撤消最IO <-操作或功能.我想要一个IO monad hoo或者hoo'(为随后的乱码道歉).

hoo :: [String] -> IO [String]
hoo (xs:ys:yss) = do
                  let rs = goo xs ys ++ hoo yss
                  return rs

要么

hoo' :: [String] -> IO [String]
hoo' (xs:ys:yss) = do
                  rs <- goo xs ys 
                  let gs = rs ++ hoo' yss
                  return gs

(顺便说一句,如果你想知道我的项目是什么,我正在编写一个遗传算法程序从头开始.我的goo函数需要两个父母并繁殖两个后代,它们作为IO返回,因为goo使用随机数生成器.我需要做的是使用递归hoo函数goo从20个父母的名单中培育20个后代.我的想法是将前两个父母列入名单,培育两个后代,接下来的两个父母列表,培育另一对后代,依此类推.)

Answer 1

如果您发现do符号令人困惑,我的建议是根本不使用它.你可以做你需要的一切>>=.只是假装它的类型是

(>>=) :: IO a -> (a -> IO b) -> IO b

那就是说,让我们来看看你的代码.

let在do块中给出了某个值的名称.这与它在外面做的是一样的do,所以这里没有用(它没有给你额外的力量).

<- 更有趣的是:它充当"从本地IO提取值"构造(如果你稍微眯一下).

hoo :: [String] -> IO [String]
hoo (xs:ys:yss) = do
    -- The right-hand side (goo xs ys) has type IO [String], ...
    rs <- goo xs ys
    -- ... so rs :: [String].

    -- We can apply the same construct to our recursive call:
    hs <- hoo yss
    -- hoo yss :: IO [String], so hs :: [String].

    let gs = rs ++ hs
    return gs

如上所述,let只需将名称绑定到值,所以我们在这里并不需要它:

hoo :: [String] -> IO [String]
hoo (xs:ys:yss) = do
    rs <- goo xs ys
    hs <- hoo yss
    return (rs ++ hs)

或者,没有do符号,<-我们按如下方式进行.

(>>=) :: IO a -> (a -> IO b) -> IO b

>>=接受一个IO值和一个回调函数,它在"unwrapped"值(a)上运行函数.这意味着在函数内部,只要整个事物的结果IO b再次出现(对于某些任意类型b),我们就可以获得对值的本地访问.

hoo :: [String] -> IO [String]
hoo (xs : ys : yss) =
    goo xs ys -- :: IO [String]
    ...

我们有一个IO [String],我们需要做一些事情[String],所以我们使用>>=:

hoo :: [String] -> IO [String]
hoo (xs : ys : yss) =
    goo xs ys >>= (\rs -> ...)

如果你看一下>>=类型签名,那么这个角色a是由[String]here(rs :: [String])扮演的,b也是[String](因为hoo整体需要返回IO [String]).

那么我们在这...部分做什么呢？我们需要进行递归调用hoo,这又会产生一个IO [String]值,所以我们>>=再次使用:

hoo :: [String] -> IO [String]
hoo (xs : ys : yss) =
    goo xs ys >>= (\rs -> hoo yss >>= (\hs -> ...))

再次,hs :: [String]并且...更好地使用类型IO [String]来完成整个事情.

现在我们已经rs :: [String]和hs :: [String],我们可以简单地连接它们:

hoo :: [String] -> IO [String]
hoo (xs : ys : yss) =
    goo xs ys >>= (\rs -> hoo yss >>= (\hs -> rs ++ hs))  -- !

这是一个类型错误.rs ++ hs :: [String],但背景需要IO [String].幸运的是,有一个功能可以帮助我们:

return :: a -> IO a

现在它是typechecks:

hoo :: [String] -> IO [String]
hoo (xs : ys : yss) =
    goo xs ys >>= (\rs -> hoo yss >>= (\hs -> return (rs ++ hs)))

由于Haskell语法的工作方式(函数体尽可能向右扩展),这里的大多数parens实际上是可选的:

hoo :: [String] -> IO [String]
hoo (xs : ys : yss) =
    goo xs ys >>= \rs -> hoo yss >>= \hs -> return (rs ++ hs)

通过一些重新格式化,整个事情可以看起来很有启发性:

hoo :: [String] -> IO [String]
hoo (xs : ys : yss) =
    goo xs ys >>= \rs ->
    hoo yss   >>= \hs ->
    return (rs ++ hs)