Stream, чтобы быть экземпляром traversable

Пакет vector-0.1 имеет довольно эффективную реализацию Stream (Data.Vector.Stream< /а>):

data Step s a = Yield a s
              | Skip    s
              | Done

-- | The type of fusible streams
data Stream a = forall s. Stream (s -> Step s a) s Size

Более поздние версии vector расширили это до монадической версии Data.Vector.Fusion.Stream.Monadic, но для простоты воспользуемся старым, не монадическим.

Stream вполне естественно является экземпляром Functor и Foldable:

instance Foldable Stream where
    foldMap f s = foldl' (\a b -> a <> (f b)) mempty s

В качестве потока он также должен быть экземпляром Traversable , не так ли? По крайней мере, на первый взгляд кажется, что это легко. Нам нужно

sequenceA :: Applicative f => Stream (f a) -> f (Stream a)

который начнется как

sequenceA (Stream step s) = Stream <$> step' <*> (pure s) where
    step' = ...

<*> — единственный способ «вытащить» аппликатив f из-под Stream. Теперь step' должно быть

step' :: f (s -> Step s a)

и у нас есть в наличии

step :: s -> Step s (f a)

Все, что я знаю, это то, что f — это Applicative (и Functor). Но <*> "притягивает" f (<*> :: f(a->b)->(f a->f b)), а здесь мне нужно прямо противоположное, так сказать со-<*>.

Наличие экземпляра Traversable не имеет решающего значения ни в одном из моих начинаний, и с точки зрения производительности это может быть даже нецелесообразно. Но меня беспокоит то, что я действительно не понимаю, почему Stream не будет Traversable. Какой структурный элемент отсутствует, чтобы сделать Stream Traversable?


stream haskell applicative traversable
person mcmayer    schedule 11.07.2018    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Это Traversable, но не очень интересным образом. Поскольку он допускает fromList, а также toList, у нас есть

sequenceA = fmap fromList . sequenceA . toList

Вы не можете сделать ничего более интересного: у вас есть Stream (f a), и вместо этого вы хотите создать f (Stream a). Поскольку ваш поток изоморфен списку, чтобы вывести эффекты из f на внешний уровень, вы должны пройтись по каждому элементу в вашем потоке, включая эффекты каждого из них, и, наконец, реконструировать поток, повторяющий объекты, встроенные в аппликативную структуру, в том же порядке, в котором вы их видели.

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

sequenceA (Stream step init) = case step init of
  Yield x s -> cons <$> x <*> sequenceA (Stream step s)
  Skip s -> sequenceA $ Stream step s
  Done -> pure (Stream (const Done) ())

Как вы можете видеть, большое отклонение от вашей попытки заключается в том, что вы должны fmapping в значение x, найденное в случае Yield - это единственный способ включить его эффекты, потому что, как вы заметили, вы не можете извлечь значение из f a, только вставьте другие значения в одно. К счастью, это то, что вы хотите сделать в конце концов! Вы просто не можете выполнить fmap над чем-либо, пока не доберетесь до интересной части структуры, что означает сначала вызвать step s, чтобы получить доступ к ее эффектам.

Вам вообще не нужен pure s, потому что вы строите новый поток с новым типом внутреннего состояния, не связанным с потребляемым вами потоком. И у вас уже есть способ использовать значение s, которое у вас есть в области видимости: вызовите step вместе с ним!

Этот подход довольно естественен, если вы уже написали пару функций, потребляющих потоки (которые я обнаружил, реализовав Foldable и Functor вручную). Единственный возможный способ использования Stream — это сопоставление регистра step s, и если вы начнете с этого, вы избежите отвлекающего маневра.

person amalloy    schedule 11.07.2018
comment
Два момента, сделанные @amalloy, прояснили мне все: (1) все эффекты должны быть оценены и (2) в правильном порядке; Поэтому рекурсия необходима. Это, вероятно, относится к большинству (всем?) traversables. - person mcmayer; 16.07.2018
comment
@mcmayer Конечно, не для всех проходов. Рассмотрим Maybe: sequenceA Nothing = pure Nothing; sequenceA (Just x) = Just <$> x. У Identity есть такой же скучный экземпляр. Вы могли бы сказать, что рекурсия необходима для всех traversables, структура которых рекурсивна, хотя я думаю, что это вопрос точки зрения. Вместо этого вы, конечно, можете использовать катаморфизм для типа — это одно и то же или нет? - person amalloy; 16.07.2018