Молния монадой трансформаторов

Question

streaming пакет предлагает zipsWith функция

zipsWith
  :: (Monad m, Functor h)
  => (forall x y. f x -> g y -> h (x, y))
  -> Stream f m r -> Stream g m r -> Stream h m r

и немного более обтекаемая версия,

zipsWith'
  :: Monad m
  => (forall x y p. (x -> y -> p) -> f x -> g y -> h p)
  -> Stream f m r -> Stream g m r -> Stream h m r

Они могут быть очень легко адаптированы к FreeT от free пакет. Но этот пакет предлагает другую версию бесплатного монадного преобразователя:

newtype FT f m a = FT
  { runFT
      :: forall r.
         (a -> m r)
      -> (forall x. (x -> m r) -> f x -> m r)
      -> m r }

Существует также третья (довольно простая) формулировка:

newtype FF f m a = FF
  { runFF
      :: forall n. Monad n
      => (forall x. f x -> n x)  -- A natural transformation
      -> (forall x. m x -> n x)  -- A monad morphism
      -> n a }

Можно конвертировать туда и обратно между FreeT и либо FT или же FF, который предлагает косвенный способ реализации zipsWith и его родственники для FF а также FT, Но это кажется совершенно неудовлетворительным. Я ищу более прямое решение.

Кажется, проблема связана с проблемой складывания списков с использованием складывания. Этот вопрос был рассмотрен в статье Launchbury et al., А также в блоге Donnacha Kidney, Coroutining Folds with Hyperfunctions. Ничто из этого не очень просто, и я понятия не имею, как они могут быть адаптированы к FT или же FF контексты.

---

Когда я изучил эту проблему, я понял, что streaming должен действительно предложить несколько более мощных версий. Самый простой будет что-то вроде

zipsWith''
  :: Monad m
  => (forall x y p. (x -> y -> p) -> f x -> g y -> h p)
  -> Stream f m r -> Stream g m s -> Stream h m (Either r s)

но более мощный вариант будет включать в себя остаток:

zipsWithRemains
  :: Monad m
  => (forall x y p. (x -> y -> p) -> f x -> g y -> h p)
  -> Stream f m r
  -> Stream g m s
  -> Stream h m (Either (r, Stream g m s)
                        (f (Stream f m r), s))

Я бы догадался, что zipsWith'' будет не сложнее, чем zipsWith', но это zipsWithRemains может быть более сложной задачей в контексте FT или же FF, так как остаток, вероятно, придется каким-то образом восстанавливать.

Заметка

Поскольку ранее была некоторая путаница, позвольте мне упомянуть, что я не ищу помощь в написании zipsWithRemains за Stream или же FreeT; Я только ищу помощь с функциями на FT а также FF,

Answer 1

Я реализовал zipsWith', zipsWith'' а также zipsWithRemains за FT, Моя реализация тесно отражает реализацию zipWith из этого блога.

Во-первых, обратите внимание, что, учитывая zipsWith', осуществляя zipsWith'' тривиально:

zipsWith''
  :: (Functor f, Functor g, Monad m)
  => (forall x y p. (x -> y -> p) -> f x -> g y -> h p)
  -> FT f m r
  -> FT g m s
  -> FT h m (Either r s)
zipsWith'' phi a b = zipsWith' phi (Left <$> a) (Right <$> b)

Итак, давайте реализуем zipsWith',

Начните с расширенной и аннотированной версии zipWith используя складки:

newtype RecFold a r = RecFold { runRecFold :: BFold a r }
type AFold a r = RecFold a r -> r
type BFold a r = a -> AFold a r -> r

zipWith
  :: forall f g a b c.
  (Foldable f, Foldable g)
  => (a -> b -> c)
  -> f a
  -> g b
  -> [c]
