Complexity of a function

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… :smirk:

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]

1 Like

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)

1 Like