search

bow-swift / bow

🏹 Bow is a cross-platform library for Typed Functional Programming in Swift
https://bow-swift.io
Other
645 stars 32 forks source link

Introduce Program type for free-er monads #634

Closed ferranpujolcamins closed 3 years ago

ferranpujolcamins commented 3 years ago

Goal

(Re)Introduce[1] Free-er monads in Bow. Program allows you to get a monad from any type constructor. Unlike Free, it doesn't require F to be a functor, so not only does it defer the evaluation of flatMap calls for later interpretation into another monad, but also (unlike Free) defers calls to map.

Reference: free-operational

Do we need both Free and Program? Yes. When you use Free, certain properties can be enforced in the Functor implementation of F, meaning that those properties will be fulfilled no matter what interpreter you use later [2].

When you use Program, you cannot enforce properties on the Functor implementation of F, because it's just not a functor. But, on the other hand, you don't have to implement the Functor instance. So Program is easier to use, but you cannot guarantee custom properties hold. Context will tell what option is best for you.

Implementation details

Program is just Free<Coyoneda<F>>. Free needs a functor, since F is not a functor, we use Coyoneda<F> which is the free functor of F and defers evaluation of map. So, at the end, Program defers the evaluation of flatMap calls for later interpretation into another monad, but unlike Free, it also defers calls to map (thanks to the inner Coyoneda).

Testing details

I used the same test program found in the Free tests, but you can see how it is not a functor here!

Name

I'm not really happy with the name Program. I took it from Haskell, but it doesn't really tell what this type is about IMHO.

On the other hand, Freer is too similar to Free and I think this can cause confusion or problems in code.

A third option would be to come up with a new name that tries to capture the essence of this data type but is not similar to Free. Something like EvenFreer? But then it would be more difficult to relate this type to its Haskell and Scala counterpart.

What's your view on the naming issue?

Notes

[1] The previous interpretation of Free was actually the Free-er monad! So we are just bringing it back. [2] See Purify code using free monads (Proofs section) for an example.

ferranpujolcamins commented 3 years ago

Thanks for the review. I keep forgetting about using *Of aliases!

ferranpujolcamins commented 3 years ago

What do you think about the name?

truizlop commented 3 years ago

I think it is a good name, I like it better than Freer.