# functor-monad: Monads on category of Functors

This package provides `FFunctor` and `FMonad`,
each corresponds to `Functor` and `Monad` but higher-order.

|      | a Functor `f`   | a FFunctor `ff` |
|----|----|----|
| Takes | `a :: Type` | `g :: Type -> Type`, `Functor g` |
| Makes | `f a :: Type` | `ff g :: Type -> Type`, `Functor (ff g)` |
| Methods | `fmap :: (a -> b) -> f a -> f b` | `ffmap :: (Functor g, Functor h) => (g ~> h) -> (ff g ~> ff h)` |

|      | a Monad `m`   | a FMonad `mm` |
|----|----|----|
| Superclass | Functor | FFunctor |
| Methods | `return = pure :: a -> m a` | `fpure :: (Functor g) => g ~> mm g` |
|        | `(=<<) :: (a -> m b) -> m a -> m b` | `fbind :: (Functor g, Functor h) => (g ~> mm h) -> (mm g ~> mm h)` |
|        | `join :: m (m a) -> m a` | `fjoin :: (Functor g) => mm (mm g) ~> mm g` |

See also: https://viercc.github.io/blog/posts/2020-08-23-fmonad.html (Japanese article)

## Motivational examples

Many types defined in [base](https://hackage.haskell.org/package/base-4.18.1.0) and popolar libraries like
[transformers](https://hackage.haskell.org/package/transformers-0.6.1.1) take a parameter expecting a `Functor`.
Here are two, simple examples.

```haskell
-- From "base", Data.Functor.Sum
data Sum f g x = InL (f x) | InR (g x)
instance (Functor f, Functor g) => Functor (Sum f g)

-- From "transformers", Control.Monad.Trans.Reader
newtype ReaderT r m x = ReaderT { runReaderT :: r -> m x }
instance (Functor m) => Functor (ReaderT r m)
```

These types often have a way to map a natural transformation, an arrow between two `Functor`s,
over that parameter.

```haskell
-- The type of natural transformations
type (~>) f g = forall x. f x -> g x

mapRight :: (g ~> g') -> Sum f g ~> Sum f g'
mapRight _  (InL fx) = InL fx
mapRight nt (InR gx) = InR (nt gx)

mapReaderT :: (m a -> n b) -> ReaderT r m a -> ReaderT r n b

-- mapReaderT can be used to map natural transformation
mapReaderT' :: (m ~> n) -> (ReaderT r m ~> ReaderT r n)
mapReaderT' naturalTrans = mapReaderT naturalTrans
```

The type class `FFunctor` abstracts type constructors equipped with such a function.

```haskell
class (forall g. Functor g => Functor (ff g)) => FFunctor ff where
    ffmap :: (Functor g, Functor h) => (g ~> h) -> ff g x -> ff h x

ffmap :: (Functor g, Functor g') => (g ~> g') -> Sum f g x -> Sum f g' x
ffmap :: (Functor m, Functor n)  => (m ~> n) -> ReaderT r m x -> ReaderT r n x
```

Not all but many `FFunctor` instances can, in addition to `ffmap`, support `Monad`-like operations.
This package provide another type class `FMonad` to represent such operations.

```haskell
class (FFunctor mm) => FMonad mm where
    fpure :: (Functor g) => g ~> mm g
    fbind :: (Functor g, Functor h) => (g ~> ff h) -> ff g a -> ff h a
```

Both of the above examples, `Sum` and `ReaderT r`, have `FMonad` instances.

```haskell
instance Functor f => FMonad (Sum f) where
    fpure :: (Functor g) => g ~> Sum f g
    fpure = InR

    fbind :: (Functor g, Functor h) => (g ~> Sum f h) -> Sum f g a -> Sum f h a
    fbind _ (InL fa) = InL fa
    fbind k (InR ga) = k ga

instance FMonad (ReaderT r) where
    fpure :: (Functor m) => m ~> ReaderT r m
    -- return :: x -> (e -> x)
    fpure = ReaderT . return

    fbind :: (Functor m, Functor n) => (m ~> ReaderT r n) -> ReaderT r m a -> ReaderT r n a
    -- join :: (e -> e -> x) -> (e -> x)
    fbind k = ReaderT . (>>= runReaderT . k) . runReaderT 
```

## Comparison against similar type classes

There are packages with very similar type classes, but they are more or less different to this package.

* From [hkd](https://hackage.haskell.org/package/hkd): `FFunctor`
  
  There is a class named `FFunctor` in `hkd` package too. It represents a functor from /category of type constructors/ `k -> Type` to
  the category of usual types and functions.

  Since it is not an endofunctor, there can be no `Monad`-like classes on them.

  Another package [rank2classes](https://hackage.haskell.org/package/rank2classes) also provides the same class `Rank2.Functor`.
  
* From [mmorph](https://hackage.haskell.org/package/mmorph-1.2.0): `MFunctor`, `MMonad`

  `MFunctor` is a class for endofunctors on the category of `Monad`s and monad homomorphisms.
  If `T` is a `MFunctor`, it takes a `Monad m` and constructs `Monad (T m)`,
  and its `hoist` method takes a *Monad morphism* `m ~> n` and returns a new *Monad morphism* `T m ~> T n`.

  On the other hand, this library is about endofunctors on the category of `Functor`s and natural transformations,
  which are similar but definitely distinct concept.

  For example, `Sum f` in the example above is not an instance of `MFunctor`, since there are no general way to make `Sum f m` a `Monad`
  for arbitrary `Monad m`.

  ```
  instance Functor f => FFunctor (Sum f)
  instance Functor f => MFunctor (Sum f) -- Can be written, but it will violate the requirement to be MFunctor
  ```

* From [index-core](https://hackage.haskell.org/package/index-core): `IFunctor`, `IMonad`

  They are endofunctors on the category of type constructors of kind `k -> Type` and polymorphic functions `t :: forall (x :: k). f x -> g x`.
  
  While any instance of `FFunctor` from this package can be faithfully represented as a `IFunctor`, some instances can't be an instance of `IFunctor` _as is_.
  Most notably, [Free](https://hackage.haskell.org/package/free-5.1.8/docs/Control-Monad-Free.html#t:Free) can't be an instance of `IFunctor` directly,
  because `Free` needs `Functor h` to be able to implement `fmapI`, the method of `IFunctor`.

  ```haskell
  class IFunctor ff where
    fmapI :: (g ~> h) -> (ff g ~> ff h)
  ```

  There exists a workaround: you can use another representation of `Free f` which doesn't require `Functor f` to be a `Functor` itself,
  for example `Program` from [operational](https://hackage.haskell.org/package/operational) package.

  This package avoids the neccesity of the workaround by admitting the restriction that the parameter of `FFunctor` must always be a `Functor`.
  Therefore, `FFunctor` gives up instances which don't take `Functor` parameter, for example, a type constructor `F` with kind `F :: (Nat -> Type) -> Nat -> Type`.

* From [functor-combinators](https://hackage.haskell.org/package/functor-combinators-0.4.1.2): `HFunctor`, `Inject`, `HBind`

  This package can be thought of as a more developed version of `index-core`, since they share the base assumption.
  The tradeoff between this package is the same: some `FFunctor` instances can only be `HFunctor` via alternative representations.
  Same applies for `FMonad` versus `Inject + HBind`.