haskell - 无压缩单子(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

这些可以很容易地适应 FreeT 来自 free包裹。但该套餐提供another version免费的单子(monad)变压器:

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

这个问题似乎与使用折叠压缩列表的挑战有关。这已在一篇论文中得到解决，Coroutining Folds with Hyperfunctions ，由 Launchbury 等人撰写，以及 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 的背景下可能是一个更大的挑战或 FF ，因为其余部分可能必须以某种方式重组。

笔记

由于之前有一些困惑，让我提一下，我不是在寻求帮助写作zipsWithRemains对于 Stream或 FreeT ;我只是在 FT 上寻求有关功能的帮助和 FF .

Answer 1

我实现了zipsWith' , zipsWith''和 zipsWithRemains对于 FT .我的实现与 zipWith 的实现密切相关。来自 this blog post .

首先，请注意，给定 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 ，首先实现zipWithRemains普通 Foldable年代:

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

我希望 Haskell 有本地类型!

这可能回答了 FT 的问题。 .关于FF :这种类型的设计是为了用它做任何事情，你首先必须将它转换为其他一些 monad。那么问题来了，是哪一个？可以将其转换为 Stream或 FreeT , 并使用这些类型的函数。也可以转换成FT并在其上使用上述实现。有没有更适合实现 zipsWith 的 monad ?也许。