Работа бесконечных списков со строгими монадами

Question

У меня есть функция f :: [a] -> b, которая работает с бесконечными списками (например, take 5, takeWhile (< 100) . scanl (+) 0 и т. Д.). Я хочу передать эту функцию значениям, генерируемым строгими монадическими действиями (например, randomIO).

С this question, я узнал, что трюк подход repeat и sequence не работает для жестких монад, как пример ниже шоу:

import Control.Monad.Identity 

take 5 <$> sequence (repeat $ return 1) :: Identity [Int] 
-- returns `Identity [1,1,1,1,1]` 
-- works because Identity is non-strict 

take 5 <$> sequence (repeat $ return 1) :: IO [Int] 
-- returns `*** Exception: stack overflow` 
-- does not work because IO is strict 

Таким образом, вместо этого, я думал об использовании функции «внутри «монадический контекст. Я был вдохновлен этой circular programming example и попробовал:

let loop = do 
     x <- return 1 
     (_, xs) <- loop 
     return (take 5 xs, x:xs) 
in fst loop :: Identity [Int] 
-- Overflows the stack 

и

import Control.Monad.Fix 

fst <$> mfix (\(_, xs) -> do 
    x <- return 1 
    return (take 5 xs, x:xs)) :: Identity [Int] 
-- Overflows the stack 

и даже

{-# LANGUAGE RecursiveDo #-} 
import System.Random 

loop' = mdo 
    (xs', xs) <- loop xs 
    return xs' 
where loop xs = do 
     x <- randomIO 
     return (take 5 xs, x:xs) 

print $ loop' 
-- Returns a list of 5 identical values 

Но ни одна из этих работ. Я также попытался Conduit подход, который не работал ни даже в Identity случае:

import Conduit 

runConduitPure $ yieldMany [1..] .| sinkList >>= return . take 5 

Поэтому я хотел бы знать:

1. Почему никто из «круговой» не подходит выше работы?

2. Если существует решение, которое не включает unsafeInterleaveIO. (возможно iteratee s, Arrow ы?)

Answer 1

Я использую randomIO здесь только для простоты примеров. На практике, я хотел бы обрабатывать сообщения, полученные с помощью сокетов

Это невозможно без unsafeInterleaveIO. Проблема в конце дня заключается в том, что действия IO должны быть упорядочены. Хотя порядок оценки ссылочно прозрачных значений не имеет значения, действия IO могут быть выполнены. Если вам нужен ленивый бесконечный список всех сообщений, полученных по сокету, вы должны сообщить Haskell априори, где в последовательности IO действий это подходит (если вы не используете unsafeInterleaveIO).

Arrow абстракции вы ищете называется ArrowLoop, но он тоже имеет проблемы с право ужесточением закона для строгих монад.

На первый взгляд, это может выглядеть как (проявляется через mdo или mfix) является решением тоже, но копать немного глубже shows that fixIO has problems, как loop от ArrowLoop.

Однако иногда ограничение на то, что действия IO должны выполняться один за другим, немного чрезмерно, и это то, что для unsafeInterleaveIO.Цитируя docs

unsafeInterleaveIO позволяет IO вычисление быть отложено лениво. Когда передано значение типа IO a, IO будет выполняться только тогда, когда требуется значение a.

---

Теперь, даже если вы явно сказали, что вы не хотите unsafeInterleaveIO решение, как я надеюсь, удалось убедить вас, что это путь, вот это:

interweavingRepeatM :: IO a -> IO [a] 
interweavingRepeatM action = unsafeInterleaveIO ((:) <$> action <*> interweavingRepeatM action) 

И здесь работает для случайных чисел:

ghci> import System.Random 
ghci> sourceOfRandomness <- interweavingRepeatM randomIO :: IO [Integer] 
ghci> take 10 sourceOfRandomness 
[-2002742716261662204,7803971943047671004,-8395318556488893887,-7372674153585794391,5906750628663631621,6428130029392850107,6453903217221537923,-8966011929671667536,6419977320189968675,-1842456468700051776] 

Answer 2

Alec's answer охватывает у наш общий вопрос. Ниже приводится конкретно о кабелепровод и аналогичные потоковые библиотеки.

Я также попытался Conduit подход, который не работал ни даже в случае Identity:

import Conduit 

runConduitPure $ yieldMany [1..] .| sinkList >>= return . take 5 

Хотя потоковые библиотеки обычно используются, чтобы избежать рода трудности вы упоминаете (сравни вступительные замечания Pipes.Tutorial), предполагается, что вы будете использовать их типы потоков вместо списков. Рассмотрим, например, как sinkList описывается в документации Conduit:

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

Это означает, что с помощью sinkMany сразу после yieldMany возвращает вас на круги свои: Собирают все значения в память именно то, что делает сочетание sequence, IO и бесконечные списки непригодных. Вместо этого вы должны использовать инфраструктуру потоковой библиотеки для построения этапов вашего конвейера. Вот несколько простых примеров использования в основном готовые вещей из трубопровода и трубопроводных-комбинаторы:

GHCi> import Conduit 
GHCi> runConduitPure $ yieldMany [1..] .| takeC 5 .| sinkList 
[1,2,3,4,5] 
GHCi> runConduit $ yieldMany [1..] .| takeC 5 .| printC -- try it without takeC 
1 
2 
3 
4 
5 
GHCi> runConduit $ yieldMany [1..] .| takeC 5 .| scanlC (+) 0 .| printC 
0 
1 
3 
6 
10 
15 
GHCi> :{ 
GHCi| runConduit $ yieldMany [1..] .| takeC 5 
GHCi|  .| awaitForever (\x -> liftIO (print (2*x)) >> yield x) 
GHCi|  .| printC 
GHCi| :} 
2 
1 
4 
2 
6 
3 
8 
4 
10 
5 
GHCi> runConduit $ (sourceRandom :: Producer IO Int) .| takeC 5 .| printC 
1652736016140975126 
5518223062916052424 
-1236337270682979278 
8079753510915129274 
-609160753105692151 

(спасибо Michael заставили меня заметить sourceRandom - сначала я закатилась моим с repeatMC randomIO.)