> bool -> bool has 2^2=4 values

Not the best example since 2*2=4 also.

How about this bit of Haskell:

  f :: Bool -> Maybe Bool

  f False = Nothing
  f False = Just True
  f False = Just False
  f True = Nothing
  f True = Just True
  f True = Just False

EDIT: Nevermind, I counted wrong. Here are the 9:

  f x = case x of
    True -> Nothing
    False -> Nothing

  f x = case x of
    True -> Nothing
    False -> Just False

  f x = case x of
    True -> Nothing
    False -> Just True

  f x = case x of
    True -> Just False
    False -> Nothing

  f x = case x of
    True -> Just False
    False -> Just False

  f x = case x of
    True -> Just False
    False -> Just True

  f x = case x of
    True -> Just True
    False -> Nothing

  f x = case x of
    True -> Just True
    False -> Just False

  f x = case x of
    True -> Just True
    False -> Just True

Good point, well there's Ordering type built-in in Haskell (LT | EQ | GT). Ordering -> bool has 2^3=8 values (const true, const false, == LT, == EQ, == GT, is_lte, is_gte, ne)

EDIT: now you see why I used the smallest type possible to make my point. Exponentials get big FAST (duh).

You didn't list all functions, just input-output pairs. Each function is a map from every possible input to an output:

f1 False = Nothing, f1 True = Nothing

f2 False = Nothing, f2 True = Just True

...

This gives the correct 3^2 = 9 functions.