I was reading functional programming for mortals with cats and learn about function complexity. I cannot understand why complexity of Option[Boolean] => Option[Boolean] is 2 ^ 3. Shouldn’t it be 3 * 3?
Some(True) => Some(True), Some(False), None
Some(False) => Some(True), Some(False), None
None => Some(True), Some(False), None
You are viewing the return values for a single input in isolation, but you need to take the combinations into account, so it’s 33 possible functions, as stated in the book.
| f | Some(true) | Some(false) | None |
|---|---|---|---|
| f0 | Some(true) | Some(true) | Some(true) |
| f1 | Some(true) | Some(true) | Some(false) |
| f2 | Some(true) | Some(true) | None |
| f3 | Some(true) | Some(false) | Some(true) |
| f4 | Some(true) | Some(false) | Some(false) |
| f5 | Some(true) | Some(false) | None |
| f6 | Some(true) | None | Some(true) |
| f7 | Some(true) | None | Some(false) |
| f8 | Some(true) | None | None |
| f9 | Some(false) | Some(true) | Some(true) |
| f10 | Some(false) | Some(true) | Some(false) |
| f11 | Some(false) | Some(true) | None |
| f12 | Some(false) | Some(false) | Some(true) |
| f13 | Some(false) | Some(false) | Some(false) |
| f14 | Some(false) | Some(false) | None |
| f15 | Some(false) | None | Some(true) |
| f16 | Some(false) | None | Some(false) |
| f17 | Some(false) | None | None |
| f18 | None | Some(true) | Some(true) |
| f19 | None | Some(true) | Some(false) |
| f20 | None | Some(true) | None |
| f21 | None | Some(false) | Some(true) |
| f22 | None | Some(false) | Some(false) |
| f23 | None | Some(false) | None |
| f24 | None | None | Some(true) |
| f25 | None | None | Some(false) |
| f26 | None | None | None |
Thank you for taking time to explain this to me but i still don’t see it.
Why do you have 3 columns when the function consist of 1 input and 1 output?
| Input (Option[Boolean]) | Output (Option[Boolean]) | |||
|---|---|---|---|---|
| Some(true) | Some(true) | |||
| Some(true) | Some(false) | |||
| Some(true) | None | |||
| Some(false) | Some(true) | |||
| Some(false) | Some(false) | |||
| Some(false) | None | |||
| None | Some(true) | |||
| None | Some(false) | |||
| None | None |
As the book states:
The complexity of a total function is the number of possible functions that can satisfy the type signature
You need to consider the outputs for each possible input in combination. If a function yields a different output only for a single input value than another function, they’re different functions. E.g. f0, f1 and f2 are different functions, although they only differ in the return value for None. Each of f0 through f26 is a unique function that requires a dedicated implementation. Just write them all down if you’re still suspicious… 
To get started:
def f0(i: Option[Boolean]): Option[Boolean] = Some(true)
def f1(i: Option[Boolean]): Option[Boolean] = Some(i.isDefined)
// ...
[EDIT: Nicer impl for f1]
Thanks. I was gonna ask some more stupid questions until i finally get what you are trying to illustrate. For the benefit of anyone else who might be stuck like me, this clarification might help
| input = Some(true) | input = Some(false) | input = None | |||
|---|---|---|---|---|---|
| f0 | output = Some(true) | output = Some(true) | output = Some(true) | ||
| f1 | output = Some(true) | output = Some(true) | output = Some(false) |
…