Порядок исполнения с Haskell в `mapM`

Question

Рассмотрим следующий Haskell заявление:

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

Действительно, это печатает "1", "2" и "3", в порядке.

Вопрос: Как вы знаете, что mapM будет первый печать "1", а затем печать "2", и, наконец, печать "3". Есть ли какая-то гарантия, что он это сделает? Или это совпадение того, как оно осуществляется глубоко внутри GHC?

Answer 1

Если оценивать 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 совершенно другой вопрос, который вы не должны беспокоиться о долгое время.

Answer 2

Гарантия не распространяется на порядок оценки, но есть гарантия на порядок эффектов. Для получения дополнительной информации см this answer that discusses forM.

Вы должны научиться делать следующее, каверзный различие:

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

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

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

Answer 3

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

Есть ли какая-либо гарантия, что [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 

The Traversable instance for lists, например, является:

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 

Очевидно, что объединение и, следовательно, последовательность действий происходит через (<*>), поэтому давайте сосредоточимся на нем на мгновение. Выбор в IO аппликативный функторе в качестве иллюстративного примера, мы можем видеть (<*>) секвенирования эффектов слева направо:

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

(<*>), однако, последовательности эффектов слева направо by convention, and not for any inherent reason. Как видно из the Backwards wrapper from transformers, в принципе всегда можно реализовать (<*>) с секвенированием справа налево и получить законный экземпляр 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? Хотя мы могли бы это выяснить, пытаясь доказать, что это удержание identity and composition laws of Traversable, это на самом деле не является необходимым: учитывая, что Backwards f применительно к любому применению f также применимо, код esrevart с рисунком после любого законного traverse также будет следовать законам Traversable.The Reverse wrapper, также часть трансформаторов, предлагает общую реализацию этого разворота.

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

Последнее, историческое примечание. Смысл этого обсуждения, который в конечном счете составляет около mapM, в плане класса Traversable был бы поворотным сомнением в недалеком прошлом. mapM был фактически включен в число traverse только в прошлом году, но он существовал гораздо дольше. Например, Haskell Report 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 операций (в реализации Report 1.3 цитируемых здесь, к примеру, он просто требует обмен p и q в правой части от mcons), для монад не существует общей вещи Backwards. Начиная с f в x >>= f функция Monad m => a -> m b, которая создает эффекты от значений, эффекты, связанные с f, зависят от x. Как следствие, простая инверсия последовательности, подобная той, которая возможна с (<*>), даже не гарантируется, что она имеет смысл, не говоря уже о законности.