Re: Functional Dependencies

[Heribert Schuetz]

Hi Mark,

at the end of section 2 of http://www.cse.ogi.edu/~mpj/fds.html you
might want to mention that there is a "standard" work-around whenever a
type constructor is needed but not available: Introduce a newtype.

 import Bits

 class Collects e c where
empty  :: c e
insert :: e - c e - c e
member :: e - c e - Bool

 instance Eq e = Collects e [] where
   empty  = []
   insert = (:)
   member = elem

Apply the work-around for characteristic functions.

 newtype CharacteristicFunction e = CF {unCF :: e - Bool}

 instance Eq e = Collects e CharacteristicFunction where
   empty  = CF (\y - False)
   insert x c = CF (\y - x == y || unCF c x)
   member x c = unCF c x

Apply the work-around for bit sets. The dummy type variable "a" is
needed to make "BitSet b" a type constructor. (I've also generalized
your example from Char to Enum.)

 newtype Bits b = BitSet b a = BS {unBS :: b}

 instance (Enum e, Bits b) = Collects e (BitSet b) where
   empty  = BS (bit 0)
   insert x c = BS (setBit (unBS c) (fromEnum x))
   member x c = testBit (unBS c) (fromEnum x)

For the hash-table example I am pretty sure that the work-around works
as well, even though I could not figure out your intended
implementation.

Of course this is just a work-around and does not make functional
dependencies superfluous.

Regards,

Heribert.

RE: Implementation of type classes

[Heribert Schuetz]

Hi Mark,

thanks a lot for the private lesson. I have downloaded various papers
and started to read them. I'm just done with the Wadler/Blott paper.

I already suspected that I was partly reinventing the wheel with my
translation of type classes. It turned out that my approach is exactly
the same as the Wadler/Blott translation. I didn't expect my approach to
be so close to the "standard" solution, but now this gives me the good
feeling that I might have understood the stuff. In hindsight the reason
for the close similarity is of course the "user-level" understanding
that I had of type classes before.

You were mentioning rank-2 polymorphism in your message. It was exactly
that beast (and also second-order lambda calculus) that I was afraid of
when I was unsure whether my transformation does its job. I feared that
these beasts (which I don't understand yet, but hope to after working
through the pile of downloaded papers) were indispensable for type
classes. Now I see that they are not, at least for the basic case.

Regards,

Heribert.


PS: What I meant with "dependent types" were the ideas in Cayenne.

RE: Haskell Wish list: library documentation

[Johan Jeuring]

I don't want to give the impression that I think the advocates of
polytypism or arrows (...etc...) have done a poor job of describing
them.  Far from it -- there are lots of papers about polytypism for
example, and it is fine work.  But as a not-very-bright implementor
I'm just not going to get around to implementing a general idea; I
need a precise design.   

I agree: and I think Haskell's polytypic programming extension PolyP
(developed by Patrik Jansson and me) is not mature enough to be included in
a Haskell compiler: until recently we had design problems (with multiple
argument and/or mutual recursive datatypes). Recent work by Hinze gives a
nice solution to our problems, and Hinze and I agreed to implement the
ideas. So hopefully we will have a precise design + implementation of
polytypic/generic programming in a not too distant future.

-- Johan Jeuring

RE: Functional Dependencies

[Mark P Jones]

Hi Heribert,

Thanks for your feedback!

| at the end of section 2 of http://www.cse.ogi.edu/~mpj/fds.html you
| might want to mention that there is a "standard" work-around whenever a
| type constructor is needed but not available: Introduce a newtype.

Yes, an in fact this idea is mentioned at the end of the constructor
classes paper!).  But it doesn't always work, and, even when it does,
you have to deal with the extra newtype constructors in both types and
terms.  The BitSet example shows when it doesn't work ... your reworking
of that example depended on generalizing the collection type to add an
extra parameter.  But suppose that you didn't want to, or couldn't, make
that generalization.  For example, this might occur (and indeed, has
occurred in some of our experiments at OGI) in programs that package up
somebody else's code to be used via a class.  And if you can't generalize,
then you're stuck.

| For the hash-table example I am pretty sure that the work-around works
| as well, even though I could not figure out your intended
| implementation.

For the hash table example, one possible newtype encoding might be
as follows:

   newtype HTable bucket a = Array Int (bucket a)
   instance (Hashable a, Collects a b)
  = Collects a (HTable b a) where ...

But this has some problems too ... suppose (somewhat bizarrely in
this case perhaps) that you wanted to use a composition of two
collection types to build the bucket type.  The type of the
corresponding collection would be: Array Int (outer (inner a)).
This would work just fine with the functional dependencies version,
but for the constructor classes version you'd have to introduce
yet another newtype and instance:

   newtype Compose f g x = Comp (f (g x))
   instance (Collects a g, Collects (g a) f)
  = Collects a (Comp f g) where ...

And so on ...

| Of course this is just a work-around and does not make functional
| dependencies superfluous.

That's true.  There are plenty of things you can do with dependencies
that you can't do with constructor classes, and vice versa.

I picked the Collects example because I thought it would be something
that would be reasonably familiar, but perhaps it has the danger of
giving people the impression that functional dependencies are an
alternative to constructor classes.  That's unfortunate because they're
really pretty orthogonal.

All the best,
Mark