压缩自由 monad 变换器

Question

streaming 套餐提供 a zipsWith function

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

这些可以很容易地适应免费的 monad 转换器的 FreeT from the free package. But that package offers another version：

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。但这似乎并不令人满意。我寻求更直接的解决方案。

这个问题似乎与使用折叠压缩列表的挑战有关。这已在 Donnacha Kidney 的论文 Coroutining Folds with Hyperfunctions, by Launchbury et al, as well as a blog post 中得到解决。这些都不是非常简单，我不知道它们如何适应 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 或 [=22] 的背景下可能是一个更大的挑战=]，因为其余部分可能必须以某种方式重组。

备注

由于之前有些混乱，让我提一下，我不是寻求帮助为 Stream 或 FreeT 编写 zipsWithRemains ;我只是在寻求有关 FT 和 FF.

功能的帮助

Answer 1

我为 FT 实施了 zipsWith'、zipsWith'' 和 zipsWithRemains。我的实现与 this blog post.

中 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

请注意，结果可能是实现了这些函数的任何 monad。

要实现 zipsWithRemains，首先要为普通 Foldable 实现 zipWithRemains：

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)

在这里，折叠的结果不是一个函数，而是一个包含一个函数和一个值的二元组。后者用于处理 "remains" 案例。

这个也可以适配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

我希望 Haskell 有本地类型！

这可能回答了 FT 的问题。关于 FF：这种类型的设计使得要对其进行任何操作，您首先必须将其转换为其他一些 monad。那么，问题是，哪一个？可以将其转换为 Stream 或 FreeT，并使用这些类型的函数。也可以将其转换为 FT 并在其上使用上述实现。有没有更适合实现 zipsWith 的 monad？也许。

Answer 2

应用一点 Coyoneda to 并做一些杂耍产生一个避免 Functor f 和 Functor g 约束的实现。如果那些仿函数有昂贵的 fmaps，这可能会提高性能。我怀疑在 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))

压缩自由 monad 变换器

Zipping free monad transformers

haskell

monad-transformers

free-monad

备注