Data.Vector.Stream обеспечивает хорошую реализацию Stream, которая очень эффективна благодаря фокусированию на плавкость (подробнее см. в этой статье ). Поскольку vector-0.1 эта реализация Stream немного изменилась, переместив тип Step в монаду. (Теперь реализация находится в Data.Vector.Fusion.Stream.Monadic.)
В двух словах, вот определение Stream:
data Step s a where
Yield :: a -> s -> Step s a
Skip :: s -> Step s a
Done :: Step s a
data Stream a = forall s. Stream (s -> Step s a) s
Step s a инкапсулирует три возможных результата из одной итерации состояния s с функцией обновления s -> Step s a. Поток либо Done, либо пропускает вывод, либо выдает вывод. (В приведенном выше определении используются GADT, но здесь это не имеет значения.)
Простые приложения этого Stream:
empty :: Stream a
empty = Stream (const Done) ()
singleton :: a -> Stream a
singleton x = Stream step True where
step True = Yield x False
step False = Done
fromList :: [a] -> Stream a
fromList zs = Stream step zs
where
step (x:xs) = Yield x xs
step [] = Done
Строгий левый сгиб делается так:
foldl'S :: (a -> b -> a) -> a -> Stream b -> a
foldl'S f a0 (Stream step s) = go a0 s where
go a s = a `seq`
case step s of
Yield b s' -> go (f a b) s'
Skip s' -> go a s'
Done -> a
и это дает обычные функции, подобные списку lengthS = foldl'S (\n _ -> n+1) 0 и т. Д. Это, конечно, не так элегантно, как Conduit или Pipes, но это просто и быстро. Пока все хорошо.
Теперь давайте попробуем объединить потоки «низкого уровня» в потоки более высокого уровня. Например, если у вас есть поток битов Stream Bool, вы можете декодировать биты, чтобы получить Stream Int, используя какой-нибудь умный кодек. Конечно, всегда можно создать новую пошаговую функцию s -> Step s b из функции step, извлеченной из данной Stream step s. Повторные применения функции step :: s->Step s a приводят к неуклюжим каскадам case (step s) of ..., которые снова и снова обрабатывают три возможности Done, Skip, Yield. В идеале aggregate должно выглядеть так:
aggregate :: Stream a -> M?? -> Stream b
newStream = aggregate oldStream $ do
a1 <- get -- a1 :: a
if a1 == True then doSomething
else do
a2 <- get
-- etc.
M?? - это некоторая монада, которую нужно определить. Давайте попробуем тип Appl s a:
newtype Appl s a = Appl ((s->Step s a) -> s -> Step s a)
Он называется Appl, потому что имеет подпись приложения-функции. Экземпляр монады довольно прост:
instance Monad (Appl s) where
return a = Appl (\_ s -> Yield a s)
(Appl ap) >>= f = Appl (\step s ->
case (ap step s) of
Done -> Done
Skip s' -> untilNotSkip step s'
Yield a' s' -> ap' step s' where Appl ap' = f a'
, где untilNotSkip :: (s->Step s a) -> s -> Step s a - это просто повторное (вложенное) применение step :: (s->Step s a) до тех пор, пока не будет возвращено Done или Yield.
Функция get - это обычное применение функции
get :: Appl s a
get = Appl(\step s -> step s)
Чтобы связать вещи, нужно сделать Functor и Applicative, и тут возникает проблема: Appl s нельзя сделать функтором. Подпись
fmap :: (a->b) -> Appl s a -> Appl s b
и это просто не работает, потому что для создания функции (s->Step s b) -> s -> Step s b) из функции (s->Step s a) -> s -> Step s a) мне понадобится b->a. Я могу оттянуть Appl s b над a->b, но я не могу выдвинуть Appl s a - то есть у меня может быть контравариантный функтор, но не функтор. Это странно. Потоки вполне естественны , но я не вижу связи. цель Appl - превратить шаговую функцию s->Step s a в другую s->Step s b.
Здесь что-то не так, Appl не так "M??". Кто-нибудь может помочь?
Обновление
Как указал Ли-яо Ся, тип должен быть примерно таким:
data Walk a b = forall s. Walk ((s->Step s a) -> s -> Step s b)
И экземпляры Functor, Applicative и Monad будут иметь значение
instance Functor (Step s) where
fmap f Done = Done
fmap f (Skip s) = Skip s
fmap f (Yield a s) = Yield (f a) s
instance Functor (Walk a) where
fmap f (Walk t) = Walk ( \step s -> fmap f (t step s) )
-- default Applicative given a monad instance
ap :: (Monad m) => m (a -> b) -> m a -> m b
ap mf m = do
f <- mf
x <- m
return (f x)
untilNotSkip :: (s->Step s a) -> s -> Step s a
untilNotSkip step s = case step s of
Done -> Done
Skip s' -> untilNotSkip step s'
Yield a' s' -> Yield a' s'
instance Monad (Walk a) where
return a = Walk (\_ s -> Yield a s)
Walk t >>= f =
Walk (\step s -> case t (untilNotSkip step) s of
Done -> Done
Skip _ -> error "Internal error."
Yield b' s' -> case f b' of Walk t' -> t' step s' -- bad
)
instance Applicative (Walk a) where
pure = return
(<*>) = ap
Однако средство проверки типов не разрешит этот экземпляр монады. В определении >>= s в Walk (\step s -> ... отличается от s' в Yield b' s' -> ..., но оно должно быть таким же. Основная проблема здесь заключается в том, что (>>=) :: Walk a b -> (b->Walk a c) -> Walk a c имеет два независимо всех количественных состояния s, одно в первом аргументе и другое, которое возвращается b->Walk a c. Фактически это так (со злоупотреблением обозначениями)
(forall s. Walk s a b) -> (forall s'. b->Walk s' a' c) -> (forall s''. Walk s'' a c), что не имеет смысла ни концептуально, ни для проверки типов. Все три s, s', s'' должны быть одного типа.
Вариант, в котором Walk не является полностью количественным значением за s:
data Walk s a b = Walk ((s->Step s a) -> s -> Step s b)
разрешает правильное определение привязки, но тогда aggregate не будет работать:
-- does not compile
aggregate :: Stream a -> Walk s a b -> Stream b
aggregate (Stream step s) (M t) = Stream (t step) s
Опять же, состояние потока s всегда должно быть одинаковым. Одним из выходов из этого является введение data PreStream s a = PreStream (s -> Step s a) s, но это также не позволяет aggregate :: Stream a -> ?? -> Stream b.
Исходный код находится на github .