Question about typing

[Marcin 'Qrczak' Kowalczyk]

Sat, 07 Apr 2001 20:46:00 -0500, Matt Harden <matth@mindspring.com> pisze:

>    class (Functor f) => ZipFunctor f where
>       -- "zap" stands for "zip apply"
>       -- it applies a set of functions to a set
>       -- of arguments, producing a set of results
>       zap :: f (a->b) -> f a -> f b

This is nice as long as the type is fully polymorphic. Unfortunately
this is not always the case in reality.

Let's take unboxed flat sequences (unboxed vectors). Imagine we have
    data UVector a
    class Seq c a | c -> a
    instance Seq (UVector Bool) Bool
    instance Seq (UVector Char) Char
    instance Seq (UVector Int)  Int
    -- etc.
(in fact I do have this). Class Seq provides various operations common
to sequences. There are no problems with operations involving sequences
of the same type (e.g. splitAt), but it's not obvious how to handle map
and zipWith.

BTW. Alternatively it could be expressed thus:
    data UVector a
    class Seq c a
    instance Seq UVector Bool
    instance Seq UVector Char
    instance Seq UVector Int
    -- etc.
but it disallows certain abstractions, like conversion of an immutable
container to a mutable container independently of its kind. This
doesn't change the problem with map.

I found a way to express map and zipWith, but it's quite ugly. I would
be happy to have a better way.

    class Map c' a' c a | c' -> a', c -> a, c' a -> c, c a' -> c' where
        map :: (a' -> a) -> c' -> c
    class (Map c a c a, ...) => Seq c a
        -- Class Seq requires method map which doesn't chage the
        -- element type.

    instance Map [a] a [b] b
        -- map on lists is more general than mere Seq requires:
        -- it's fully polymorphic wrt. the element type.
    instance Seq [a] a
        -- This instance alone implies only Map [a] a [a] a.

    class IArray c a
        -- This is a class of immutable arrays, provided by ghc.

    newtype IArrayToVector c a = V (c Int a)
        -- Convert an immutable array to a flat sequence.
        -- (In fact I have done this a bit differently; it doesn't
        -- matter now.)
    instance (IArray c a', IArray c a) => Map (c Int a') a' (c Int a) a
        -- As long as both element types are ok for an immutable array,
        -- vector derived from the array can be mapped from one to
        -- the other.
    instance IArray c a => Seq (c Int a) a
        -- This implies only Map (c Int a) a (c Int a) a.

    data UArray k a
    instance IArray UArray Bool
    instance IArray UArray Char
    instance IArray UArray Int
        -- etc. This is provided by ghc.
    type UVector = IArrayToVector UArray
        -- There are instances  Seq (UVector a) a  for particular choices
        -- of a, and more: instances  Map (UVector a') a' (UVector a) a
        -- for particular choices of a' and a.

    -- zipWith is similar to map, only more complicated:
    class ZipWith c1 a1 c2 a2 c a
        | c1 -> a1, c2 -> a2, c -> a,
          c1 a -> c, c a1 -> c1, c2 a -> c, c a2 -> c2
        where
        zipWith :: (a1 -> a2 -> a) -> c1 -> c2 -> c

    -- zipWith3 is even more ugly.

An alternative way is this: remove Map class, have map as a standalone
function which converts a container to a list, maps the list, and
converts it back. Disadvantages are that it applies only to things
which can be sensibly converted to a list, and that if mapping of a
dictionary is specified as preserving the keys (actually the key is
in the function argument but not in the result), then it must recreate
the dictionary structure from scratch.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK