Haskell: type variables and generic types

Question

When I mention in the type signature of the function isQuestion the types explicitly, GHCi compiles it perfectly:

isQuestion :: [Char] -> Maybe Bool
isQuestion [] = Nothing
isQuestion xs = Just (last xs == '?')

However, when I turn to 'generic' code, it doesn't work:

isQuestion :: [a] -> Maybe b
isQuestion [] = Nothing
isQuestion xs = Just (last xs == '?')

since I get the below error:

<interactive>:138:17: error:
    * Couldn't match type `b' with `Bool'
      `b' is a rigid type variable bound by
        the type signature for:
          isQuestion :: forall a b. [a] -> Maybe b
        at <interactive>:136:1-28
      Expected type: Maybe b
        Actual type: Maybe Bool
    * In the expression: Just (last xs == '?')
      In an equation for `isQuestion':
          isQuestion xs = Just (last xs == '?')
    * Relevant bindings include
        isQuestion :: [a] -> Maybe b (bound at <interactive>:137:1)

Not 100% sure, but I think it's because the expression can only ever evaluate to `Maybe Bool` in the second example, it's either `Nothing` or `Just Bool`. — Evan Trimboli, Apr 11 '18 at 00:42
`[a] -> Maybe b` means it should work **for all** `a` and `b`. Walk through what would happen if the compiler let you call `isQuestion` with an argument of, say, `[4]`. Ultimately it would end up trying to evaluate the expression `4 == '?'`, which doesn't make sense since you can't compare values of different types. — Chris Martin, Apr 11 '18 at 01:02
When you write a generic function, the *caller* specifies the concrete types. So if you write a function of type `a -> a`, for example, it must work for `Int -> Int`, `Char -> Char`, `String -> String`, or any other concrete type in place of `a`. That means you can’t assume anything about the operations available on `a` or what type it is, without additional constraints—for example, `Eq a` to enable using `==` and `/=`. Your function assumes `a` is `Char` and `b` is `Bool`—it’s not as generic as the type signature says. (Other answers here explain how to fix this, depending on what you want.) — Jon Purdy, Apr 11 '18 at 11:08
AFAIK, the only possible implementation of `f :: [a] -> Maybe b` is `f _ = Nothing`. — molbdnilo, Apr 11 '18 at 14:09

David Young · Answer 1 · 2018-04-12T01:07:38.813

4

The type [a] -> Maybe b is shorthand for forall a b. [a] -> Maybe b. But isQuestion doesn't work for all types a and b, it only works specifically if a is Char and b is Bool.

edited Apr 12 '18 at 01:07

answered Apr 11 '18 at 00:57

David Young

10,713
2
33
47

I think you mean if a is `Char` not `[Char]` – dave Apr 11 '18 at 23:59

Regis Kuckaertz · Accepted Answer · 2018-04-11T10:58:42.347

First observation is that

last xs == something

can only work if there is a definition of (==) in scope for the elements of xs. But as the compiler knows nothing about a, there is no such thing. You must narrow a to be the subset of types with equality:

isQuestion :: Eq a => [a] -> Maybe b

The second observation is that something is a Char in your code ('?'), so this method can only ever work when a ≡ Char. Instead, you could add that something as a parameter:

isQuestion :: Eq a => a -> [a] -> Maybe b

Finally, as has been pointed out, you have a concrete return type, i.e. Maybe Bool, as

(==) :: a -> a -> Bool

So your function's signature could be

isQuestion :: Eq a => a -> [a] -> Maybe Bool

Edited this paragraph for clarity Note that, depending on your business logic, you might not want to make a special case of the empty string. If the only thing you care about is whether a string ends with a question mark, then Nothing and Just false would virtually mean the same thing. In that case, your function becomes a "yes or no" question and you can drop the Maybe:

isQuestion :: Eq a => a -> [a] -> Bool
isQuestion x = isSuffixOf [x]

or simply

isQuestion :: String -> Bool
isQuestion = isSuffixOf "?"

Thanks Regis. But when you say "thus `Maybe Bool` would be redundant", what do you exactly mean? — devio, Apr 11 '18 at 08:44
oh, sorry that was not very clear. I'll update. I meant that, if my assumption applies, then `Nothing` and `Just false` would mean virtually the same thing, and so you could get away with just a `Bool`. — Regis Kuckaertz, Apr 11 '18 at 10:55
Thanks for clearing that up. I have put the `Maybe` type in the first place to consider the case of error (an empty list).. — devio, Apr 11 '18 at 15:31

score 2 · Answer 3 · answered Apr 11 '18 at 02:29

2

Parametric polymorphism is not subtyping or supertyping. It's a statement that the implementation of a value doesn't depend on part of the type. In fact, the implementation works for any choice of type at all.

Your implementation doesn't work for any choice of type. It only works if a is Char and b is Bool. You can tell this because it uses (== '?') in there, which is a function of type Char -> Bool.

answered Apr 11 '18 at 02:29

Carl

26,500
4
65
86

Doesn't parametric polymorphism give rise to [a subtyping relation](https://en.wikipedia.org/wiki/Hindley–Milner_type_system#Polymorphic_type_order) (you get an order on types and you upcast by specializing), though? There's *more* to it, but you can still use subtyping to explain why this can't work. Specifically, here we need `forall a b. [a] -> Maybe b`, but we've a value for a supertype, `[Char] -> Maybe Bool`, so we can't use it. If we had an `exists` quantifier, we'd even get a nice hierarchy with `exists a. a` at the top, everything else in between, and `forall a. a` at the bottom. – HTNW Apr 11 '18 at 03:06
Sure. Some polymorphic types are more general than others. But without existentials, it doesn't work at all like one would expect with OO-style subtyping. Unless you've got an incredibly strong type theory background, it's better to just learn how parametric polymorphism works first, and then place it in the theory terms later. – Carl Apr 11 '18 at 05:32

Haskell: type variables and generic types

3 Answers3