[Challenge] implementing the ambiguous operator in D

Philippe Sigaud philippe.sigaud at gmail.com
Mon Sep 6 14:34:04 PDT 2010


Peter:
        I must be missing something, because I don't understand how you
        could possibly take the cross product of any number of infinite
        ranges (other than to just return the range of (a[0], b[i]) for
        all (infinitely many) i in b).


The trick is to iterate diagonally. Me, I'll use tensorial product :p
Say you have: [0,1,2,...] x [0,1,2,...]

The tensorial product produces a range of ranges:
[[(0,0),(0,1),(0,2),(0,3),...
,[(1,0),(1,1),(1,2), ...
,[(2,0),(2,1),...
...
]

The standard cartesian product just iterates in the first line and will try to
explore an infinite row.
The trick is to iterate along the secondary diagonals, like this:

0 1 3 6
2 4 7
5 8
9

Which gives us: (0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3), ..
See the indices: sum of 0, then sum of 1, then sum of 2, ...
You never get stuck in an infinite line since these diagonal slices are finite.


Andrei:
    We've discussed this before. Crosscartesian product of multiple infinite
ranges can be easily done by applying Cantor's trick for proving that rational
numbers are just as numerous than natural numbers. Google for "Cantor" with
"site:digitalmars.com".



Ok, I think I solved this particular problem, if only for infinite ranges.
It's in three parts:

1- A memorize(range) struct that slowly looks ahead in a range, store the result
in an internal array and so slowly transforms an input range into a random-access
range. I tried this a few months ago, but got stuck in trying to propagate
properties (bidirectional, etc). Now it's just an input range. Much easier. It's
related to Zippers (in functional PL).
2- Generate the indices of sum  = 0, then sum = 1, then sum = 2; etc.
3- Just take the corresponding indices in the input ranges.

example:
a = memorize(cycle([0,1,2,3,4])); // to make it infinite.
auto dp = diagonalProduct(a,a,a);
 // -> (0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,0,2),(0,1,1), ...


entire source code attached (I hope it works). Now, I still have some problems
with finite ranges in the mix. Nothing crucial, but it's getting late.

Philippe
begin 644 infiniteproduct.zip
M4$L#!!0````(`!B[)CT"TUP_F@```.4````&````;6%I;BYD58[+"L(P$$7W
M at O\PRP0&J?6Q*?Z#>W$Q)+$-)ID04T7$?S>M*.T,LSESN%SK(Z<,MZQ7Y2PW
MR\4$D6LYV=SY.4X46E/0'\;$NE=Y1'>V&CS9("2\!@!EJ,\,!`=03^6,.%6X
MQAHWN,4=[L^RF5 at Z%DU;:CF0.WZ#!6'9GW;A9$AUPCCC&\AT-4)'A+J2$AZE
MKG%A_`W^>VCP`5!+`P04````"`#RNB8]=*T:)9\'``!,10``"0```'!R;V1U
M8W0N9.T;74\;1S#/E?H?SE+5F`1,T\>ZI*5*6D7*1T61JLA""/`97(Q!V$`)
M(K^]M]>9G?7LQ\V<UZY:]6'DN[W=V?G>V=GUDR=/+BJXK&!8P4T%DPK*"@KX
M5CI]KBNXKZ!?P9<5?%'!&+Y?.7WF,'YFG@%W#[X=53"MX-3 at 7@*7>;Z'OB6\
MW\#[)#/N$Q at SA;Z$EWZW*WA6`[7M$GZ:?U'&ODP83=?`UPG2"[]G]3AJ.W'P
M%##')<`YM!W!N!*>A]`^AG'SNC_UG<+[W!EWW4#WG<&'8Q`7_/8"=.WZ-)'M
M63QDHYL+\B%=CI$6E+\=2[3=PAP3D&DIX!^?KQV>[PTO\.TCC+D)ZX%HL&VD
MN]NZG>8X,0!MLQH(QZ6/S]<SM`]C^D[(8>;*`IX_5-"MX$4%&S at _VG*#SB_!
MUM\`OB'T_[.6'>GHIUJ>I-.;B!S&3%XG#@^3D*R$MK9)?%,\<,;>F6>BD6*!
MI8=BR<RS'9+G%?`V#_F/P!;YF*'Y#GK82MN//Q?3P;,*MO&](?:\XVL"T/S)
MM(.][*&]P+<1/'?-.^!_$Y#+7H#.#L.W;<##37CW(C+:#<DG-6?"-LX<GY\X
M?O4'M,UL?[+1L7F.V.F>(_L'Y[E@\!K7#NM_9"O[N&8Q'@85'$36\WY`IK\S
M'_/Y)![+ at +WO&AJ0#JL'\I--EW^`7H+G/8>6&XS#C/=^>#S%2[0/M,^H7Y"=
M/0CF-=]WS&\BMWE$VA(T'CNRF-1MI*<K)Q_I.O3]"-^N,=:R6'2_P`?1/G?X
MF4;LHN?-3_B^-B"031`'RB2SC9MQ(Y0%]E^AO+IF;H7<D(8?XO+VZ8>^WPEE
M[8T7R/H6^H\=W[YRY/-S9IG6\7I)&3[$9"B at _6]YD']-,(XI?%XSC\3WMPG\
MO!;7*I8'3*']3IC7VC at HV-O%\MH+OK;!;\G:1A:?GP^_=?,Q9DO'!A<;7RZN
M-Y3CLW6YI[1Q25ZHM?/@_.GUG""D$VC[7,&.T"Z]&!!9XS^8?AG6<BE?)QG\
M*3A72Q_COO#>]3UHOR*_HSP?[=#21WN=D<*V5F&O[\%F9RP?/T3?!'HW,MGJ
MG<VK:+WNIOR=YP_0YV4%WQBZ%'-KZ+2 at D"7Z?G^)>;8`IDH\CTO:^D(NJ8S!
MZXISJ=RJ(X at 77GZP@AB!-C%A<B@$,HKZ=](__?C_UN']%.-6"YU)\]I03C4)
MT:#8V[3-YZ/U(T&<&V>,<U[]`IZ_;R&S4`WC(^CA`N!>09N&#XT/<IX&P/=!
MQEAF(92/-\A^QT`F^4^P+L-JZ6<8,^&]]&K/M/9->+UTC>M94(_"O&NDS+5R
MZW?!#RP?)/^.^<9D^WZ-LD5[VVII;QI9<C at RNN.U?[;V%<*]P3)T)'-SFW?Z
MM&T:^67(HZ+VS>=<@TW;;\&US\\AAKA'13UB7T$=W5T++Q0U=VE],V==7E*[
M#NI1>*;0X3PF>.LK=?2+XRLEX:7:AK]GI-H*Z9C.%0)[PAFN\?#^U&V#]\U0
M_83P4^X4V8.^PG[(:R)'&K#^!WA.(.#MK6,K<T$NYLZS(>AOY:*P+0V?V+\$
M&";B@]_7Q[E5P0L']TZ`CWY+O_#/G7WY=Q@]74ZSTB^:]CZCFD[*B^:N+6:P
M/0G/W8PVMT!/BHYX[*3Q=F]`=O!"8<<I6QA$:#J(Z5:Q%FED\U_3U<L6>M+0
M9^7EUO/Q3%60GS3L<VFLHD8W=NVTX8[+L7.WX#SCOEHJ0QY?9]!^Y.Z]&O at 8
M0(VQ!_`5X/T6\'XV<HF.]?L_;YG;:G-ZB7]!;N3+C/S)EUD+VA?.9:Q-4#VJ
M9'6>?HB_->[=I/:UZ)M4"Y at Y=!\[O`U='7&^\<P&XXW"KW"?6;2T+0OI6$-G
M2BWXUM"CJ0T\-R"(9X\MUTY)W'T4WNG<!UF=+^3[_GVO$3[CNIN\\^G?'1NR
M^M0G at X?=13MML7<91^K8PX6[7C3VV)GO*>81,,\IYGT46^C^'.X=V+GMTR7N
MGKUJF/O7*#^T?^PAQ'($%B=_LS*EN#L"F71:[ITW<2_+S\0RS.W9'9]3D>?$
M[J[M\[O62`_IC^@&';R#MBOLJSP;J/?'C(>BQ7EQD"<EW8EZA4\K/?L^'Z,U
M-09C2`M\TGUW&QP#0V^Z'NK7&;RS'3^_Z?/]C/#,$W&\5IX5INX+'L;DGC$O
M;LJSQF!?ATZ.M;=$7E7+5#`F>2Z6E at V='RGN=R7T1_D76RM*1R;'3(;G at OMP
MA2"G2O*'M"GJME*Y:?-!#9\2/ZSY:E$?K&.F(#;`7H7BD(!GRZ/`GH/Q?47K
M?V(-)G]5^FPM,Y2-\MZPJ[L1\H>YOC#&+IS?"?I+8G2..\Y:.G+$ON!>0Q"W
M)'*6V+C]'LN!,MZ)SK&F1>E3QK1UKXV%$D;.&>38\9FA&\L%_QO at L7\@C-%8
MYSIPQZ_XWD;0%X3Z_:?OIN>P;8E>EKWC6 at CN)$EH\.+MFGUCU;Z[BEB?E+W0
M?WL-=S`W5D#G,KHJ!#XOX;GM7=M<,GA<`<YE\Z!"H;=<."T(<I3 at WDJ1)RX+
MWKYM1?-JUKB<8Y\;4-1;"H$NI__"O9M&ILE[5TO6A3O\/\N"&G>;.G/3O:S9
M__7HQGIT,-?,<#8 at O5\V2]VE^0M02P,$"@``````B6F).$;]QUXZ````.@``
M`"````!!<F-H:79E(&-R96%T960 at 8GD@9G)E92!J6FEP+G5R;%M);G1E<FYE
M=%-H;W)T8W5T70T*55),/6AT='`Z+R]W=W<N:GII<"YC;VTO87)C:&EV95]L
M:6YK#0I02P$"%``4````"``8NR8]`M-</YH```#E````!@```````````"``
M````````;6%I;BYD4$L!`A0`%`````@`\KHF/72M&B6?!P``3$4```D`````
M```````@````O@```'!R;V1U8W0N9%!+`0(4``H``````(EIB3A&_<=>.@``
M`#H````@````````````(````(0(``!!<F-H:79E(&-R96%T960 at 8GD@9G)E
@92!J6FEP+G5R;%!+!08``````P`#`+D```#\"```````
`
end


More information about the Digitalmars-d mailing list