Skip to content

Instantly share code, notes, and snippets.

@Icelandjack

Icelandjack/ApplicativeSum.markdown

Created June 1, 2017 15:24
Show Gist options
  • Save Icelandjack/78542ddbdb622a48d8e60e14510cd7dd to your computer and use it in GitHub Desktop.
Save Icelandjack/78542ddbdb622a48d8e60e14510cd7dd to your computer and use it in GitHub Desktop.
Download ZIP
Applicative (Sum f g) where
@Icelandjack
Copy link
Author

http://www.cs.ox.ac.uk/jeremy.gibbons/publications/ringads.pdf

The well-behaved operations over monadic values are called the algebras for that monad—functions k such that k . return = id and k . mult = k . fmap k. In particular, join is itself a monad algebra.

type Algebra f a = f a -> a

join :: Monad m => Algebra m (m a)

@Icelandjack
Copy link
Author

"Perfect Trees and Bit-reversal Permutations" (Ralf Hinze) points out that functor composition distributes left through sums

-- iso
Compose (Sum g g') f <~> Sum (Compose g f) (Compose g' f)

but distributing right goes one way,

Sum (Compose f g) (Compose f g') ~> Compose f (Sum g g')

But when does this make sense?

from' :: AppHom g g' -> Compose Pair (Sum g g') a -> Sum (Compose Pair g) (Compose Pair g') a
from' nat (Compose (InL xs  :# InL ys)) = InL (Compose (xs :# ys))
from' nat (Compose (InL xs  :# InR ys)) = InR (Compose (nat xs :# ys))
from' nat (Compose (InR xs  :# InL ys)) = InR (Compose (xs :# nat ys))
from' nat (Compose (InR xs  :# InR ys)) = InR (Compose (xs :# ys))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment