[Haskell-cafe] FDs [The container problem]

[David Menendez]

On Sat, Sep 27, 2008 at 2:43 PM, Andrew Coppin
<andrewcoppin at btinternet.com> wrote:
> Ooo, wait a sec, section 8.6.2.2. That helps...
>
> Mmm, OK. Now can somebody explain the "FDs cause problems" part?

It's not so much that fundeps cause problems, as they're less
convenient than associated types/type families in some cases.

If you look at the collection example again,

class CollFD e c | c -> e where
    emptyFD :: c
    insertFD :: e -> c -> c

class CollTF c where
    type Elem c :: *
    emptyTF :: c
    insertTF :: Elem c -> c -> c

If I want to write code that's polymorphic over instances of CollFD, I
need to use two type variables, even though one of them is completely
determined by the other.

====

If I want to write a function that, say, adds 0 to an arbitrary
Int-collection, I would write

    insertZeroFD :: (CollFD Int c) => c -> c
    insertZeroFD = insertFD 0

    insertZeroTF :: (CollTF c, Elem c ~ Int) => c -> c
    insertZeroTF = insertTF 0

But the class context for insertZeroFD isn't valid, because it doesn't
have the form CollFD e c, where e and c are type variables. So we need
the FlexibleContexts extension to make that work. (I think this is in
section 8.7.1.1 of the GHC manual, although it doesn't refer to
FlexibleContexts by name. See also
<http://hackage.haskell.org/trac/haskell-prime/wiki/FlexibleContexts>.)

====

Let's say I have a collection wrapper that stores the size of the
collection, like in Edison.

    data SizedFD1 e c = SizedFD1 Int c
    instance (CollFD e c) => CollFD e (SizedFD1 e c) where
        ...

    data SizedFD2 c = SizedFD2 Int c
    instance (CollFD e c) => CollFD e (SizedFD2 c) where
        ...

    data SizedTF c = SizedTF Int c
    instance (CollTF c) => CollTF (SizedTF c) where
        type Elem (SizedTF c) = Elem c
        ...

The two versions of SizedFD each have annoyances. First, they both
have a type variable directly in the instance head, which requires
another extension, FlexibleInstances. (Section 8.6.3.1 of the GHC
manual.)

SizedFD1 has a phantom parameter to capture the element type, so that
the element type can be connected to the collection type. Without
that, we have SizedFD2, which will not work without yet another
extension, UndecidableInstances. (Section 8.6.3.2 of the GHC manual.)

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>