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 8Imagine 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.
Re:The Algebra of Algebraic data types
by joelburget on Friday June 26, 2015 @08:39PM
(#9788566)
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.
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...