Lattice and calculation of Least Upper Bounds

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Lattice and calculation of Least Upper Bounds

Aaron Gray-6
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 ?

--
Aaron Gray

Independent Open Source Software Engineer, Computer Language Researcher, Information Theorist, and amateur computer scientist.

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Lattice and calculation of Least Upper Bounds

Olaf Klinke
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.
Reply | Threaded
Open this post in threaded view
|

Re: Lattice and calculation of Least Upper Bounds

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

Thanks,
Siddharth


On Tue 19 Jun, 2018, 21:53 Olaf Klinke, <[hidden email]> 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!

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: 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 <[hidden email]>:
>
> I'd love a reference for the last sentence - free lattice ~= continuation monad?
>
> Thanks,
> Siddharth

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Lattice and calculation of Least Upper Bounds

Aaron Gray-6
In reply to this post by Olaf Klinke
Olaf,

Thanks for the reply. Answer inline.

On Tue, 19 Jun 2018 at 20:53, Olaf Klinke <[hidden email]> 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

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 reference types.

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 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.

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.
 
 

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 ?


--
Aaron Gray

Independent Open Source Software Engineer, Computer Language Researcher, Information Theorist, and amateur computer scientist.

_______________________________________________
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.