zipWith c a b = loop af bf where
  af :: AFold a [c]
  af = foldr ac ai a
  ai :: AFold a [c]
  ai _ = []
  ac :: a -> AFold a [c] -> AFold a [c]
  ac ae ar bl = runRecFold bl ae ar
  bf :: BFold a [c]
  bf = foldr bc bi b
  bi :: BFold a [c]
  bi _ _ = []
  bc :: b -> BFold a [c] -> BFold a [c]
  bc be br ae ar = c ae be : loop ar br
  loop :: AFold a [c] -> BFold a [c] -> [c]
  loop al bl = al (RecFold bl)

И превратить это в zipsWith':

newtype RecFold f m r = RecFold { runRecFold :: BFold f m r }
type AFold f m r = m (RecFold f m r -> r)
type BFold f m r = m (f (AFold f m r) -> r)

zipsWith'
  :: forall f g h m r.
  (Monad m, Functor f, Functor g)
  => (forall x y p. (x -> y -> p) -> f x -> g y -> h p)
  -> FT f m r
  -> FT g m r
  -> FT h m r
zipsWith' phi a b = loop af bf where
  af :: AFold f m (FT h m r)
  af = runFT a ai ac
  ai :: r -> AFold f m (FT h m r)
  ai r = return $ const $ return r
  ac :: (x -> AFold f m (FT h m r)) -> f x -> AFold f m (FT h m r)
  ac am ae = return $ effect . fmap ($ (fmap am ae)) . runRecFold
  bf :: BFold f m (FT h m r)
  bf = runFT b bi bc
  bi :: r -> BFold f m (FT h m r)
  bi r = return $ const $ return r
  bc :: (x -> BFold f m (FT h m r)) -> g x -> BFold f m (FT h m r)
  bc bm be = return $ wrap . flip (phi loop) (fmap bm be)
  loop :: AFold f m (FT h m r) -> BFold f m (FT h m r) -> FT h m r
  loop av bv = effect $ fmap ($ (RecFold bv)) av

Здесь используются две вспомогательные функции: effect а также wrap,

effect :: Monad m => m (FT f m r) -> FT f m r
effect m = FT $ \hr hy -> m >>= \r -> runFT r hr hy

wrap :: f (FT f m r) -> FT f m r
wrap s = FT $ \hr hy -> hy (\v -> runFT v hr hy) s

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

Реализовать zipsWithRemainsначать с реализации zipWithRemains для обычных Foldables:

data ListWithTail a b = Nil b | Cons a (ListWithTail a b)
type Result a b c = ListWithTail c (Either [b] (a, [a]))
newtype RecFold a b c = RecFold { runRecFold :: BFold a b c }
type AFold a b c = (RecFold a b c -> Result a b c, [a])
type BFold a b c = (a -> AFold a b c -> Result a b c, [b])

zipWithRemains
  :: forall f g a b c.
  (Foldable f, Foldable g)
  => (a -> b -> c)
  -> f a
  -> g b
  -> Result a b c
zipWithRemains c a b = loop af bf where
  af :: AFold a b c
  af = foldr ac ai a
  ai :: AFold a b c
  ai = (\bl -> Nil $ Left $ snd (runRecFold bl), [])
  ac :: a -> AFold a b c -> AFold a b c
  ac ae ar = (\bl -> fst (runRecFold bl) ae ar, ae : snd ar)
  bf :: BFold a b c
  bf = foldr bc bi b
  bi :: BFold a b c
  bi = (\ae ar -> Nil $ Right (ae, snd ar), [])
  bc :: b -> BFold a b c -> BFold a b c
  bc be br = (\ae ar -> Cons (c ae be) (loop ar br), be : snd br)
  loop :: AFold a b c -> BFold a b c -> Result a b c
  loop al bl = fst al (RecFold bl)

Здесь результатом сгиба является не функция, а 2-кортеж, содержащий функцию и значение. Последний используется для обработки "остатков" дела.

Это также может быть адаптировано к FT:

type Result f g h m r s = FT h m (Either (r, FT g m s) (f (FT f m r), s))
newtype RecFold f g h m r s = RecFold { runRecFold :: BFold f g h m r s }
type AFold f g h m r s = m (RecFold f g h m r s -> Result f g h m r s, FT f m r)
type BFold f g h m r s = m (f (AFold f g h m r s) -> Result f g h m r s, FT g m s)

