Are closed type classes enough for inference of associated types (without type families)?

Question

In the code below, ghc complains about ambiguity. I'm assuming it's because type classes are open (outside code could define new instance and actually make this ambiguous).

If I could somehow close the Indexable type class, would that be enough to make this idea a valid way to implement basic associated types?

The question is more about theoretical aspects of type inference than about how to get it to work in Haskell. Is the problem here a theoretical issue with such a system that would make inference not possible for t1 below? Would allowing closed type classes be enough to infer t1 unambiguously?

{-# LANGUAGE NoMonomorphismRestriction #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}

class Indexable a where

instance Indexable (String, Int, Char) where
instance Indexable ([(String, a)], String, a) where

test1 :: Indexable (a,b,c) => a -> b -> c
test1 x y = undefined

t1 = test1 "hi" 3 == 'c'

main = return ()

----------------------------------------------------------------
-- indexable.hs:14:6:                                         --
--     No instance for (Indexable ([Char], b0, Char))         --
--       arising from a use of ‘test1’                        --
--     The type variable ‘b0’ is ambiguous                    --
--     Note: there is a potential instance available:         --
--       instance Indexable (String, Int, Char)               --
--         -- Defined at indexable.hs:8:10                    --
--     In the first argument of ‘(==)’, namely ‘test1 "hi" 3’ --
--     In the expression: test1 "hi" 3 == 'c'                 --
--     In an equation for ‘t1’: t1 = test1 "hi" 3 == 'c'      --
--                                                            --
-- indexable.hs:14:17:                                        --
--     No instance for (Num b0) arising from the literal ‘3’  --
--     The type variable ‘b0’ is ambiguous                    --
--     Note: there are several potential instances:           --
--       instance Num Double -- Defined in ‘GHC.Float’        --
--       instance Num Float -- Defined in ‘GHC.Float’         --
--       instance Integral a => Num (GHC.Real.Ratio a)        --
--         -- Defined in ‘GHC.Real’                           --
--       ...plus three others                                 --
--     In the second argument of ‘test1’, namely ‘3’          --
--     In the first argument of ‘(==)’, namely ‘test1 "hi" 3’ --
--     In the expression: test1 "hi" 3 == 'c'                 --
----------------------------------------------------------------

Motivation: provide a basic associated types feature when designing a type system, but do it in a simple (for the type checker) way. Not intended to be used in Haskell — sinelaw
@dfeuer updated the question to clarify and also see comment above — sinelaw
@sinelaw Knowing that the key has a Num instance and that Indexable is closed and the only possible keys are Int and String isn't enough to know that the key must be Int. You would also need to know that there will never be a Num instance for String, implying that Num is also closed. Alternatively, you could tell that you must be using the instance where the container is a String from the fact that the container isn't a [(String, a)] and knowing Indexable is closed. Choosing the instance based on the container is exactly what you'd do with fundeps or type families. — Cirdec

Cirdec Cirdec · Accepted Answer · 2015-02-25T01:23:44

This error is caused by the dreaded monomorphism restriction. Disable it with NoMonomorphismRestriction.

{-# LANGUAGE NoMonomorphismRestriction #-}

This problem is a good example of where you should use MultiParamTypeClasses and newtypes.

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE NoMonomorphismRestriction #-}
{-# LANGUAGE MultiParamTypeClasses #-}

import Data.Maybe

class Indexable k v c where
    at :: c -> k -> Maybe v

An ordinary list is Indexable by Int.

instance Indexable Int a [a] where
    c `at` k = listToMaybe  . drop k $ c

A list that has the special meaning of being an association list can easily be Indexable in a different way if it's wrapped in a newtype.

newtype Assoc k v = Assoc {getAssoc :: [(k, v)]}

instance (Eq k) => Indexable k v (Assoc k v) where
    c `at` k = fmap snd . listToMaybe  . filter ((== k) . fst) . getAssoc $ c

With NoMonomorphismRestriction or an explicit signature the test snipped will compile.

-- t1 :: Indexable Int v [Char] => Maybe v
t1 = "hi" `at` (3 :: Int)

The Indexable class can be improved further by using FunctionalDependencies or TypeFamilies to help the compiler infer the involved types.

{-# LANGUAGE FunctionalDependencies #-}

class Indexable k v c | c -> k, c -> v where
    at :: c -> k -> Maybe v

Are closed type classes enough for inference of associated types (without type families)?

1 Answers