Hacker News Reader

Comment by acbart | Hacker News Reader

If you're like me, and you didn't immediately understand why the number of inhabitants for "a -> b" is "a^b", and needed help for the answer[1], then here's my solution to the author's question ("Why are there eight inhabitants of Tri -> Bool, but nine of Bool -> Tri? It helps to write out each possible function.").

The nine inhabitants of Bool -> Tri: https://gist.github.com/acbart/5d3fdfd8d363af26a59c

The eight inhabitants of Tri -> Bool: https://gist.github.com/acbart/c695355880a706a4ff59

Pedagogical note: If you're going to poise a question in an online presentation of material, try to have a solution (automatically checked or at least statically available). A huge part of learning is having the learner participate (which you did!) and then assessed.

[1] I got help from here, @tikhonj suggested this in another comment: http://chris-taylor.github.io/blog/2013/02/10/the-algebra-of...

View on HN

It may be helpful to think about this as a table.

9 functions from 2 to 3 - How many 2 digit numbers in base 3?

Each row represents a function from {True,False} to {A,B,C}.

    False  True
    -----  -----
      A      A      Function 1   f₁(False)=A   f₁(True)=A
      A      B      Function 2   f₂(False)=A   f₂(True)=B
      A      C      Function 3   etc.
      B      A      Function 4
      B      B      Function 5
      B      C      Function 6
      C      A      Function 7
      C      B      Function 8
      C      C      Function 9

8 functions from 3 to 2 - How many 3 digit numbers in base 2?

      A      B      C
    -----  -----  -----
    False  False  False   Function 1   f₁(A)=False f₁(B)=False f₁(C)=False
    False  False  True    Function 2   f₂(A)=False f₂(B)=False f₂(C)=True
    False  True   False   Function 3   etc.
    False  True   True    Function 4
    True   False  False   Function 5
    True   False  True    Function 6
    True   True   False   Function 7
    True   True   True    Function 8

Imagine a collection of a objects(lets call it A) and another collection of b objects(called B). A function is a set of arrows matching each object in A to an object in B. Each object in A only has one arrow originating from it.

For each object in A, you have b ways to draw an arrow to an object in B. As there are a number of objects in A, the total number of arrows you can draw is bbb*b... a times. Hence the number of functions from A -> B is b^a.

> the number of inhabitants for "a -> b" is "a^b"

You mean "b^a". (wz1000 has it right, but he didn't point out that the original statement had them flipped.)

Maybe that part would've been easier with Bool and Unit. It's obvious that there is only one function from Bool to Unit, and two functions from Unit to Bool.

Hi acbart, thanks for the suggestion. This is now fixed. https://codewords.recurse.com/issues/three/algebra-and-calcu...

Very cool! Thank you for writing this article, I found it very helpful and extremely interesting. I also found it a very nice read in general.

Thanks - wasn't obvious to me either. Am I missing something though, I only see six inhabitants in your gist for Tri?

You're right, I missed two cases! Thanks a bunch. Second pedagogical note: we just demonstrated the value of cooperative learning, which can really help a weak assessment. Similar to paired programming!

To add another way to look at it (thinking of a function as a set of tuples):

With tuples (A,B), you're listing As uniquely paired with Bs

With functions (A -> B), you're listnig unique sets of (As non-uniquely paired with Bs), so each A can go to any value of B, with replacement.

Reply on news.ycombinator.com