kleisli-0.0.3: README.md

# kleisli

Three newtype wrappers around `p a (f b)` with different type parameter orderings, enabling different type class instances depending on which parameter is last.

| Type | Parameter order | Primary instances |
|------|----------------|-------------------|
| `Kleisli p a f b` | functor in `b` | Functor, Applicative, Monad, MonadTrans, Distributive, Representable |
| `ProKleisli p f a b` | profunctor in `(a, b)` | Profunctor, Strong, Choice, Closed, Category, Arrow, Sieve, Representable |
| `ContraKleisli p b f a` | contravariant in `a` | Contravariant, Divisible, Decidable |

All three are representationally identical (`p a (f b)`) and connected by isomorphisms.

## Usage

When `p` is specialised to `(->)`, extensive instances are derived via `Star`, `ReaderT`, `Arrow.Kleisli`, and `Op`:

```haskell
import Data.Kleisli

-- Kleisli: use as a functor/monad in the result
k :: Kleisli (->) Int Maybe Int
k = fmap (+1) (Kleisli Just)

-- ProKleisli: use as a profunctor/arrow
p :: ProKleisli (->) Maybe Int Int
p = arr (+1) >>> arr (*2)

-- ContraKleisli: use as a contravariant functor
c :: ContraKleisli (->) Int Maybe Int
c = contramap (+1) (ContraKleisli Just)
```

## Type aliases

Convenient aliases eliminate common type parameters:

```haskell
type Kleisli'  p a b = Kleisli p a Identity b       -- no functor layer
type KleisliA  a f b = Kleisli (->) a f b           -- specialise profunctor to (->)
type KleisliA' a b   = KleisliA a Identity b        -- both specialised
```

Analogous aliases exist for `ProKleisli` and `ContraKleisli`.

## Isomorphisms

Lens `Iso`s convert between the three orderings:

```haskell
_Kleisli_ProKleisli    :: Iso (Kleisli p a f b) ... (ProKleisli p f a b) ...
_Kleisli_ContraKleisli :: Iso (Kleisli p a f b) ... (ContraKleisli p b f a) ...
```

Identity-eliminating isos map through the `Identity` wrapper:

```haskell
kleisli' :: Iso (Kleisli' p a b) ... (p a b) ...
```

## Design: types as interfaces

This library follows an approach where the **data type is the API** and
**type-class instances are the interface**. There are almost no top-level
functions — users interact with these newtypes entirely through standard
algebraic vocabulary (`fmap`, `>>=`, `lmap`, `arr`, `contramap`, `divide`,
etc.) that they already know.

### How it works

A single representation (`p a (f b)`) is wrapped in three newtypes that differ
only in which type parameter is "outermost" — i.e. which parameter appears last
and therefore determines which type classes the newtype can inhabit. The
newtypes carry no runtime payload beyond what `p a (f b)` already is; they
exist solely to place the type in the right position for GHC's instance
resolution to fire.

The few top-level values that do exist cover the gaps that type classes cannot
express:

- **Isomorphisms** — there is no standard `IsomorphicTo` class that yields both
  directions, so `_Kleisli_ProKleisli` and friends are explicit `Iso` values.
- **Natural-transformation maps** (`hoistKleisli`, `pureKleisli`, etc.) —
  mapping over an inner functor layer is not captured by `Functor` (which
  operates on the outermost parameter), so a small family of combinators is
  provided.

Everything else is an instance.

### Benefits

- **Vocabulary reuse.** Users do not learn a new API. If you know `Profunctor`
  you already know how to use `ProKleisli`; if you know `Divisible` you already
  know how to use `ContraKleisli`. Every generic combinator, tutorial, and
  intuition that applies to those classes applies here without modification.

- **Composability for free.** Because the interface is expressed through
  standard classes, values of these types compose with any other code written
  against those same abstractions — lens combinators, servant routing,
  contravariant logging, arrow notation, selective functors, and so on — with
  no adapter or conversion layer.

- **Minimal surface area.** A small export list means fewer names to remember,
  fewer possible breakages across versions, and fewer degrees of freedom for
  API design mistakes. The type and its instances *are* the documentation.

- **Derivability.** `DerivingVia` lets GHC generate correct, law-abiding
  instances mechanically from an existing carrier (`Star`, `ReaderT`,
  `Arrow.Kleisli`, `Op`). The module author writes each instance at most once;
  the compiler writes the rest.

### Trade-offs

- **Discoverability.** The real functionality lives in instance heads, not in a
  list of named functions. Users must know (or look up) which class provides
  the operation they want. Haddock instance lists help, but they are less
  immediately scannable than a flat function list.

- **Type errors.** When an instance is missing or a constraint doesn't match,
  GHC's error messages refer to the class and the full newtype-wrapped type,
  which can be verbose. Type aliases help at use sites but cannot simplify error
  output.

- **Orphan-instance risk.** If a user needs an instance that this library did
  not provide, they cannot add it without creating an orphan (since both the
  class and the type are defined elsewhere relative to the user). In practice
  this is mitigated by providing instances densely — if a lawful instance
  exists, this module should already have it.

### Performance implications

All three newtypes are strict newtypes — they vanish at runtime under GHC's
optimiser. The key mechanisms:

- **Newtype coercion.** GHC represents `Kleisli (->) a f b` identically to
  `a -> f b` in memory. Wrapping, unwrapping, and converting between the three
  newtypes via the provided isos are zero-cost (they compile to `id`/`coerce`
  after optimisation).

- **INLINE pragmas.** Every top-level combinator and every hand-written instance
  method carries an `INLINE` pragma, ensuring that after inlining the only code
  that remains is the user's function and the functor operations — no dictionary
  passing, no wrapper allocation.

- **DerivingVia and specialisation.** Instances derived via `Star`, `ReaderT`,
  or `Arrow.Kleisli` are thin wrappers around those types' methods. With
  optimisation enabled (`-O1` or above), GHC specialises and inlines through
  the via-type, eliminating it entirely. The generated Core is the same as if
  the instance had been written by hand.

- **No runtime indirection.** Because there is no existential, no GADT, and no
  dictionary field stored in the type, using these newtypes has exactly the same
  runtime cost as using the underlying `p a (f b)` directly. The abstraction is
  purely a compile-time mechanism for selecting instances.

In summary: you pay nothing at runtime for the newtype layer. The only cost is
at compile time — more instances means more constraint solving — but in practice
this is negligible.

## Building

```
cabal build
cabal test doctest
cabal bench
```