[Haskell-cafe] Lattice and calculation of Least Upper Bounds

[Olaf Klinke]

Well, free lattice ~= continuation monad is not entirely true, since 

Cont a x = (x -> a) -> a

and 

FreeLattice x = forall a. Lattice a => (x -> a) -> a

So in the latter the a is qualified and a rank-2 type. But the types are similar in structure. Thinking of it some more, the unit should be identical but the monad bind could be different. I'm just throwing in the first thing that type-checks; I haven't proven the monad laws for this. But at this abstraction level, the chances are good that the first thing that type-checks is the one you want. Consider the following. (I shortened the type names a bit.)

{-# LANGUAGE Rank2Types #-}
class Lat a where
   v :: a -> a -> a
   -- add more operations if you wish

newtype F x = F {free :: forall a. Lat a => (x -> a) -> a}
instance Lat (F x) where
   v x y = F (\f -> v (free x f) (free y f))

returnLat :: x -> F x
returnLat x = F (\f -> f x)
-- ^ same as for continuation monad

bindF :: F x -> (x -> F y) -> F y
bindF phi k = free phi k
-- ^ uses the fact that F y is a Lat instance.

Maybe also a blog post by Dan Doel [1] is relevant, where the free monoid is considered. 
-- Olaf

[1] http://comonad.com/reader/2015/free-monoids-in-haskell/


> 
> Am 19.06.2018 um 22:13 schrieb Siddharth Bhat <siddu.druid at gmail.com>:
> 
> I'd love a reference for the last sentence - free lattice ~= continuation monad?
> 
> Thanks,
> Siddharth