Understanding a case of Haskell Type-Ambiguity

Question

I wrote a Haskell program and got a compile error I don't understand.

The program should:

• Get the command line arguments
• Concatenate tokenized arguments back to a single String
• Read the String into a NestedList data type
• Flatten the NestedList into a List
• Print the List

Unfortunately, it won't compile because of a type ambiguity.

Haskell Code:

{-
  Run like this:
  $ ./prog List [Elem 1, List [Elem 2, List [Elem 3, Elem 4], Elem 5]]
  Output: [1,2,3,4,5]
-}
import System.Environment
import Data.List

data NestedList a = Elem a | List [NestedList a]
  deriving (Read)

main = do
  args <- getArgs
  print . flatten . read $ intercalate " " args

flatten :: NestedList a -> [a]
flatten (Elem x) = [x]
flatten (List x) = concatMap flatten x

Compile Error:

prog.hs:8:21:
    Ambiguous type variable `a0' in the constraints:
      (Read a0) arising from a use of `read' at prog.hs:8:21-24
      (Show a0) arising from a use of `print' at prog.hs:8:3-7
    Probable fix: add a type signature that fixes these type variable(s)
    In the second argument of `(.)', namely `read'
    In the second argument of `(.)', namely `flatten . read'
    In the expression: print . flatten . read

Could someone help me understand how/why there is a type ambiguity and how I can make the code unambiguous.

Answer 1

Ambiguous types occur in Haskell whenever a type variable disappears due to function application. The one you have here, read/show is common. Here's the problem:

Let's try to read a string, this operation has the type

read :: Read a => String -> a

such that if we give it a string we'll just get a type that looks like

read "()" :: Read a => a

In other words, the type system has not yet been able to pick a concrete type---it simply knows that whatever the answer is it must be Readable.

The problem is that if we turn back around and show this immediately we're applying a function

show :: Show a => a -> String

which also doesn't fully specify the type a. Combining them gives us

show (read "()") :: String

and we've lost all opportunities to decide upon what that intermediate type should have been.

Due to this ambiguity, Haskell disallows such expressions. You fix it by somehow interjecting a function which completely constrains the type. A common method is to use the function asTypeOf

asTypeOf :: a -> a -> a
asTypeOf = const

which ensures that the first and second arguments have the same type.

> show (read "()" `asTypeOf` ()) :: String
"()"

---

In your particular example you need to determine what the a is in NestedList a. An easy method to doing that is to explicitly give the type of flatten as a concrete type.

print . (flatten :: NestedList Int -> [Int]) . read $ concat args

Answer 2

This is a classic problem. The "ad hoc" polymorphism of type classes makes type inference incomplete, and you've just been bitten. Let's look at the pieces.

read    :: Read x => String -> x
flatten :: NestedList a -> [a]
print   :: Show y => y -> IO ()

and we'll also have machine-generated instances for

Read a => Read (NestedList a)
Show a => Show (NestedList a)
Read a => Read [a]
Show a => Show [a]

Now let's solve the equations we get when we try to build the composition.

print   .     flatten              .   read

      y = [a]         NestedList a = x

That means we need

Show [a]                     Read (NestedList a)  

and thus

Show a                       Read a

and we've used all our information without determining a, and hence the relevant Read and Show instances.

As J. Abrahamson has already suggested, you need to do something which determines the a. There are lots of ways to do it. I tend to prefer type annotations to writing strange terms whose only purpose is to make a type more obvious. I second the proposal to give a type to one of the components in the composition, but I'd probably pick (read :: String -> NestedList Int), as that's the operation which introduces the ambiguously typed thing.