[Haskell-cafe] Lattice and calculation of Least Upper Bounds
aaronngray.lists at gmail.com
Fri Jun 29 00:15:29 UTC 2018
Thanks for the reply. Answer inline.
On Tue, 19 Jun 2018 at 20:53, Olaf Klinke <olf at aatal-apotheke.de> wrote:
> 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
AFAICS all that needs to be known about the inheritance hierarchy in order
to create the lattice is the sub type relations, and also top and bottom
Ideally I would like to iterate through the hierarchy starting with top and
then the base classes and add them incrementally with their subtype
dependencies through to bottom.
> 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
> 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.
I think the Lattice classes may well be still in flux as I looked about a
month ago ad there seemed to be AFAICR a Least Upper Bound operation taking
a list of elements and returning an element.
> >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
> >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 ?
Independent Open Source Software Engineer, Computer Language Researcher,
Information Theorist, and amateur computer scientist.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe