Ambiguity error with higher order lists and family types
I have a higher order GADT list defined like this:
data HList as where
HNil :: HList '[]
HCons :: a -> HList as -> HList (a ': as)
I can write a function that returns me the first item from this list if it is not empty:
first :: HList (a ': as) -> HList '[a]
first (HCons a _) = HCons a HNil
However, if I create a new type Cat
and type family that simply applies each type in the type list to Cat
(like a level map):
newtype Cat a = Cat a
type family MapCat (as :: [*]) :: [*] where
MapCat '[] = '[]
MapCat (a ': as) = Cat a ': MapCat as
And a type CatList
that converts a list of types to HList
full of these types applied to Cat
:
type CatList cs = HList (MapCat cs)
I cannot write a similar function that works for CatList
.
first' :: CatList (a ': as) -> CatList '[a]
first' (HCons a _) = HCons a HNil
Failure:
Couldn't match type ‘MapCat as0’ with ‘MapCat as’
NB: ‘MapCat’ is a type function, and may not be injective
The type variable ‘as0’ is ambiguous
Expected type: CatList (a : as) -> CatList '[a]
Actual type: CatList (a : as0) -> CatList '[a]
In the ambiguity check for:
forall a (as :: [*]). CatList (a : as) -> CatList '[a]
To defer the ambiguity check to use sites, enable AllowAmbiguousTypes
In the type signature:
Testing.fst :: CatList (a : as) -> CatList '[a]
What will go wrong? Here's the gist of all the code .
source to share
Let's start with a simpler example:
type family F a
err :: F a -> ()
err _ = ()
throws
Couldn't match type ‘F a0’ with ‘F a’ NB:
F is a type function, and may not be injective
The type variable a0 is ambiguous
Expected type: F a -> ()
Actual type: F a0 -> () …
So far this compiles fine:
ok :: (a ~ Int) => F a -> ()
ok _ = ()
And this:
type family F a where
F a = a
ok :: F a -> ()
ok _ = ()
Here's another example that is closer to your problem:
data D = C
data Id (d :: D) where
Id :: Id d
type family TF_Id (d :: D) :: D where
TF_Id C = C
err :: Id (TF_Id d) -> ()
err _ = ()
Mistake
Couldn't match type ‘TF_Id d0’ with ‘TF_Id d’ NB:
TF_Id is a type function, and may not be injective
The type variable d0 is ambiguous
Expected type: Id (TF_Id d) -> ()
Actual type: Id (TF_Id d0) -> () …
But this works:
ok :: Id (TF_Id C) -> ()
ok _ = ()
and this:
type family TF_Id (d :: D) :: D where
TF_Id x = x
ok :: Id (TF_Id d) -> ()
ok _ = ()
since it TF_Id a
immediately decreases to a
in both cases.
Thus, the compiler throws an error every time it cannot reduce SomeTypeFamily a
, where a
is some type variable that was not previously defined.
So, if we want to fix this:
type family TF_Id (d :: D) :: D where
TF_Id C = C
err :: Id (TF_Id d) -> ()
err _ = ()
without overriding the type family, we need to define d
in the type signature err
. The easiest way -
type family TF_Id (d :: D) :: D where
TF_Id C = C
ok :: Id d -> Id (TF_Id d) -> ()
ok _ _ = ()
Or we can define a data type for this:
data Proxy (d :: D) = Proxy
ok :: Proxy d -> Id (TF_Id d) -> ()
ok _ _ = ()
Now back to the function first'
:
data Proxy (a :: [*]) = Proxy
first' :: Proxy (a ': as) -> CatList (a ': as) -> CatList '[a]
first' _ (HCons a _) = HCons a HNil
This compiles fine. You can use it like this:
main = print $ first' (Proxy :: Proxy '[Int, Bool]) (HCons (Cat 3) $ HCons (Cat True) HNil)
which prints Cat3:[]
.
But the only thing the compiler needs to know to shrink MapCat as
is the normal form of a weak head as
, so we really don't need to provide this additional type information in Proxy :: Proxy '[Int, Bool]
. Here's the best way:
data ListWHNF (as :: [*]) where
LZ :: ListWHNF '[]
LS :: ListWHNF as -> ListWHNF (a ': as)
first' :: ListWHNF (a ': as) -> CatList (a ': as) -> CatList '[a]
first' _ (HCons a _) = HCons a HNil
main = print $ first' (LS $ LS LZ) (HCons (Cat 3) $ HCons (Cat True) HNil)
So first'
now gets something similar to the length of the list. But can we do it statically? Not so fast:
data ListWHNF (as :: [*]) where
LZ :: ListWHNF '[]
LS :: ListWHNF as -> ListWHNF (a ': as)
data HList as ln where
HNil :: HList '[] LZ
HCons :: a -> HList as ln -> HList (a ': as) (LS ln)
throws Data constructor LZ comes from an un-promotable type ListWHNF …
. We cannot use indexed data types like indexes in Haskell.
Having some functional dependencies that would allow us to associate a term of one type and a weak vowel normal form of a term of another, we could probably do the trick, but I don't know anything like that in GHC (but I'm not an expert). It's easy in Agda
_^_ : ∀ {α} -> Set α -> ℕ -> Set α
A ^ 0 = Lift ⊤
A ^ suc n = A × A ^ n
So, if this is the only thing we need to output the list, this is its length, then we can replace the list with n
nested tuples. Abuse of designations, [?, ?] :: [*]
becomes (? :: *, (? :: *, Lift ⊤))
, and now all these ?
can now be deduced automatically among the inhabitant ⊤
(equivalent to Agda ()
). But in Agda there is no distinction between value level and type programming, so there are no such problems at all.
source to share