# How many values of this type?

## Background

The number of values for a given type is called the cardinality of that type, and that of type T is written as |T|.

Haskell and a few other languages have a certain set of enum types, each of which has a small finite number of values (the exact names vary, so this challenge uses some arbitrarily chosen names).

Name  | Cardinality
------+-------------
Never | 0
Unit  | 1
Bool  | 2 (true or false)
Order | 3 (LT, EQ, or GT)


And they also have some derived types which have one or more type parameters. Their cardinality depends on which types they get as parameters (written as T and U in the table below). Func(T,U) represents the function commonly written as T -> U, i.e. a function that takes a parameter of type T and returns a value of type U.

Name(Params) | Cardinality
-------------+-------------
Option(T)    | |T| + 1     (some value from T, or absence)
Either(T,U)  | |T| + |U|   (some value from T or some value from U)
Pair(T,U)    | |T| * |U|   (any combination of values from T and U)
Func(T,U)    | |U| ** |T|  (any combination of U for every value of T)


Note: A "function" here is to be understood as a mathematical concept rather than a programming one. A mathematical function Func(T,U) maps every possible value of T to some value of U, disregarding the "how". For programmers, it is OK to think of it as functions of the form of (in Haskell-like pseudocode):

$$x :: T) -> case x of value1OfT -> someValue1OfU value2OfT -> someValue2OfU ... valueXOfT -> someValueXOfU  with all cases provided. For example, Option(Never) has cardinality 1, and Func(Bool,Order) has cardinality 3**2 = 9. Func(Never,Never) has cardinality 1; 0**0 is defined to be 1 in this system. A type parameter can itself be a derived type, so Pair(Func(Never,Never),Pair(Either(Bool,Bool),Option(Order))) is also a valid type, which has cardinality of (0**0) * ((2+2) * (3+1)) = 16. For this challenge, assume that no types other than the 8 presented above are available. ## Challenge Given a string that represents a valid type in this system, output its cardinality. You can assume the input does not contain spaces. Standard rules apply. The shortest code in bytes wins. ## Test cases Never -> 0 Unit -> 1 Bool -> 2 Order -> 3 Func(Never,Never) -> 1 Func(Unit,Never) -> 0 Option(Unit) -> 2 Option(Order) -> 4 Either(Bool,Bool) -> 4 Either(Bool,Order) -> 5 Pair(Bool,Order) -> 6 Pair(Func(Never,Never),Pair(Either(Bool,Bool),Option(Order))) -> 16 Func(Func(Order,Order),Order) -> 7625597484987  • I cannot understand why Either(Bool, Bool) should be 4. Won't it noly support true and false anyway? – tsh Oct 14, 2021 at 2:13 • @tsh Using Haskell terms, Either(T,U) has two constructors Left(T) and Right(U), and Left(True) != Right(True). So you get four values in total: Left(True), Left(False), Right(True), Right(False). Oct 14, 2021 at 2:15 • @tsh It's not a simple union type, but a labeled union type. Oct 16, 2021 at 0:11 ## 12 Answers # Proton, 80 bytes Never,Unit,Bool,Order=0..4 Option=(1+) Either=(+) Pair=(*) Func=(x,y)=>y**x eval  Try it online! This solution is a whole lot shorter in Proton. Original Python solution included below. # Python 3, 106 bytes Never=0 Unit=1 Bool=2 Order=3 Option=1 .__add__ Either=int.__add__ Pair=int.__mul__ Func=int.__rpow__ eval  Try it online! -3 bytes thanks to dingledooper __rpow__ exists so I don't even have to do lambda x,y:y**x so this is even more boring :D trivial solution and I'm sure there's something both better and smarter • Perhaps I'm missing something but the bare eval at the end seems not to do anything? Oct 14, 2021 at 3:54 • @Dingus It's the actual function that produces the output. Oct 14, 2021 at 3:56 • Funny solution! I think you can replace lambda x,y:y**x with int.__rpow__? Oct 14, 2021 at 4:07 • Is there a special rule that allows this format for function answers? It looks to me half way between full program and function: you cannot assign this code to a variable and call it like a function, or use it in a place where a lambda function would be accepted, like in another function's parameter.. Oct 14, 2021 at 7:50 • @Kaddath Functions are allowed to depend on previous code (such as other function declarations), if that's what you mean? – Neil Oct 14, 2021 at 8:30 # JavaScript (V8), 98 bytes Never=0 Unit=1 Bool=2 Order=3 Option=x=>1+x Either=(x,y)=>x+y Pair=Math.imul Func=(x,y)=>y**x eval  Try it online! Same idea as @hyper-neutrino, though its shorter in js -1 byte thanks to @Arnauld • You can save a byte by using Math.imul instead of (x,y)=>x*y (32-bit only, though). Oct 14, 2021 at 9:10 • @Arnuald nice, thanks! Oct 14, 2021 at 10:15 # 05AB1E, 7731 28 bytes Rv"0123>+*m ""NUBdpEPF"ykè.V  Byte-count more than halved and sped up a lot by porting @Neil's Charcoal answer, so make sure to upvote him as well! Explanation: R # Reverse the (implicit) input-string v # Loop over each of its characters y: "NUBdpEPF"yk # Get the index of y in "NUBdpEPF" # (which will result in -1 if it isn't present) "0123>+*m " è # Use it to (0-base modulair) index into "0123>+*m " .V # Execute it as 05AB1E code: # >: Increment the top value by 1 # +: Add the top two values together # *: Multiply the top two values # m: Take the exponent of the top two values # The digits 0-3 remain the same #  : No-op for not found characters / index -1 # (after which the result is output implicitly)  ### Original (77 bytes) answer: ”†™‰¿ëÄ‚Ñ”#ā<:Δ”íŽ‰‡¥Öˆ¦c”#vD.γd}þàÝ©NĀiã©',ý}€…(ÿ)yì®N_i>ëíðý…m+*Nè«}øvy.V:  Because 05AB1E lacks both regexes and functions, this uses a brute-force replacement method wrapped in a loop. It's therefore also extremely slow the larger the integer becomes, and will fail to complete the final test cases as is. Try it online or verify all test cases (the Δ is replaced with [Dd# in the test suite to speed it up slightly, so we can also verify the last test case). Explanation: ”†™‰¿ëÄ‚Ñ” # Push dictionary string "Never Unit Bool Order" # # Split it on spaces: ["Never","Unit","Bool","Order"] ā # Push a list in the range [1,length] (without popping): [1,2,3,4] < # Decrease each to the range [0,length): [0,1,2,3] : # Replace all "Never" with 0; "Unit" with 1; etc. in the (implicit) # input-string Δ # Loop until the result no longer changes: [Dd# # (slightly faster alternative, so we'll have one iteration less:) [ # Start an infinite loop D # Duplicate the current string d # If it's a non-negative (>=0) integer: # # Stop the infinite loop ”íŽ‰‡¥Öˆ¦c” # Push dictionary string "Option Either Pair Func" # # Split it on spaces: ["Option","Either","Pair","Func"] v # Loop over each string y in this list: D.γd}þà # Get the current maximum integer in the string: D # Duplicate the string .γ # Group this string into substrings by: d # If it's a non-negative (>=0) integer }þ # After the group-by, only leave these integers à # And pop and push the maximum Ý # Pop and push a list in the range [0,max] © # Store it in variable ® NĀi # If the index is NOT 0 (thus not "Option"): ã # Take the cartesian product of this list © # Store that in variable ® instead ',ý '# And join each inner pair with "," delimiter }€…(ÿ) # After the if-statement: wrap each integer/string into parenthesis yì # And prepend the current string y ® # Push list ® again N_i # If the index is 0 (thus "Option"): > # Simply increase the value by 1 ë # Else: í # Reverse each pair in the list ðý # Join each pair with space delimiter …m+* # Push string "m+*" Nè # Index the loop-index into it (0-based modulair) « # Append it to each string }ø # After the if-else statement: zip to create pairs of the two lists v # Loop over each pair y in this list: y # Push the pair y  # Pop and push both values separated to the stack .V # Execute the second string as 05AB1E code, resulting in an integer : # Replace the first string to this integer # (after which the result is output implicitly)  See this 05AB1E tip of mine (section How to use the dictionary?) to understand why ”†™‰¿ëÄ‚Ñ” is "Never Unit Bool Order" and ”íŽ‰‡¥Öˆ¦c” is "Option Either Pair Func". • Ugh, another boring eval-based answer ;-) – Neil Oct 15, 2021 at 8:34 • @Neil Haha, I guess yeah. Seems to be the shortest approach, based on my two programs. ;p Oct 15, 2021 at 8:45 # Retina, 129 bytes Or Q {TNUBQ)(l0-3;_ O(\d+); .(_1* E(\d+),(\d+); .(1*_2* P(\d+),(\d+); .(1*2* F(\d+) F1* (F_*)_(,\d+;) P122 F,\d+; 1  Try it online! Link includes test cases. Explanation: Or Q  Change Order to Qder to avoid confusion with Option, and also because O has special meaning for Transliterate. {  Repeat the remaining transformations until the desired result is obtained. (The transliteration does not need to be repeated but it's golfer to share the .) TNUBQ)(l0-3;_  Transliterate the Never, Unit, Bool and Qder to 0 to 3 respectively, transliterate the ) to ; for ease of matching, and delete the lower case letters and (. O(\d+); .(_1*  Handle Option by incrementing the value. E(\d+),(\d+); .(1*_2*  Handle Either by taking the sum of the values. P(\d+),(\d+); .(1*2*  Handle Pair by taking the product of the values. F(\d+) F1*  Convert the first parameter of Func to unary. (F_*)_(,\d+;) P122  Compute Func(n+1,m) as Func(n,m)*m using P to do the multiplication. F,\d+; 1  Func(0,m) is just 1. # Retina 0.8.2, 111 bytes Op.{5} EU, TNUB\O)(l0-3;_ \d * E(1*),(1*); 12 (P1*)1(,1*;) E122 P,1*; (F1*)1(,1*;) P122 }F,1*; 1 1  Try it online! Link includes reduced test cases, as Retina 0.8.2 has to calculate in unary, which limits the magnitude of the result. Explanation: Op.{5} EU,  Change Option( to Either(Unit, (except preabbreviated). TNUB\O)(l0-3;_  Transliterate the Never, Unit, Bool and Order to 0 to 3 respectively, transliterate the ) to ; for ease of matching, and delete the lower case letters and (. \d *  Convert to unary. E(1*),(1*); 12  Handle Either by taking the sum of the values. (P1*)1(,1*;) E122  Compute Pair(n+1,m) as Pair(n,m)+m using E to do the addition. P,1*;  Pair(0,m) is just 0. (F1*)1(,1*;) P122  Compute Func(n+1,m) as Func(n,m)*m using P to do the multiplication. F,1*; 1  Func(0,m) is just 1. }  Repeat the above transformations until the desired result is obtained. 1  Convert to decimal. # JavaScript (ES7), 103 bytes A regex-based solution. This is longer than using @hyper-neutrino's method, but not as much longer as I was expecting. s=>eval(s.replace(/\w+/g,s=>(i="enorpiau".search(s))<4?i:((x,y)=>y{['|1+','+','*','**'][i&3]}x)))  Try it online! ### How? All keywords can be unambiguously identified by looking at the second character. Hence the lookup string "enorpiau" and an index i into this string. We use the pattern ((x,y)=>y…x) for all operations.  i | keyword | translation ---+----------+---------------- 0 | N[e]ver | 0 1 | U[n]it | 1 2 | B[o]ol | 2 3 | O[r]der | 3 4 | O[p]tion | ((x,y)=>y|1+x) 5 | E[i]ther | ((x,y)=>y+x) 6 | P[a]ir | ((x,y)=>y*x) 7 | F[u]nc | ((x,y)=>y**x) # Julia 1.0, 87 bytes eval∘Meta.parse Never,Unit,Bool,Order=0:3 Option,Pair,Either=x->x+1,*,+ Func(x,y)=y^x  Try it online! Same idea as the other answers # Charcoal, 6661 60 bytes Ｆ⮌Ｓ«≡ιd⊞υ³B⊞υ²U⊞υ¹N⊞υ⁰p⊞υ⊕⊟υE⊞υ⁺⊟υ⊟υP⊞υ×⊟υ⊟υF«≔⊟υθ⊞υＸ⊟υθ»»Ｉυ  Try it online! Link is to verbose version of code. Edit: Saved 5 bytes thanks to @KevinCruijssen pointing out that d and p uniquely identify Order and Option. Saved 1 byte by finding a slightly shorter way to exponentiate. Explanation: Ｆ⮌Ｓ«  Loop over the characters of the input string in reverse order. ≡ι  Switch on the current character. d⊞υ³  For (Or)d(er) push 3 to the predefined empty list. B⊞υ²  For B(ool) push 2 to the predefined empty list. U⊞υ¹  For U(nit) push 1 to the predefined empty list. N⊞υ⁰  For N(ull) push 0 to the predefined empty list. O⊞υ⊕⊟υ  For (O)p(tion) increment the top of the list. E⊞υ⁺⊟υ⊟υ  For E(ither) sum the top two elements of the list. P⊞υ×⊟υ⊟υ  For P(air) multiply the top two elements of the list. F«≔⊟υθ⊞υＸ⊟υθ»  For F(unc) exponentiate the top two elements of the list. (Unfortunately the elements are in the wrong order, complicating the code. I tried processing the string from left to right which avoids that issue but that then requires an operator stack which ends up making the code much longer.) »  Ignore any other characters. Ｉυ  Output the final result. • -5 bytes by removing the split on "Or" and join on null-bytes, by simply using "d" and "p" as switch options, instead of null and "O": try it online. Oct 15, 2021 at 7:53 # Ruby, 120 95 bytes p=i=->x,y=1{x+y} a=->x,y{x*y} u=->x,y{y**x} f=->s{eval s.gsub(/\w+/){&}.tr'enor()','0-3[]'}  Try it online! • Thanks to @Dingus for the 25 Bytes saved! # R, 121 bytes Or R>=4.1, 100 bytes by replacing the three function appearances with \s. function(s,Never=0,Unit=1,Bool=2,Order=3,Option=function(x)x+1,Either=+,Pair=*,Func=function(a,b)b^a)eval(parse(t=s))  Try it online! R doesn't have a simple eval, you need to parse the string first. # Haskell, 206 bytes f.read data T=Never|Unit|Bool|Order|Option T|Either(T,T)|Pair(T,T)|Func(T,T)deriving Read f(Option a)=f a+1 f(Either(a,b))=f a+f b f(Pair(a,b))=f a*f b f(Func(a,b))=f b^f a f Never=0 f Unit=1 f Bool=2 f _=3  Try it online! # Pari/GP, 92 bytes Never=0 Unit=1 Bool=2 Order=3 Option(x)=1+x Either(x,y)=x+y Pair(x,y)=x*y Func(x,y)=y^x eval  Try it online! The same as @hyper-neutrino's and @wasif's answers. # Perl 5, 105 bytes s/\w(.)\w+/1/g;y/enor/0123/;1while s|([piau]).(\d+)(,(\d+))?$$|($4//1).({a,'*',u,'**'}->{$1}//'+').\$2|ee
`

Try it online!