Why does GHC not "upcast" a Vector to a Foldable?

Question

In an attempt to learn how to write more generic code, I tried to write a simple Array class. The idea is to write some simple array operations only with the functions provided by the Array class and then to write different data types as instances. So I want to write different representations of arrays.

For a first attempt, an array has a number of rows and columns and a container that is foldable.

module Array where

import qualified Data.Vector as V
import           Data.Foldable

class Array arr where
    aRows :: arr a -> Int
    aCols :: arr a -> Int
    aData :: Foldable t => arr a -> t a

data VectorArray a = VectorArray
    { vRows :: !Int
    , vCols :: !Int
    , vData :: !(V.Vector a)}

instance Array VectorArray where
    aRows = vRows
    aCols = vCols
    aData = vData

The last line does not compile:

• Couldn't match type ‘t’ with ‘V.Vector’
  ‘t’ is a rigid type variable bound by
    the type signature for:
      aData :: forall (t :: * -> *) a. Foldable t => VectorArray a -> t a
    at src/Array.hs:19:5
  Expected type: VectorArray a -> t a
    Actual type: VectorArray a -> V.Vector a
• In the expression: vData

My interpretation of the error message: You (programmer) give me a V.Vector a but I (the GHC compiler) want a t a where the t must be an instance of the Foldable class.

Now, a V.Vector is an instance of Foldable. So in every function where I have to pass an instance of Foldable as an argument, I can use a value of type V.Vector. My question is: Why does GHC not "upcast" a V.Vector to a Foldable? Are there any examples, where such an upcast would be a source of problems?

PS: The real and good solution to avoid the above error is to drop the aData function from the Array class and to make VectorArray an instance of Foldable.

Answer 1

The type of aData says that for any t that the caller chooses, it will return a value of type t a. But the implementation only returns a Vector. "Upcasting" as you call it would require converting a Vector to any Foldable structure, but not only is there no implicit way to do this, it is practically not possible: what if the vector is empty and the users wants a NonEmpty list?

Answer 2

Values are not instances of typeclasses. An Int is not a Num; a VectorArray Foo is not an Array. Types are instances of typeclasses: Int is Num, VectorArray is Array, Vector is Foldable. You cannot upcast some x :: Vector Foo to x :: Foldable, because Foldable just isn't applicable to values. Haskell does have subtyping (e.g. mempty :: forall m. Monoid m => m, but since Group m (if such a class existed) implies Monoid m, mempty :: forall g. Group g => g, too), but it's a bit arcane and isn't relevant.

You want an existential type:

class Array arr where
  aRows :: arr a -> Int
  aCols :: arr a -> Int
  aData :: arr a -> (exists f. Foldable f => f a)

The syntax exists f. Foldable f => f a is (somewhat standard) psuedo-Haskell. It means that, whatever it is, it is Foldable, and it contains as, but you don't know what the containing type exactly is. You can't do this directly, but you can get close:

data SomeFoldable a = forall f. Foldable f => SomeFoldable (f a)
-- Can't be a newtype: the Foldable f dictionary needs to be put somewhere
aData :: Array arr => arr a -> SomeFoldable a

The Haskell syntax for existential types is rather perverse, as it uses the opposite quantifier, forall to define them. The justification is that the above creates the constructor

SomeFoldable :: forall f. Foldable f => f a -> SomeFoldable a

which "forgets" what f specifically is.

Using these is pretty straightforward, but not as nice as just making Foldable a superclass of Array:

instance Array VectorArray where
    aRows = vRows
    aCols = vCols
    aData = SomeFoldable . vData

sum :: (Num a, Array arr) => arr a -> a
sum arr = case aData arr of
  SomeFoldable fa -> foldl' (+) 0 fa
-- Need to use patterns to destructure; let won't work (same for GADTs).
-- Foldable instance in scope on right side of case

-- Example:
instance Array [] where
  aRows _ = 1
  aCols = length
  aData = SomeFoldable
sum [1,2,3] == 6