Haskell ad-hoc polymorphism on values, calculating the length of list of ad-hoc polymorphism

Question

I am trying to understand one phenomenon from my code below:

{-# LANGUAGE NoMonomorphismRestriction #-}

import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.Map as M
import Data.Function
import Data.Ratio

class (Show a, Eq a) => Bits a where
    zer :: a
    one :: a

instance Bits Int where
    zer = 0
    one = 1

instance Bits Bool where
    zer = False
    one = True

instance Bits Char where
    zer = '0'
    one = '1'

When I try this:

b = zer:[]

It works perfectly, but when I try:

len = length b

I get this error:

<interactive>:78:8: error:
    • Ambiguous type variable ‘a0’ arising from a use of ‘b’
      prevents the constraint ‘(Bits a0)’ from being solved.
      Probable fix: use a type annotation to specify what ‘a0’ should be.
      These potential instances exist:
        instance [safe] Bits Bool -- Defined at main.hs:18:10
        instance [safe] Bits Char -- Defined at main.hs:22:10
        instance [safe] Bits Int -- Defined at main.hs:14:10
    • In the first argument of ‘length’, namely ‘b’
      In the expression: length b
      In an equation for ‘it’: it = length b

Can someone explain to me why it is possible to create list from values zer and one, but if I want to calculate length of the list I get an error?

`b` is not a list, but a polymorphic list: for each type, `b` produces a list. Potentially, the length of `b` could depend on the type (OK, not on this class, but that's immaterial). So, we need to use `length (b :: [SomeType])`. — chi, Nov 15 '18 at 13:23
"*why it is possible to create list from values zer and one*" - it isn't. You haven't actually created a concrete list yet, you defined `b` with a polymorphic type. You can't e.g. print it either. When you want to use `b`, you need to tell the program which type it should use - if it cannot infer it from something else, e..g in the expression `True : b` or `0 : b`. — Bergi, Nov 15 '18 at 13:50
The type checker lets you "pass the buck" on the specific instance of `Bits` to use if the `Bits` constraint remains in the final value. Consider `map id b`, which has type `Bits a => [a]`. The use of `length`, though, forces a decision to be made, because the `Bits` constraint is not passed on; as far as the type checker is concerned, `length` might do something that requires a specific instance. — chepner, Nov 15 '18 at 14:50

Benjamin Hodgson · Accepted Answer · 2018-11-15T15:41:18.577

3

It's perhaps a little easier to understand the meaning of this error in the following example:

roundTrip :: String -> String
roundTrip = show . read

So roundTrip reads a String, and then shows it back into a (presumably identical) String.

But read is a polymorphic function: it parses the input string in a manner that depends on the output type. Parsing an Int is a rather different ask than parsing a Bool!

The elaborator decides which concrete implementation of read to use by looking at the inferred return type of read. But in the expression show . read, the intermediate type could be any type a which implements both Show and Read. How is the compiler supposed to choose an implementation?

You might argue that in your example it doesn't matter because length :: [a] -> Int treats its type argument uniformly. length [zer] is always 1, no matter which instance of Bits you're going through. That sort of situation is difficult for a compiler to detect in general, though, so it's simpler and more predictable to just always reject ambiguous types.

You can fix the issue by giving a concrete type annotation.

> length ([zer] :: [Bool])
1

edited Nov 15 '18 at 15:41

answered Nov 15 '18 at 14:57

Benjamin Hodgson

42,952
15
108
157

The part I'm confused about is why Haskell wants to infer a monomorphic type for `len` rather than the polymorphic type `(Bits a) => Integer` – Owen Nov 15 '18 at 17:00
1

@Owen Because `Integer` is not a polymorphic type. The type variable needs to appear on the right hand side. – Bergi Nov 15 '18 at 22:07
@Owen You could define `len :: Bits a => [a] -> Integer; len = length`, but still when you would call `len b` the compiler has exactly the same problem as with `show` and `read`. – Bergi Nov 15 '18 at 22:09
@Bergi Ah ok, I see, thank you. Though, I will add that with `(Bits a) => Integer` is not ill-defined, it's just unusable, and with `AllowAmbiguousTypes` Haskell does allow it. – Owen Nov 16 '18 at 01:31

Haskell ad-hoc polymorphism on values, calculating the length of list of ad-hoc polymorphism

1 Answers1