Type Inference in Haskell v. Scala

Question

Given the following code:

Prelude> let f x = if (x) then 55 else "foo"

Why does the compiler look for a Num [Char]?

<interactive>:2:23:
    No instance for (Num [Char]) arising from the literal `55'
    In the expression: 55
    In the expression: if (x) then 55 else "foo"
    In an equation for `f': f x = if (x) then 55 else "foo"

However, in Scala, it will find the least-upper bound of 55 and "foo", which is Any:

scala> def f(x: Boolean) = if (x) 55 else "foo"
f: (x: Boolean)Any

import scala.reflect.runtime.universe._

scala> lub( List[Type]( typeOf[Int], typeOf[String] ) )
res4: reflect.runtime.universe.Type = Any

What's the key difference between Haskell's and Scala's Type Inference?

Answer 1

If you're still somewhat confused, it helps to understand a little of how the back-end works.

In Haskell, a typeclass is a dictionary of functions associated with a type. Each type can only have one dictionary of functions for each typeclass. When it does, we say that it satisfies the associated constraint. So if you type :t 5 into GHCi it will tell you that the type of 5 is Num a => a, in other words, there are many types which have a value of 5 and those types are ones which have a Num dictionary. This is true because the Num dictionary defines the fromInteger :: Num a => Integer -> a function which takes the specific 5 of type Integer and casts it to that other type.

So it's complaining that it does not have the Num dictionary defined for the String type -- and of course it doesn't, because people don't usually use strings as numbers. (The type String is an alias for [Char].)

So when you write:

let f x = if x then 55 else "foo"

then here is what happens:

1. Haskell is strongly typed and if is an expression with a concrete return value with a concrete type. Both branches must have the same type.
2. GHC knows that and discerns, first off, that the type of x is x :: Bool (because it appears as the test of an if-branch and Haskell's strong types don't allow non-explicit coercion) and that 55 :: Num x => x while "foo" :: String.
3. GHC now unifies those last two types. It does this by merging the constraints separately from merging the types, so it merges x with String to find out that x = String on a type-level.
4. GHC propagates the constraint to the result of that to say that the type is Num String => String.
5. GHC complains because it does not know what the Num dictionary for String looks like.

How do you solve this problem? The easiest way is to use the data structure data Either x y = Left x | Right y that comes built-in with Haskell:

let f x = if x then Left 55 else Right "foo"

The type of the output is then Num x => Either x String, which is totally fine and does not unify the two at all. Caution: Due to a thing called the "monomorphism restriction", which is set by default in GHC but not GHCi, if you don't provide an explicit type annotation saying otherwise, f may reduce the Num a => Either a String to Either Integer String:

Prelude> :set -XMonomorphismRestriction
Prelude> let f x = if x then Left 55 else Right "foo"
Prelude> :t f
f :: Num a => Bool -> Either a [Char]
Prelude> let f = \x -> if x then Left 55 else Right "foo"
Prelude> :t f
f :: Bool -> Either Integer [Char]

Answer 2

This is because of how number literals are interpreted in Haskell.

λ> :type 412
412 :: Num a => a

What this is doing behind-the-scenes is calling the Num class fromInteger function to convert 412, or in your case, 55, into whatever instance.

We can look at the Num class like this:

λ :info Num
class Num a where
  (+) :: a -> a -> a
  (*) :: a -> a -> a
  (-) :: a -> a -> a
  negate :: a -> a
  abs :: a -> a
  signum :: a -> a
  fromInteger :: Integer -> a

So, when you write 55 and "foo", Haskell first realises that the return value must be of type [Char], because "foo" :: [Char], and tries to find an instance of Num that matches that. It fails, of course.

Scala is a very much less strictly-typed language, and, because it has no type-classes exactly like Haskell's, so can only resort to Any to describe types like that. I don't think I have to explain why that's not great, because type errors are never fun.

---

If you want to be able to return either an Int or String, you can use Either:

f :: Bool -> Either Int String
f b = if b then Left 55 else Right "foo"

Answer 3

You can add an instance for Num [Char] in Haskell, if that's what you want:

{-# LANGUAGE FlexibleInstances #-}

import Data.Function (on)
import Data.Composition ((.:))  -- cabal install composition

helper :: (Integer -> Integer -> Integer) -> (String -> String -> String)
helper op = show .: on op read

cast :: (Integer -> Integer) -> (String -> String)
cast f = show . f . read

instance Num [Char] where
    fromInteger = show
    (+) = helper (+)
    (-) = helper (-)
    (*) = helper (*)
    abs = cast abs
    signum = cast signum
    negate = cast negate

where this is just one possible implementation. This will make your example compile:

> let f x = if x then 55 else "foo"
> f True
"55"
> f False
"foo"

Haskell has polymorphic numeric literals, so 55 :: Num a => a, and since both branches of an if must return the same type, you are forcing a ~ [Char] by having the else branch return "foo". This leads to a somewhat confusing error message, but it can be a very powerful feature. It means that any numeric literal can act as the type you need it to be, and it's the same concept behind the OverloadedStrings extension, allowing you to have polymorphic string literals instead of using pack everywhere you need a Text or ByteString.

Scala uses subtyping and has a generic type for all values. It allows you to relax the type safety on a function and return literally Anything. Haskell does not have subtyping at all, so the only way to unify those types (similar to finding the LUB) is to use the fact that numeric literals are polymorphic under the Num constraint, so in order to compile "foo" has to implement Num. Actually, if you enabled OverloadedStrings f will compile just fine with the type

f :: (Data.String.IsString a, Num a) => Bool -> a

There aren't any types by default that meet both constraints, but GHC will happily accept this as a valid function.