[prev in list] [next in list] [prev in thread] [next in thread] 

List:       haskell-cafe
Subject:    Re: [Haskell-cafe] Most Important GHC extensions to learn/use?
From:       Gábor_Lehel <illissius () gmail ! com>
Date:       2012-06-03 10:25:50
Message-ID: CAPNUp09ZJa6zf+8qY0XChgYPD9Ei2OSuYz2+RdpuX2pnR-w3cQ () mail ! gmail ! com
[Download RAW message or body]

On Fri, Jun 1, 2012 at 4:37 PM, James Cook <mokus@deepbondi.net> wrote:
> On Jun 1, 2012, at 6:11 AM, Gábor Lehel wrote:
> 
> > On Fri, Jun 1, 2012 at 6:29 AM, wren ng thornton <wren@freegeek.org> \
> > wrote:
> > > 
> > > TypeFamilies (aka TFs)
> > > These are really nifty and they're all the rage these days. In
> > > a formal sense they're equivalent to fundeps, but in practice
> > > they're weaker than fundeps.
> > 
> > Is that still true? The reason used to be that we didn't have
> > superclass equalities, but we do have them now since 7.2. The only
> > drawbacks I know of relative to FDs are that it's sometimes more
> > typing, not supported by GeneralizedNewtypeDeriving, and doesn't allow
> > OverlappingInstances (ick).
> 
> In addition to other things mentioned today in the "Fundeps and \
> overlapping instances" thread, type families have no way of defining \
> injective type functions where the range includes already-existing types. \
>  For example, if you define:
> 
> > type family Succ a
> 
> there is no way (that I've found) to define it in such a way that the \
> compiler can "see" that Succ a ~ Succ b => a ~ b. 
> The equivalent in MPTCs+FDs would be:
> 
> > class Succ a b | a -> b, b -> a

class (S a ~ b, P b ~ a) => Succ a b where
    type S a
    type P b

(Succ a c, Succ b c)
=>
(S a ~ c, P c ~ a, S b ~ c, P c ~ b)
=>
(P c ~ a, P c ~ b)
=>
(a ~ P c, P c ~ b)
=>
(a ~ b)

> 
> There is more discussion of this particular weakness at \
> http://hackage.haskell.org/trac/ghc/ticket/6018 . 
> Also, there are less-common usages of fundeps that may be translatable to \
> type families but not easily, when there are complex interrelationships \
> between type variables.  For example, type-level binary operations will \
> sometimes have fundeps such as "a b -> c, a c -> b, b c -> a" - that is \
> to say, any two determines the third.

Like above:

class (FD1 a b ~ c, FD2 b c ~ a, FD3 c a ~ b) => BinOp a b c where
    type FD1 a b
    type FD2 b c
    type FD3 c a

You can mechanically translate MPTCs with FDs into MPTCs with ATs and
superclass equalities in this way, and your fingers will get a lot of
exercise. But that's the basis for the claim that TFs with superclass
equalities are no less powerful than FDs. It's true that this doesn't
always allow you to express everything as just plain top-level type
families, but then, neither do FDs :).

@wren, did you have some other examples in mind?

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


[prev in list] [next in list] [prev in thread] [next in thread]