A first-order function type is already exponential.

A sum type has as many possible values as the sum of its cases. E.g. `A of bool | B of bool` has 2+2=4 values. Similarly for product types and exponential types. E.g. the type bool -> bool has 2^2=4 values (id, not, const true, const false) if you don't think about side effects.

▲ jolmg 5 days ago | parent [-]

> 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

That's 3 ^ 2 = 9, right?

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

Those are 6. What would be the other 3? or should it actually be a*b=6?

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

▲

ackfoobar 5 days ago | parent | next [-]

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).

	▲	jolmg 3 days ago \| parent [-]
		> now you see why I used the smallest type possible I think the length's worth it for the sake of a crystal clear enumeration.

▲

jasperry 5 days ago | parent | prev [-]

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.