5 ms·
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
by acbart 11y ago
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 https://gist.github.com/acbart/5d3fdfd8d363af26a59c
The eight inhabitants of Tri -> Bool: https://gist.github.com/acbart/c695355880a706a4ff59 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-algebraic-data-types/ http://chris-taylor.github.io/blog/2013/02/10/the-algebra-of...
- jbun77 11y agoThanks - wasn't obvious to me either. Am I missing something though, I only see six inhabitants in your gist for Tri?
- acbart 11y agoYou'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!
- wz1000 11y agoImagine 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.
- cousin_it 11y agoMaybe 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.
- saurik 11y ago> 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.)
- kahirsch 11y agoIt 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
- T-R 11y agoTo 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.
- joelburget 11y agoHi acbart, thanks for the suggestion. This is now fixed. https://codewords.recurse.com/issues/three/algebra-and-calculus-of-algebraic-data-types#fn:answer https://codewords.recurse.com/issues/three/algebra-and-calcu...
- acbart 11y agoVery 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.