Как взять элементы в список, завернутый в монаду - PullRequest
Новая
       1

Как взять элементы в список, завернутый в монаду

4 голосов
/ 10 декабря 2010

У меня есть небольшая загадка, мне интересно, не могли бы вы помочь мне прояснить.

Давайте определим функцию, которая возвращает список: 

let f = replicate 3

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

takeWhile (< 3) $ concatMap f [1..]

Отлично! Это возвращает [1,1,1,2,2,2], что я и хочу.

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

let f' x = Just $ replicate 3 x

Для сопоставления и сопоставления я могу использовать: 

fmap concat $ mapM f' [1..5]

Возвращает: Just [1,1,1,2,2,2,3,3,3,4,4,4,5,5,5]

Если я хочу использовать takeWhile, это все еще работает: 

fmap (takeWhile (< 3) . concat) $ mapM f' [1..5]

Что возвращает: Просто [1,1,1,2,2,2]. Отлично!

Но, если я составлю список, по которому я сопоставлю бесконечный список, это не сделает то, что я ожидал: 

fmap (takeWhile (< 3) . concat) $ mapM f' [1..]

Похоже, что takeWhile никогда не происходит. Так или иначе, я не получаю ленивый расчет, который я ожидал. Я немного растерялся.

Ответы [ 3 ]

8 голосов
/ 10 декабря 2010

Проблема не в том, что fmap + takeWhile не работает с бесконечными списками, заключенными в монаду.Проблема в том, что mapM не может создать бесконечный список (по крайней мере, не в монаде Maybe).

Подумайте об этом: если f' возвращает Nothing для любого элемента в списке, mapM должен вернуть Nothing.Однако mapM не может знать, произойдет ли это, пока он не вызовет f' для всех элементов в списке.Поэтому ему нужно перебрать весь список, прежде чем он узнает, будет ли результат Nothing или Just.Очевидно, это проблема бесконечных списков.

5 голосов
/ 10 декабря 2010

Это должно сработать: 

takeWhileM :: (Monad m) => (a -> Bool) -> [m a] -> m [a]
takeWhileM p [] = return []
takeWhileM p (m:ms) = do 
    x <- m
    if p x
      then liftM (x:) (takeWhileM p ms) 
      else return []

См. Ответ sepp2k, чтобы объяснить, почему вы теряете лень.Например, монада Identity или непустой список не будут иметь этой проблемы.

4 голосов
/ 10 декабря 2010

Вы не можете отобразить M бесконечный список Maybes. mapM - карта, сопровождаемая последовательностью. Вот определение последовательности: 

sequence ms = foldr k (return []) ms
  where
    k m m' = do { x <- m; xs <- m'; return (x:xs) }

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

EDIT:

luqui и Carl подчеркивают, что это не обобщает ни одну монаду. Чтобы понять, почему это не работает, возможно, нам нужно взглянуть на реализацию (>> =): 

(>>=) m k = case m of
    Just x  -> k x
    Nothing -> Nothing

Важным моментом здесь является то, что мы делаем случай на m. Это делает m строгим, потому что мы должны оценить его, чтобы выяснить, как продолжить выполнение. Обратите внимание, что здесь мы не записываем x, поэтому он остается ленивым.

...