I have the following setup. $<>$ is a sequence. $()$ is a tuple.
$A_1 = < B_1, B_3 >$ where $B_1 = < C_2, C_3, C_4 >$ and $B_3 = < C_5 > $
So $A_1 = << C_2,C_3,C_4 >, < C_5 >>$
$C$ is a tuple of the form $(C_{index}, 1)$. $B$ is a sequence of $C$'s.
I want to write a recursion that takes an $A$, say $A_1$, and returns
(1) the number of $B$'s in $A$ (in the example above, this is 2)
(2) the number of $C$'s in $A$ (in the example above, this is 4)
(3) to flatten the sequence of $C$'s in $A$ (in the example above, you should get a sequence of $<C_2,C_3,C_4,C_5>$.
In my book they have an example, which is what I am trying to use here.
Entry == Date x Course x Location x Professor x N (N = natural number = number of students)
Table == seq Entry
To write the recursive function of the total number of students attending all courses we say: $\forall$ x : Entry; k : seq Entry $\bullet$ total (<>) = 0 $\land$ total (< x > ^ k) = x.5 + total(k) This makes sense but in this case we simply have this structure: $x = < (tuple1), (tuple2)... >$ so x.5 can be simply extracted.
My ideas so far: (1) Won't the cardinality of the set resolve this? (2) Typically I use x.2 to identify the second element of the tuple and then recurse over it but this won't work here. (3) Not sure how to do this.
For 1: Sequences are not the same as sets, so while the basic idea of taking the cardinality is good, technically it's not something you apply to a sequence. However, what the idea does correspond to, is the length of a sequence. Also, I thought you had to provide a recursive function? So how about:
$Length(<>)=0$
$Length(<B|S>) = 1+Length(S)$
(in here, $<B|S>$ means a sequence whose first entry is $B$, and where the rest of the sequence is sequence $S$. So, for example, if $S = <1,2,3,4>$, then $S= <1|<2,3,4>>$ (this is standard notation in LISP or PROLOG))
For 2: How about:
$Length2(<>)=0$
$Length2(<B|S>) = Length(B)+Length2(S)$
For 3:
$Flatten(<>) = <>$
$Flatten(<B|S>) = Concat(B,Flatten(S))$
where
$Concat(<>,S) = S$
$Concat(<C|B>,S) = <C|Concat(B,S)>$
Note: using the $Flatten$ function, you can do the $Length2$ function also as follows:
$Length2(S) = Length(Flatten(S))$