Re: [Haskell-cafe] Code review: initial factoring for sequences andother structures

4 Aug 2006

      Brian Hulley wrote:
...
Hi -
I've started work on an initial factoring of sequence ops into
[snip]
class Foldable c a | c -> a where
       foldR :: (a -> b -> b) -> b -> c -> b
[snip]
There is a general problem that when the element type needs to be
specified along with the type of the overall collection, there is no
way to talk about the functor type at the same time
After writing this I realised it was a bit silly of me to have used a fundep 
when I could have just specified the functor types directly (instead of the 
resulting collection) thus:

    class Foldable f a where
        foldR :: (a -> b -> b) -> b -> f a -> b

so I applied this change to everything then wrote:

    module Duma.Data.Class.Functor
        ( Functor(..)
        ) where

    import Prelude hiding (map, Functor)
    import Duma.Data.Class.BasicSeq

    class Functor f a b where
        fmap :: (a -> b) -> f a -> f b

    instance (BasicSeq f a, BasicSeq f b) => Functor f a b where
        fmap = map

Now surely such an absolutely clear and straightforward instance decl would 
cause no problems at all, but guess what? Yes, even without fundeps and 
attempts to pattern match against the components of a type, GHC can't handle 
it because it needs at least one non-type variable in the instance head or 
else the dreaded -f-allow-undecidable-instances.

I wonder why there needs to be a distinction between type variables and 
non-type-variables because I'd have thought that the whole point of 
restricted polymorphism is that there's supposed to be a continuum between a 
fully unrestricted polymorphic type and a fully concrete type, with 
constraints like (BasicSeq f a) "partially solidifying" (f) and (a).

The good news is that even though the Functor class can't be implemented, 
(fmap) can at least now be implemented within BasicSeq:

    class Foldable s a => BasicSeq s a where

        map :: BasicSeq t b => (a -> b) -> s a -> t b
        map f xs =
            case viewL xs of
                Just (x, xs') -> pushL (f x) (map f xs')
                Nothing -> empty

        fmap :: BasicSeq s b => (a -> b) -> s a -> s b
        fmap = map

Anyway it's interesting that there does not yet appear to be a proper 
solution (ie to give us Foldable, BasicSeq, and Functor all with restricted 
polymorphism) with the type system as it stands at present unless 
"dangerous" flags are used.

Regards, Brian.
-- 
Logic empowers us and Love gives us purpose.
Yet still phantoms restless for eras long past,
congealed in the present in unthought forms,
strive mightily unseen to destroy us.

http://www.metamilk.com