Alfonso Acosta alfonso.acosta at gmail.com
Wed Feb 21 12:10:50 EST 2007

Now I'm facing another problem, sorry if it takes too long to reach
the Type level lambdas issue ...

The full definition of my class is

class Synchronous s f1 f2 |  s -> f1, s -> f2  where
mapSY		:: f1 a b -> s a -> s b
delaySY	:: a  -> s a -> s a
zipWithSY     :: f2 a b c-> s a -> s b -> s c

The goal of this class is to extend the name of the following
functions (which BTW are already present in a working library and for
that reason _it is a must_ that their types remain untouched) ...

mapSY  :: (a->b) -> Signal a -> Signal b
delaySY :: a -> Signal a -> Signal b -> Signal c
zipWithSY :: (a->b->c) -> Signal a -> Signal b -> Signal c

.. accepting these definitions as well

mapSY :: (HDPrimType a, HDPrimType b) => HDFun (a->b) -> HDSignal a -> Signal b
delaySY :: HDPrimType a => a -> HDSignal a -> HDSignal a
zipWithSY :: (HDPrimType a, HDPrimType b, HDPrimType c) => HDFun
(a->b->c) -> HDSignal a -> HDSignal b -> HDSignal c

The problem is: How to choose the f1 and f2 parameters when defining
the instances?

instance Synchronous Signal (->) ?? where

instance Synchronous HDSignal ?? ?? where

I'm facing one of the problems discussed at Type Classes with
Functional Dependencies
(http://web.cecs.pdx.edu/~mpj/pubs/fundeps-esop2000.pdf )section 3.1:

"Some of the remaining instances can be reworked to ﬁt the constructor
class framework by introducing dummy type and value constructors"

The following is a solution following the one proposed by MJones in
his paper, but is not acceptable as it requires changing the types of
the original functions.

newtype F2 a b c = F2 (a->b->c)
newtype HDF1 a b = HDF1 (HDFun (a->b))
newtype HDF2 a b c = HDF2 (HDFun (a->b->c))

instance Synchronous Signal (->) F2 where ....
instance Synchronous HDSignal HDF1 HDF2 where ...

Following MJones advice, redefining the class to something such us ...

class Synchronous2 a sa sb sc f1ab f2abc |  {- dependencies ommited -} where
mapSY		:: f1ab -> sa -> sb
delaySY	:: a  -> sa -> sa
zipWithSY     :: f2abc-> sa -> sb -> sc

... is feasible but not elegant at all because the number of class
parameters and dependencies are dramatically increased.

In my opinion adding Type-level lambdas would be the way to go, but
they unfortunately are not part of Haskell.

Something like this would be much more expressive and useful.

Using the first definition of the class we could do something as

instance Synchronous Signal (->) (\a b c -> (a->b->c))  where ....
instance Synchronous HDSignal (\a b -> HDFun (a->b)) (\a b c -> HDFun
(a->b->c)) where ...

Is there any extension to the language covering type-level lambdas or
even a plan to include them in next revision?

Thanks,

Fons

On 2/21/07, Alfonso Acosta <alfonso.acosta at gmail.com> wrote:
> Thanks, the functional dependency solved the problem
>
> On 2/21/07, Yitzchak Gale <gale at sefer.org> wrote:
> > Hi Alfonso,
> >
> > You wrote:
> > >     Could not deduce (Synchronous s f11)
> > >       from the context (Synchronous s f1)
> > > \begin{code}
> > > class Synchronous s f1  where
> > >  mapSY          :: f1 a b   -> s a -> s b
> > >  delaySY         :: a        -> s a -> s a
> > >  sourceSY       :: f1 a a -> a    -> s a
> > >  sourceSY f s0 = o
> > >   where
> > >      o                  = delaySY s0 s
> > >      s                  = mapSY f o
> > > \end{code}
> > >
> > > Can anyone explain a bit further than GHC what am I doing wrong?
> >
> > Every method of a multiparameter class must refer
> > to every parameter in its signature. Otherwise, there
> > is no way for the compiler to know which instance
> > of the class you want when you use the method.
> >
> > There are two ways to get around this restriction.
> > One is to use a functional dependency:
> >
> > class Synchronous s f1 | s -> f1 where
> >
> > That promises that for each type s, you will
> > only define an instance Synchronous s f1
> > for at most a single type f1. Now, whenever
> > you mention s in a type signature, it is as if
> > you also mentioned f1.
> >
> > If you can't keep that promise, then you will
> > have to use a phantom parameter. Change
> > the type of delaySY to
> >
> > delaySY         :: f1 -> a -> s a -> s a
> >
> > and ignore the f1 parameter when you implement
> > delaySY:
> >
> > delaySY _ x y = ...
> >
> > Then, when you use delaySY, you specify the
> > type f1 by writing:
> >
> > delaySY (undefined :: T) ...
> >
> > Regards,
> > Yitz
> >
>