Является ли Haskell mapM не ленивым?

Ответ 1

Ну, там лениво, а потом там лениво. mapM действительно ленив в том, что он не делает больше работы, чем нужно. Однако посмотрите на подпись типа:

mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]

Подумайте, что это значит: вы даете ему функцию a -> m b и связку a s. Обычный map может превратить их в группу m b s, но не m [b]. Единственный способ объединить b в один [b], не вмешиваясь в монаду, - это использовать >>= для последовательности m b для построения списка.

Фактически, mapM точно эквивалентен sequence . map.

В общем случае для любого монадического выражения, если значение используется вообще, вся цепочка >>=, приводящая к выражению, должна быть принудительной, поэтому применение sequence к бесконечному списку не может быть завершено.

Если вы хотите работать с неограниченной монадической последовательностью, вам потребуется либо явное управление потоком - например, условие завершения цикла, испеченное в цепочке привязок, так как простые рекурсивные функции, такие как mapM и sequence не предоставляйте - или пошаговую последовательность, что-то вроде этого:

data Stream m a = Nil | Stream a (m (Stream m a))

... так что вы только усиливаете столько слоев монады, сколько необходимо.

Изменить:: Что касается splitRandom, то происходит то, что вы передаете ему вычисление Rand, оценивая это с помощью семени splitRandom, затем return ing результат. Без splitRandom семя, используемое одиночным getRandom, должно исходить из конечного результата секвенирования бесконечного списка, поэтому он зависает. С дополнительным splitRandom, используемое семя только нужно пропустить хотя бы два вызова splitRandom, поэтому он работает. Окончательный список случайных чисел работает, потому что вы оставили монаду Rand в этой точке и ничего не зависит от ее конечного состояния.

Ответ 2

Здесь попытка доказательства того, что mapM return [1..] не заканчивается. Предположим, что мы находимся в монаде Identity (аргумент применим и к любой другой монаде):

mapM return [1..] -- initial expression
sequence (map return [1 ..]) -- unfold mapM
let k m m' = m >>= \x ->
             m' >>= \xs ->
             return (x : xs)
in foldr k (return []) (map return [1..]) -- unfold sequence

До сих пор так хорошо...

-- unfold foldr
let k m m' = m >>= \x ->
             m' >>= \xs ->
             return (x : xs)
    go [] = return []
    go (y:ys) = k y (go ys)
in go (map return [1..])

