Выполнение рекурсии внутри монады

Question

Я пытался выяснить, как сделать рекурсию в монаде IO.Я знаком с выполнением рекурсии с использованием чистых функций, но не смог передать эти знания монадам ввода-вывода.

Рекурсия с чистыми функциями
Мне удобно делать рекурсию с чистыми функциями, такими как приведенная ниже функция 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 

Попытка получить рекурсию внутри монады ввода-вывода
Когда я пытаюсь выполнить рекурсию внутри монады ввода-вывода (например, "основной" функции), я не могу.Я посмотрел liftM, replicateM и оператор или функцию отмены ввода-вывода <-.Я хочу монаду ввода-вывода, такую ​​как 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 обозначение очень удобно.Используй это, это твой друг.Нам просто нужно следовать его правилам, если каждая вещь, идущая на свое место, должна иметь правильный тип, соответственно.

Вы были очень близки:

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.Вот и все.(Некоторые дополнительные объяснения, например, здесь ).

Что касается рекурсии, она достигается с помощью нотации do так же, как это достигается в чистом коде: путем именования вещей и обращения кто же имя внутри выражения, определяющего это имя, будь то чистое выражение или запись do.

Рекурсия - это прыжок веры.Нам все равно, как вещь определена - мы предполагаем, что она определена правильно, поэтому мы можем просто обратиться к ней по ее имени.Пока типы подходят.

Answer 2

Чтобы сделать это с нотацией do, вам необходимо связать результаты каждого действия IO, чтобы использовать эти результаты в чистых выражениях, таких как let rs =… ++…,например, так:

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

То есть fmapping (++) поверх результата goo xs ys с использованием <$> - это действие, которое возвращает частично примененную функцию, а <*> создает действие, которое применяетсяэта функция к результату hoo yss.

(Существует закон, который гласит, что f <$> x эквивалентно pure f <*> x, то есть если у вас есть действие pure f, которое просто возвращает функциюf, разверните это действие и примените его к результату x, используя <*>, тогда это то же самое, что просто применить чистую функцию к действию с <$>.)

Другой примериспользуя это с функцией из 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

• ($) применяет функцию pure к pure аргумент
• (<$>) применяет функцию pure к результату действия
• (<*>) применяет pure function , являющаяся результатом из действия к результату другого action
• (=<<) (перевернутая версия (>>=)) применяет функцию возвращая действие к результату действие

Answer 3

Если вы обнаружите, что запись do сбивает с толку, я бы порекомендовал не использовать ее вообще.С помощью >>= вы можете делать все, что вам нужно.Просто представьте, что его тип

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

Тем не менее, давайте посмотрим на ваш код.

let в блоке do дает имя некоторому значению.Это то же самое, что и за пределами do, поэтому здесь это бесполезно (это не дает вам дополнительных возможностей).

<- более интересно: оно действует как «извлечение значения из IO локально»."construct (если вы немного щуритесь).

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 -> ...)

Если вы посмотрите на сигнатуру >>=, роль a играет [String] здесь (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

Теперь она проверяет:), большинство паренсов здесь на самом деле необязательны:

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)