Fixing type inference in HLists

Question

I've been trying to get the some code to compile. It's meant to take a HList, extract out the strings and concatenate them together.


{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeSynonymInstances #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}

module Lib
    ( y
    ) where

import Data.HList

data HConcat2 = HConcat2
instance ApplyAB HConcat2 (String, String) String where
  applyAB _ (a,b) = a ++ b
instance ApplyAB HConcat2 (Int, String) String where
  applyAB _ (_,a) = a

x :: HList '[Int, String, Int, String]
x = 3 .*. "Hello" .*. 4 .*. " World" .*. HNil

y :: String
y = hFoldr HConcat2 "Result: " x

Unfortunately, when I try to compile this it gives me

    No instance for (ApplyAB HConcat2 ([Char], [Char]) r2)
      arising from a use of ‘hFoldr’
    The type variable ‘r2’ is ambiguous
    Note: there is a potential instance available:
      instance ApplyAB HConcat2 (String, String) String
        -- Defined at src/Web/Rusalka/Condition.hs:274:10
    In the expression: hFoldr HConcat2 "Result: " x
    In an equation for ‘y’: y = hFoldr HConcat2 "Result: " x

How do I convince it to use the instances I've declared?

Ørjan Johansen Ørjan Johansen · Accepted Answer · 2015-07-12T01:21:49

There is no functional dependency on the ApplyAB class, so when GHC tries to select an instance, the input types don't determine the result type. In this case, this causes all the intermediate types in the hFoldr chain to become ambiguous, and GHC doesn't know which instances to select.

To solve this, you can use a trick, where you keep the result type completely general in the head of the instance, and use an equational ~ constraint to restrict it after GHC has selected the instance (only the head of an instance is used for selection).

If you do :i ApplyAB in GHCi, you will notice that several of the pre-defined instances use such equational constraints.

Using this (and adding TypeFamilies) makes your code work for me:

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeSynonymInstances #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE TypeFamilies #-}

module Lib
    ( y
    ) where

import Data.HList

data HConcat2 = HConcat2
instance s ~ String => ApplyAB HConcat2 (String, String) s where
  applyAB _ (a,b) = a ++ b
instance s ~ String => ApplyAB HConcat2 (Int, String) s where
  applyAB _ (_,a) = a

x :: HList '[Int, String, Int, String]
x = 3 .*. "Hello" .*. 4 .*. " World" .*. HNil

y :: String
y = hFoldr HConcat2 "Result: " x

Fixing type inference in HLists

1 Answers