-- unfold map so we have enough of a list to pattern-match go:
go (return 1 : map return [2..])
-- unfold go:
k (return 1) (go (map return [2..])
-- unfold k:
(return 1) >>= \x -> go (map return [2..]) >>= \xs -> return (x:xs)

Вспомним, что return a = Identity a в монадии Identity и (Identity a) >>= f = f a в монаде Identity. Продолжение:

-- unfold >>= :
(\x -> go (map return [2..]) >>= \xs -> return (x:xs)) 1
-- apply 1 to \x -> ... :
go (map return [2..]) >>= \xs -> return (1:xs)
-- unfold >>= :
(\xs -> return (1:xs)) (go (map return [2..]))

Обратите внимание, что в этот момент мы хотели бы применить к \xs, но мы пока не можем! Мы должны продолжать разворачиваться, пока не получим значение:

-- unfold map for go:
(\xs -> return (1:xs)) (go (return 2 : map return [3..]))
-- unfold go:
(\xs -> return (1:xs)) (k (return 2) (go (map return [3..])))
-- unfold k:
(\xs -> return (1:xs)) ((return 2) >>= \x2 ->
                         (go (map return [3..])) >>= \xs2 ->
                         return (x2:xs2))
-- unfold >>= :
(\xs -> return (1:xs)) ((\x2 -> (go (map return [3...])) >>= \xs2 ->
                        return (x2:xs2)) 2)

В этот момент мы по-прежнему не можем применяться к \xs, но мы можем применить к \x2. Продолжение:

-- apply 2 to \x2 :
(\xs -> return (1:xs)) ((go (map return [3...])) >>= \xs2 ->
                         return (2:xs2))
-- unfold >>= :
(\xs -> return (1:xs)) (\xs2 -> return (2:xs2)) (go (map return [3..]))

Теперь мы достигли точки, где ни \xs, ни \xs2 еще не могут быть уменьшены! Наш единственный выбор:

-- unfold map for go, and so on...
(\xs -> return (1:xs))
  (\xs2 -> return (2:xs2))
    (go ((return 3) : (map return [4..])))

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

Это имеет смысл, если вы посмотрите на этот пример (заимствованный из другого потока StackOverflow, я не могу найти его в данный момент). В следующем списке монадов:

mebs = [Just 3, Just 4, Nothing]

мы ожидаем, что sequence поймает Nothing и вернет сбой для всего:

sequence mebs = Nothing

Однако для этого списка:

mebs2 = [Just 3, Just 4]

мы ожидаем, что последовательность даст нам:

sequence mebs = Just [3, 4]

Другими словами, sequence должен видеть весь список монадических вычислений, объединять их вместе и запускать их все, чтобы придумать правильный ответ. Нет способа sequence дать ответ, не видя весь список.

Примечание. В предыдущей версии этого ответа утверждается, что foldr вычисляет начало с обратной стороны списка и не будет работать вообще в бесконечных списках, но это неверно! Если оператор, который вы переходите на foldr, ленив по второму аргументу и производит вывод с ленивым конструктором данных, подобным списку, foldr будет работать с бесконечным списком. См. foldr (\x xs -> (replicate x x) ++ xs) [] [1...] для примера. Но это не так с нашим оператором k.

Ответ 3

Хорошо, этот вопрос становится потенциально очень простым.

q < - mapM return [1..]

Почему это никогда не возвращается?

Это не обязательно верно. Это зависит от монады, в которой вы находитесь.

Например, с монодатой с идентификатором вы можете использовать результат лениво и прекратить выполнение:

newtype Identity a = Identity a

instance Monad Identity where
  Identity x >>= k = k x
  return = Identity

-- "foo" is the infinite list of all the positive integers
foo :: [Integer]
Identity foo = do
  q <- mapM return [1..]
  return q

main :: IO ()
main = print $ take 20 foo -- [1 .. 20]

Ответ 4

Этот вопрос очень хорошо показывает разницу между IO Monad и другими Монадами. В фоновом режиме mapM создает выражение с операцией bind ( → =) между всеми элементами списка, чтобы превратить список монадических выражений в монадическое выражение списка. Теперь, что отличается в монаде IO, заключается в том, что модель исполнения Haskell выполняет выражения во время связывания в IO Monad. Это именно то, что окончательно заставляет (в чисто ленивом мире) что-то исполнять вообще.

Итак, IO Monad особенным образом, он использует парадигму последовательности привязки для фактического принудительного выполнения каждого шага, и это то, что наша программа делает, чтобы что-то выполнить в конце концов. Другие Монады разные. Они имеют другие значения оператора привязки, в зависимости от Монады. IO на самом деле является одной Monad, которая выполняет вещи в bind, и именно поэтому типы IO являются "действиями".

В следующем примере показано, что другие Monads не применяют исполнение, например, монаду Maybe. Наконец, это привело к тому, что mapM в IO Monad возвращает выражение, которое при выполнении - выполняет каждый отдельный элемент перед возвратом конечного значения.

Есть хорошие статьи об этом, начните здесь или найдите денотационную семантику и монады: Борьба с неуклюжей командой: http://research.microsoft.com/en-us/um/people/simonpj/papers/marktoberdorf/mark.pdf

Пример с Maybe Monad:

где

fstMaybe:: [Int] → Возможно [Int] fstMaybe = mapM (\ x → если x == 3, то Nothing else Just x)

main = do    пусть r = fstMaybe [1..]    return r

Ответ 5

Расскажите об этом в более общем контексте.

Как говорят другие ответы, mapM представляет собой комбинацию sequence и map. Поэтому проблема заключается в том, что sequence является строгим в определенных Monad s. Однако это не ограничивается Monads, но также Applicative, поскольку мы имеем sequenceA, которые в большинстве случаев используют одну и ту же реализацию sequence.

Теперь просмотрите подпись типа (специализированный для списков) sequenceA:

sequenceA :: Applicative f => [f a] -> f [a]

Как вы это сделаете? Вам был предоставлен список, поэтому вы хотели бы использовать foldr в этом списке.

sequenceA = foldr f b where ...
  --f :: f a -> f [a] -> f [a]
  --b :: f [a]

Так как f является Applicative, вы знаете, что b coule be - pure []. Но что такое f? Очевидно, что это поднятая версия (:):

(:) :: a -> [a] -> [a]

Итак, теперь мы знаем, как работает sequenceA:

sequenceA = foldr f b where
  f a b = (:) <$> a <*> b
  b = pure []

или

sequenceA = foldr ((<*>) . fmap (:)) (pure [])

Предположим, вам дали ленивый список (x:_|_). Вышеприведенное определение sequenceA дает

sequenceA (x:_|_) === (:) <$> x <*> foldr ((<*>) . fmap (:)) (pure []) _|_
                  === (:) <$> x <*> _|_

Итак, теперь мы видим, что проблема была уменьшена, чтобы считать, что погода f <*> _|_ равна _|_ или нет. Очевидно, если f строго, это _|_, но если f не является строгим, чтобы позволить остановку оценки, нам нужно <*> быть нестрогим.

Таким образом, критерии для аппликативного функтора, чтобы он остановился на sequenceA, будет оператор <*> должен быть нестрогим. Простым тестом будет

const a <$> _|_ === _|_      ====> strict sequenceA
-- remember f <$> a === pure f <*> a

Если мы говорим о Moand s, критерии

_|_ >> const a === _|_ ===> strict sequence