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

Siddharth Bhat siddu.druid at gmail.com
Tue Jun 19 20:13:53 UTC 2018

I'd love a reference for the last sentence - free lattice ~= continuation


On Tue 19 Jun, 2018, 21:53 Olaf Klinke, <olf at aatal-apotheke.de> wrote:

> Aaron,
> the lattices package provides some modules to extend a given lattice by
> some elements, e.g. new top and bottoms. There are also derived typeclass
> instances for combinations like tuples, endomorphisms and so forth. But the
> way of choice really depends on what you know about your multiple
> inheritance hierarchy.
> In universal algebra one powerful method of constructing (semi-)lattices
> is by generators and relations. That means you define the lattice as a
> quotient of a free lattice. The quotient itself is defined as a set of
> ineqalities on the generators. I don't know how one would implement that
> without dependent types, though, as the type would be another type together
> with a function. To make things worse, the word problem is undecidable in
> general.
> Looking at Algebra.Lattice.Free I'm surprised that the free (semi-)lattice
> types don't have a Monad instance. Does anyone know why they are not
> implemented? Under the hood the free lattice types are identical to the
> continuation monad.
> Olaf
> >Hi,
> >
> >I am trying to work out how to use the Algebra.Lattice family of Lattice
> >data structures.
> >
> >Firstly how do I construct a lattice ?
> >
> >What I am wanting to do is to be able to construct a lattice to represent
> a
> >multiple inheritance hierarchy. Then I to be able to find the Least Upper
> >Bound of a set of classes/types. This is in order to find the type of a
> >multiple case expression.
> >
> >I am not sure if the Haskell classes are actually applicable ? but if they
> >are how do I apply them to the following problem please ?
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.

Sending this from my phone, please excuse any typos!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20180619/dd1664c1/attachment.html>

More information about the Haskell-Cafe mailing list