3 ms·

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 valu

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 1y ago
> 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 1y ago
  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 1y ago
    > 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 1y ago
  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.

jolmg 1y ago

> 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 1y ago
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 1y ago
  > 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 1y ago
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.