zipsWithRemains
  :: forall f g h m r s.
  (Monad m, Functor f, Functor g)
  => (forall x y p. (x -> y -> p) -> f x -> g y -> h p)
  -> FT f m r
  -> FT g m s
  -> Result f g h m r s
zipsWithRemains phi a b = loop af bf where
  af :: AFold f g h m r s
  af = runFT a ai ac
  ai :: r -> AFold f g h m r s
  ai r = return (return . Left . (r,) . effect . fmap snd . runRecFold, return r)
  ac :: (x -> AFold f g h m r s) -> f x -> AFold f g h m r s
  ac am ae = return (effect . fmap (($ (fmap am ae)) . fst) . runRecFold, wrap $ fmap (effect . fmap snd . am) ae)
  bf :: BFold f g h m r s
  bf = runFT b bi bc
  bi :: s -> BFold f g h m r s
  bi r = return (return . Right . (,r) . fmap (effect . fmap snd), return r)
  bc :: (x -> BFold f g h m r s) -> g x -> BFold f g h m r s
  bc bm be = return (wrap . flip (phi loop) (fmap bm be), wrap $ fmap (effect . fmap snd . bm) be)
  loop :: AFold f g h m r s -> BFold f g h m r s -> Result f g h m r s
  loop av bv = effect $ fmap (($ (RecFold bv)) . fst) av

Я бы хотел, чтобы на Хаскеле были местные типы!

Это, вероятно, отвечает на вопрос FT, относительно FF: этот тип разработан таким образом, что для того, чтобы что-то с ним сделать, сначала нужно преобразовать его в какую-нибудь другую монаду Итак, вопрос в том, какой? Можно конвертировать в Stream или же FreeTи использовать функции для этих типов. Также возможно преобразовать его в FT и используйте вышеупомянутые реализации на нем. Есть ли монада, лучше подходящая для реализации zipsWith? Может быть.

Answer 2

Применение небольшого количества Coyoneda к ответу abacabadabacaba и некоторая жонглирование приводит к реализации, которая избегает Functor f а также Functor g ограничения. Если эти функторы дорогие fmapс, это может улучшить производительность. Я сомневаюсь, что это на самом деле лучше в типичных ситуациях, когда f а также g такие вещи, как (,) a, Я также до сих пор не понимаю, что из этого получается.

type AFold f m r = m (RecFold f m r -> r)
newtype Fish f m r = Fish {unFish :: forall x. (x -> AFold f m r) -> f x -> r}
type BFold f m r = m (Fish f m r)
newtype RecFold f m r = RecFold { runRecFold :: BFold f m r }

zipsWith'
  :: forall f g h m r.
  Monad m
  => (forall x y p. (x -> y -> p) -> f x -> g y -> h p)
  -> FT f m r
  -> FT g m r
  -> FT h m r
zipsWith' phi a b = loop af bf where
  af :: AFold f m (FT h m r)
  af = runFT a ai ac

  ai :: r -> AFold f m (FT h m r)
  ai r = return $ const $ return r

  ac :: (x -> AFold f m (FT h m r)) -> f x -> AFold f m (FT h m r)
  ac am ae = return $ (lift >=> \(Fish z) -> z am ae) . runRecFold

  bf :: BFold f m (FT h m r)
  bf = runFT b bi bc

  bi :: r -> BFold f m (FT h m r)
  bi r = return $ Fish $ \_ _ -> return r

  bc :: (x -> BFold f m (FT h m r)) -> g x -> BFold f m (FT h m r)
  bc bm be = return $ Fish $ \xa z -> wrap $ phi (\q -> loop (xa q) . bm) z be

  loop :: AFold f m (FT h m r) -> BFold f m (FT h m r) -> FT h m r
  loop av bv = lift av >>= ($ (RecFold bv))