Порядок выполнения с помощью `mapM` в Haskell

Если вы оцените mapM print ["1", "2", "3"], расширив определение mapM, вы получите (игнорируя некоторые несущественные детали)

print "1" >> print "2" >> print "3"

Вы можете думать о print и >> как об абстрактных конструкторах операций ввода-вывода, которые не могут быть оценены дальше, так же как конструктор данных, такой как Just, не может быть оценен дальше.

Интерпретация print s — это действие печати s, а интерпретация a >> b — это действие, которое сначала выполняет a, а затем выполняет b. Итак, интерпретация

mapM print ["1", "2", "3"] = print "1" >> print "2" >> print "3"

заключается в том, чтобы сначала напечатать 1, затем напечатать 2 и, наконец, напечатать 3.

Как это на самом деле реализовано в GHC — это совершенно другой вопрос, о котором вам не следует беспокоиться в течение длительного времени.

Нет гарантии порядка оценки, но есть гарантия порядка эффектов. Для получения дополнительной информации см. этот ответ, в котором обсуждается forM.

Вам нужно научиться делать следующее сложное различие:

1. Порядок оценки
2. Порядок эффектов (также известных как «действия»)

Что forM, sequence и подобные функции обещают, так это то, что эффекты будут упорядочены слева направо. Так, например, следующее гарантирует печать символов в том же порядке, в котором они встречаются в строке...

Примечание: "forM это mapM с перевернутыми аргументами. Для версии, которая игнорирует результаты, см. forM_."

Предварительное примечание: ответы Рейда Бартона и Даира полностью верны и полностью охватывают ваши практические проблемы. Я упоминаю об этом, потому что на полпути к этому ответу может сложиться впечатление, что он противоречит им, что не так, как станет ясно к тому времени, когда мы дойдем до конца. Это ясно, пора заняться языковым адвокатированием.

Есть ли гарантия, что [mapM print] [напечатает элементы списка по порядку]?

Да, есть, как объясняют другие ответы. Здесь я буду обсуждать, что может оправдать эту гарантию.

В наши дни mapM по умолчанию просто traverse специализирована для монад:

traverse
  :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
mapM
  :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)

Если это так, то в дальнейшем я буду в первую очередь заниматься traverse и тем, как наши ожидания относительно последовательности эффектов соотносятся с классом Traversable.

Что касается производства эффектов, traverse генерирует эффект Applicative для каждого значения в пройденном контейнере и объединяет все такие эффекты через соответствующий экземпляр Applicative. Эта вторая часть четко отражена типом sequenceA, посредством которого аппликативный контекст, так сказать, выносится за пределы контейнера:

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)

-- sequenceA and traverse are interrelated by:
traverse f = sequenceA . fmap f
sequenceA = traverse id

Экземпляр Traversable для списков< /a>, например:

instance Traversable [] where
    {-# INLINE traverse #-} -- so that traverse can fuse
    traverse f = List.foldr cons_f (pure [])
      where cons_f x ys = (:) <$> f x <*> ys

GHCi> -- Superfluous parentheses added for emphasis.
GHCi> ((putStrLn "Type something:" >> return reverse) <*> getLine) >>= putStrLn
Type something:
Whatever
revetahW

(<*>), однако, эффекты последовательности слева направо по соглашению, а не по какой-либо внутренней причине. Согласно оболочке Backwards из преобразователей, в принципе всегда можно реализовать (<*>) с последовательностью справа налево и при этом получить допустимый экземпляр Applicative. Без использования оболочки также можно воспользоваться (<**>) из Control.Applicative для инвертирования последовательности:

(<**>) :: Applicative f => f a -> f (a -> b) -> f b

GHCi> import Control.Applicative
GHCi> (getLine <**> (putStrLn "Type something:" >> return reverse)) >>= putStrLn
Whatever
Type something:
revetahW

Учитывая, что так легко изменить последовательность эффектов Applicative, можно задаться вопросом, можно ли перенести этот трюк на Traversable. Например, допустим, мы реализуем...

esrevart :: Applicative f => (a -> f b) -> [a] -> f [b]

... так что это точно так же, как traverse для списков, за исключением использования Backwards или (<**>) для изменения последовательности эффектов (я оставлю это в качестве упражнения для читателя). Будет ли esrevart законной реализацией traverse? Хотя мы могли бы выяснить это, попытавшись доказать личность Traversable, что на самом деле не обязательно: учитывая, что Backwards f для любого аппликативного f также является аппликативным, esrevart по образцу любого законного traverse также будет следовать законам Traversable. Обертка Reverse, также часть transformers, предлагает общую реализацию этого обращения.

Таким образом, мы пришли к выводу, что могут быть Traversable законные случаи, отличающиеся последовательностью эффектов. В частности, возможен список traverse, в котором эффекты упорядочиваются от хвоста к началу. Однако это не делает возможность менее странной. Чтобы избежать полного замешательства, экземпляры Traversable обычно реализуются с помощью простого (<*>) и следуют естественному порядку, в котором конструкторы используются для построения проходимого контейнера, что в случае списков составляет ожидаемую последовательность эффектов от начала до конца. Одно из мест, где проявляется это соглашение, — автоматическое создание экземпляров с помощью расширение DeriveTraversable.

Последняя, ​​историческая справка. Обсуждать эту дискуссию, которая в конечном счете касается mapM, с точки зрения класса Traversable было бы шагом сомнительного значения в недалеком прошлом. mapM был фактически включен в состав traverse только в прошлом году, но просуществовал гораздо дольше. Например, Отчет Haskell 1.3 от 1996 года, за годы до появления Applicative и Traversable (не на самом деле там даже ap), предоставляет следующую спецификацию для mapM:

accumulate        :: Monad m => [m a] -> m [a]
accumulate        =  foldr mcons (return [])
                     where mcons p q = p >>= \x -> q >>= \y -> return (x:y)

mapM              :: Monad m => (a -> m b) -> [a] -> m [b]
mapM f as         =  accumulate (map f as)

Последовательность эффектов, реализованная здесь с помощью (>>=), идет слева направо только по той причине, что это разумно.

PS: Стоит подчеркнуть, что, хотя и возможно написать mapM справа налево с точки зрения операций Monad (например, в приведенной здесь реализации Отчета 1.3 требуется просто поменять местами p и q в правой- стороны mcons), не существует такой вещи, как общее Backwards для монад. Поскольку f в x >>= f является функцией Monad m => a -> m b, которая создает эффекты из значений, эффекты, связанные с f, зависят от x. Как следствие, простая инверсия последовательности, подобная возможной с (<*>), даже не гарантируется осмысленностью, не говоря уже о законности.