Screwing this up a lot so perhaps I should write the formula down :)
First the idea: an array length N has to be indexed by a value of type N.
If N is a unitsum, for example 3 = 1 + 1 + 1, then the values are
just 0,1,2 (mod 3). Note, these are NOT integers, they're things like
case 0 of 3
case 1 of 3
case 2 of 3
You know type 2 -- that's just bool (and the members false
and true are just aliases for case 0 of 2 and case 1 of 2).
If the array has length N * M, it's a matrix, and the index is a member
of N * M, that is, a tuple (i,j) where i is type N and j is type M.
If an array has length N + M it is the joining of two arrays, length
N and length M. So naturally the index has type N + M.
This type has two cases:
(case 0 of N + M) n // where n in N
(case 1 of N + M) m // where m in M
in other words, you first choose which array to access,
then pick and index for it of the appropriate type.
Now, our array here is linear, but the indexes are structured terms,
so we must linearise them. The formulas are simple (despite the fact
I keep screwing this up .. :)
We first need to define a size function.
size (unitsum N) = N
size (N * M) = size (N) * size (M)
size (N + M) = size (N) + size (M)
So the indexing function is now:
index (case i of N) = i // unitsum
index ( case i of N, case j of M) = i * size N + j // tuple
index (case i of N+M (j)) =
if i = 0 then j else size N + j
More generally, for a tuple i0, i1, ... i(n-1) the index is
(i0 * (size N1) + i1) * (size N2) + ... i(n-1)
The standard formula for indexing a matrix rank n.
For sums, the formula is the sum of the sizes of the
subarrays of the join preceding the selected on,
plus the index into the selected one.
So we have a conversion from an indexing term to an integer
which is 1-1, i.e. maps a complex index to a simple linear
index.
We can (and must I guess) be able to go backwards too,
from the linear index to the complex index term.
The tricky thing is that whilst the sizes of the unitsums are
(currently!) known at compile time, of course the case
numbers are not (they're variables at run time).
So we don't want an Ocaml formula for doing the calculation,
we want one that *generates C++ code* that does the calculation
at run time.
--
john skaller
skal...@users.sourceforge.net
http://felix-lang.org
------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
