4

我一直试图弄清楚如何在 IO monad 中进行递归。我熟悉使用纯函数进行递归，但无法将这些知识转移到 IO monads。

使用纯函数递归
我很乐意使用纯函数进行递归，例如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 中进行递归时（例如，“main”函数），我做不到。我查找了liftM,replicateM和 undo-the-IO<-运算符或函数。我想要一个类似hooor的 IO monad 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 个后代。我的想法是取列表中的前两个父母，繁殖两个后代，带上接下来的两个父母名单，繁殖另一对后代，依此类推。）

4

3 回答 3

5

如果您发现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上运行该函数。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 -> ...)

如果看>>='s 的类型签名，这里 ( )a起到的作用也是 is （因为整体需要 return ）。[String]rs :: [String]b[String]hooIO [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]and 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

现在它进行类型检查：

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

由于 Haskell 语法的工作方式（函数体尽可能向右延伸），这里的大多数括号实际上是可选的：

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)
于 2018-06-26T05:14:01.117 回答
2

do记法非常方便。使用它，它是你的朋友。我们只需要遵循它的规则，如果每个进入它的位置的东西都必须相应地具有正确的类型。

你非常接近：

goo :: String -> String -> IO [String]

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

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

用do符号表示，x <- foo当 时foo :: IO a，我们有x :: a。而已。（更多的解释是例如here）。

至于递归，它是通过do符号来实现的，就像在纯代码中实现的一样：通过命名事物，并从定义该名称的表达式内部引用相同的名称，无论它是纯表达式还是do符号。

递归是信念的飞跃。我们不关心事物是如何定义的——我们假设它是正确定义的，所以我们可以通过它的名称来引用它。只要类型合适。

于 2018-06-26T13:41:00.873 回答
1

要使用do符号执行此操作，您需要绑定每个IO操作的结果，以便在纯表达式中使用这些结果，例如let rs =...<code>++...，如下所示：

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

但是，通常您不想为每个操作的结果引入一个临时名称，因此在典型的 Haskell 代码中，有一些组合器可以使这种事情更加紧凑。在这里您可以使用liftA2：

liftA2
  :: Applicative f

  -- Given a pure function to combine an ‘a’ and a ‘b’ into a ‘c’…
  => (a -> b -> c)

  -- An action that produces an ‘a’…
  -> f a

  -- And an action that produces a ‘b’…
  -> f b

  -- Make an action that produces a ‘c’.
  -> f c

像这样：

hoo (xs:ys:yss) = liftA2 (++) (goo xs ys) (hoo yss)

liftA2但是，仅适用于具有两个参数的函数；对于应用其他数量参数的函数，您可以使用Functor运算符<$>（的别名fmap）和Applicative运算符<*>：

(<$>)
  :: Functor f

  -- Given a pure function to transform an ‘a’ into a ‘b’…
  => (a -> b)

  -- And an action that produces an ‘a’…
  -> f a

  -- Make an action that produces a ‘b’.
  -> f b

(<*>)
  :: Applicative f

  -- Given an action that produces a function from ‘a’ to ‘b’…
  => f (a -> b)

  -- And an action that produces an ‘a’…
  -> f a

  -- Make an action that produces a ‘b’.
  -> f b

这些可以像这样组合：

(++) <$> goo xs ys :: IO ([String] -> [String])
--                    f  (a        -> b)

hoo yss :: IO [String]
--         f a

hoo (xs:ys:yss) = (++) <$> goo xs ys <*> hoo yss :: IO [String]
--                                                  f  b

也就是说，对using(++)结果的fmapping是一个返回部分应用函数的动作，并产生一个将该函数应用于.goo xs ys<$><*>hoo yss

（有一条定律规定这f <$> x等价于pure f <*> x——也就是说，如果你有一个pure f只返回一个函数的动作f，解开该动作并将其应用于xusing的结果<*>，那么这与仅将纯函数应用于行动<$>。）

将其与 3 个参数的函数一起使用的另一个示例：

cat3 a b c = a ++ b ++ c

main = do
  -- Concatenate 3 lines of input
  result <- cat3 <$> getLine <*> getLine <*> getLine
  putStrLn result

您可以将所有这些组合器视为不同类型的应用程序运算符，例如($)：

 ($)  ::   (a ->   b) ->   a ->   b
(<$>) ::   (a ->   b) -> f a -> f b
(<*>) :: f (a ->   b) -> f a -> f b
(=<<) ::   (a -> f b) -> f a -> f b
  • ($)将纯函数应用于纯参数
  • (<$>)将纯函数应用于动作的结果
  • (<*>)将一个动作产生的纯函数应用于另一个动作的结果
  • (=<<)（的翻转版本）将返回动作的(>>=)函数应用于动作的结果
于 2018-06-26T21:54:20.917 回答