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

Question

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

Из этого вопроса я узнал, что 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

Вместо этого я подумал об использовании функции "внутри" монадического контекста. Я был вдохновлен этим примером кругового программирования и попробовал:

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, (может быть iteratees, Arrows?)

Answer 1

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

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

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

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

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

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

Ответ Алек охватывает ваш общий вопрос. Далее следует конкретно о канале и аналогичных потоковых библиотеках.

Я также попробовал 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.)