Есть ли в Haskell "цепочечная" функция монады?

Объясните "дубликат"

Кто-то указывает на Это случай для foldM? как возможный дубликат. Теперь у меня есть сильное мнение, что два вопроса, на которые можно ответить одинаковыми ответами, не обязательно дублируются! "Что такое 1 - 2" и "Что такое я ^ 2", оба дают "-1", но нет, это не повторяющиеся вопросы. Мой вопрос (который уже ответил, вроде) касался "существует ли функция iterateM в стандартной библиотеке Haskell", а не "Как реализовать прикованное действие монады".

Вопрос

Когда я пишу некоторые проекты, я обнаружил, что писал этот комбинатор:

repeatM :: Monad m => Int -> (a -> m a) -> a -> m a
repeatM 0 _ a = return a
repeatM n f a = (repeatM (n-1) f) =<< f a

Он просто выполняет монадическое действие n раз, подавая предыдущий результат в следующее действие. Я пробовал поиск hoogle и некоторые поисковые запросы Google, и не нашел ничего, что поставляется с "стандартным" Haskell. Существует ли такая формальная функция, которая предопределена?

Ответ 1

Вы можете использовать foldM, например:

import Control.Monad

f a = do print a; return (a+2)

repeatM n f a0 = foldM (\a _ -> f a) a0 [1..n]

test = repeatM 5 f 3
  -- output: 3 5 7 9 11

Ответ 2

Carsten упомянул replicate, и это не плохая мысль.

import Control.Monad
repeatM n f = foldr (>=>) pure (replicate n f)

Идея заключается в том, что для любой монады m функции типа a -> m b образуют категорию Клейсли m, с тождественными стрелками

pure :: a -> m a

(также называемый return)

и оператор композиции

(<=<) :: (b -> m c) -> (a -> m b) -> a -> m c
f <=< g = \a -> f =<< g a

Поскольку мы действительно имели дело с функцией типа a -> m a, мы действительно смотрим на один моноид категории Kleisli, поэтому мы можем думать о сворачивающихся списках этих стрелок.

Что делает вышеприведенный код, сбрасывает оператор композиции, перевернутый в список n копий f, заканчивая идентификатором, как обычно. Перевертывание оператора композиции фактически превращает нас в двойную категорию; для многих обычных монад, x >=> y >=> z >=> w более эффективен, чем w <=< z <=< y <=< x; так как все стрелки в этом случае одинаковы, похоже, мы тоже. Обратите внимание, что для ленивой монады и, вероятно, также монады-читателя, может быть лучше использовать оператор unflipped <=<; >=> обычно лучше для IO, ST s и обычного строгого состояния.

Примечание: я не теоретик категории, поэтому могут быть ошибки в объяснении выше.

Ответ 3

Я часто нахожу, что хочу эту функцию, я бы хотел, чтобы у нее было стандартное имя. Это имя, однако, не было бы repeatM - это было бы для бесконечного повтора, например, forever, если бы оно существовало, просто для согласованности с другими библиотеками (и repeatM определяется в некоторых библиотеках таким образом).

Как еще одна перспектива из уже полученных ответов, я указываю, что (s -> m s) выглядит немного как действие в государственной монаде с типом состояния s.

На самом деле он изоморфен StateT s m () - действию, которое не возвращает никакого значения, потому что вся работа, которую он делает, инкапсулируется в том, как она изменяет состояние. В этой монаде вам действительно нужна функция replicateM. Вы можете написать это так в haskell, хотя это, вероятно, выглядит уродливее, чем просто написать его напрямую.

Сначала преобразуйте s -> m s в эквивалентную форму, которую использует StateT, добавляя () без использования информации, используя liftM для сопоставления функции над возвращаемым типом.

> :t \f -> liftM (\x -> ((),x)) . f
\f -> liftM (\x -> ((),x)) . f :: Monad m => (a -> m t) -> a -> m ((), t)

(возможно, он использовал fmap, но ограничение Monad кажется более ясным здесь, возможно, использовало бы TupleSections, если вам нравится, если вы заметите, что обозначение легче читать, это просто \f s -> do x <- f s; return ((),s)).

Теперь это правильный тип для завершения с помощью StateT:

> :t StateT . \f -> liftM (\x -> ((),x)) . f
StateT . \f -> liftM (\x -> ((),x)) . f :: Monad m => (s -> m s) -> StateT s m ()

а затем вы можете реплицировать его n раз, используя версию replicateM_, потому что возвращенный список [()] из replicateM не будет интересен:

> :t \n -> replicateM_ n . StateT . \f -> liftM (\x -> ((),x)) . f
\n -> replicateM_ n . StateT . \f -> liftM (\x -> ((),x)) . f :: Monad m => Int -> (s -> m s) -> StateT s m ()

и, наконец, вы можете использовать execStateT, чтобы вернуться к Monad, изначально работавшей в:

runNTimes :: Monad m => Int -> (s -> m s) -> s -> m s
runNTimes n act =
  execStateT . replicateM_ n . StateT . (\f -> liftM (\x -> ((),x)) . f) $ act