The streaming
package offers 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
and a slightly more streamlined version,
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
These can be adapted very easily to FreeT
from the free
package. But that package offers another version of the free monad transformer:
newtype FT f m a = FT
{ runFT
:: forall r.
(a -> m r)
-> (forall x. (x -> m r) -> f x -> m r)
-> m r }
There is also a third (rather simple) formulation:
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 }
It is possible to convert back and forth between FreeT
and either FT
or FF
, which offers an indirect way to implement zipsWith
and its relatives for FF
and FT
. But that seems quite unsatisfying. I seek a more direct solution.
The problem seems related to the challenge of zipping lists using folds. This has been addressed in a paper, Coroutining Folds with Hyperfunctions, by Launchbury et al, as well as a blog post by Donnacha Kidney. Neither of these are terribly simple, and I have no idea how they might be adapted to the FT
or FF
contexts.
As I've looked into this problem, I've realized that streaming
should really offer some more powerful versions. The simplest would be something like
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)
but a more powerful option would include the remainder:
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))
I would guess that zipsWith''
would be no harder than zipsWith'
, but that zipsWithRemains
might be a bigger challenge in the context of FT
or FF
, since the remainder will presumably have to be reconstituted somehow.
Note
Since there was some confusion previously, let me mention that I am not looking for help writing zipsWithRemains
for Stream
or FreeT
; I am only looking for help with the functions on FT
and FF
.
I implemented
zipsWith'
,zipsWith''
andzipsWithRemains
forFT
. My implementation closely mirrors the implementation ofzipWith
from this blog post.First, notice that, given
zipsWith'
, implementingzipsWith''
is trivial:So let's implement
zipsWith'
.Begin with an expanded and annotated version of
zipWith
using folds:And turn it into
zipsWith'
:Here, two auxiliary functions are used:
effect
andwrap
.Note that the result could be any monad for which these functions are implemented.
To implement
zipsWithRemains
, start by implementingzipWithRemains
for ordinaryFoldable
s:Here, the result of a fold is not a function but a 2-tuple containing a function and a value. The latter is used to handle the "remains" case.
This can also be adapted to
FT
:I wish Haskell had local types!
This probably answers the question for
FT
. RegardingFF
: this type is designed such that to do anything with it, you first have to convert it to some other monad. So, the question is, which one? It is possible to convert it toStream
orFreeT
, and use the functions for those types. It is also possible to convert it toFT
and use the above implementations on it. Is there a monad better suited for implementingzipsWith
? Maybe.