Version française
Home     About     Download     Resources     Contact us    
Browse thread
Re: Okasaki's "Purely Functional Data Structures" translated to
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Pierpaolo Bernardi <bernardp@c...>
Subject: Re: Okasaki's "Purely Functional Data Structures" translated to

Hello,

   But you need not necessarily wait for the book to get the sources. The
   SML- and Haskell-version can be downloaded from his site at:

     http://www.cs.columbia.edu/~cdo/papers.html

Yes, I know this, thanks.  Still, I was waiting for the book so I
could translate the code while reading the text.

   It would be really nice to get your implementations of data structures.
   I have not yet come to the Random Access List, although it is certainly
   one of the funnier data structures: random access to elements of lists
   in O(log n) - I like that!

And they work very well with Ocaml.  A test that I did using only hd,
tl and cons was only two times slower using RALs than builtin lists.

The code is attached below.  I used Ocaml names (hd, tl) instead of the
original head, tail, etc.

Enjoy.

Pierpaolo Bernardi

begin 600 ral.tar.gz
M'XL("%\)IC8"`W)A;"YT87(`[5Q9;]M($O:S?D7#&$Q(FW%$QL>,9QP@R,P"
M`;+91;(/"P2!0%.43802)9)V*",_?JOZ8E^4*=E.@@7[P9:ZJZNKOCJZFJ3X
MX?6[%WM/W,CQ^&P\)O3_60C_"8FB4_J?MS$AIZ<GX?'X.(R."0G#ER_#/7*R
M]QW:357')2%[EVFYB,OILHNNJF^FZ:+.]OZ_V@>P?QGG1_/\Z=8(Q^/3;OL?
M@[%/T/['IR]?CL,3\(4P.CD]VR/CP?Y/WD;>`?GE[?2<,"<(;DEX%)+P]]]_
M>Q%&+Z*(C,_.Q[^=AQ%99FFYC,G?S5)\_(4<^*/1O)C>Y"FIU\N4?'C]_J]_
M_7/R^LV;OS]^G+Q[^_$_Y&)$2)5=C=#4E.99C&ME53VB?6F3I,LZ*Q;D'W&6
MWY0I*6:DJLML<66,OUW<PKSI)"ZO;N9@"F/X?5%/9L7-8DH88R`FZ7Q9K\FY
MLJ8828I%1=C(\U?MN/9%$E]/\=.Y22;'Z]PYKNF)=%DUL21"TLNBR%NJ17WM
M8)<MS%5OEM.X3COI'#*`K5]/IQG"A>#,9EF2`9"D6*9EC+T5610UF:954F:7
MZ128D64,@VAHL6R>+JY00GO=%MPR1<DDO*U,!K#3LEANTM64_M_4\8J\$`)A
MD]S*]'82+Y<IN$"7+=QBP,1NZPFBG3B#FR5QK4W:1#[+X[I.%[WIZV)"!VVA
M=+9E,5<(-_*+RS)>.QC2?IVC0LH^.GEF11T#$;<I_C,(YO$2QCWNL9>^#>NE
M8TJDSJ%_DPTS&8$%=Y%/)WDZJXG%+/:5*+ITA[V<'BK38WWZYHD.)>Y9/=G`
ML<RNKFO*\=(61=>A<WJ71#W`I7];L]>0-B2OFT56VQRP5YM@K>Z>IZVL,9D5
MY23.\Y8-IE:;`4VX<I-HH+?::@I?QA+7/543U['T@]G,T[E[*S.I5CW(XJHJ
M$DF'<AW0J%0%47E.[I]@\E_U95\M\ZSFZ%AD4H,#1X9(BOEEMK!V1PU#DRM,
MA@PO*YH/\6):S%\G25I5[UCR[*IOZO(FJ;42IR[3E%R0=VD\PX(&>KY!A3)-
M^9<#22,_.2HD8/`^RV'FAP*V99B)V=.8^M2UE#[P)EY`A3"YIINAPIV2Y6G-
M*RXJ=]M)BZV&K"E8V.9QG5S#]Z]9?<V[OA&/:NE5V5T:!G48M%^CH(Z",JUJ
MWP?W(4V%P3%JCX\9R(&S8%U*3NIKD([-#P_IT"'C0TW@-<B^CGS&4V&4YE4J
MY@74=DT`JTD1FPK]QD$@5852L3'4;'0UT:+`I(PS6,L3AMJ_GN[[+BC$*EQ]
MF-DXR5R:<7(I'-2INPE7YWV%PT];R:>@CR(B[3-N1Y)7)0G!Z16:EN,SW4>>
MM3[2*BP+[GYJ0QBGLF^"/;,8/*+E5Z8)#;T)UNA4Q*_DSF#M?0WN?,.S.4QD
M;!I0#&2^"W981<7=@-#F9A)D.P`,L921/R\X'0TD36/H"XF7/0^MN#')(DKV
MG'[S=0R1JH%U=O%%`Q3%Q6JG5S&%F+ZV.@2<Q%0$QY`3RH\TOL,!^.%+^L!Z
M:R^@W]9]78&M=[\WL-XU[WURUY!L#4Q:+R%K11`)L2J./57S'+)69\L#G[`&
MGXG>M-[)GVQDMW<I=8;I'35*MFFGX0OQ.9KCH>X//[EK>/'C>[^$.+X/%*;B
MH>!*LW^[[;/+``U9R,5`CWG\)27\$`H%!%;KB%D%EH3S)V.X"!BN59JG2=T>
M]F%Z?5WP7%/!9SA;0RT^1VIR!7W3-6``M=^RJ"A8=):<+C"@(G#C4+PO1D8I
M05Z!T%0$94/C5J.S>5UQR,S4AE>`N#C!&G$N4%4*O>:`#904[>H\=\R#1LL=
MU`#C8,+R?:7VS@,PE9HQ]`IMGZVT[^MS7!)B954RHVKQ!HC,-6>7PE/H%'$D
M0IS"FW,O+HWUH&(2`F62WP+H$àI$*?4-6T2E+F7WKEB,J$=:5F1`YB$ZS-
M!%P'+$G:RMMI.'24,YM3-(JT[W^?W5BJKR1:SUT,N79I=;J>;#5W=Z1;.M,N
MY5UH-Q6'6[H(@I+E03_X;",%6:^MO74-3+V&0A0#2J'O\`Z5C:_FY4<)"T\X
M2I:3N;:`=<!AX6\;XSBX2!L\W"6'R:%F<%"(#KVB<U`E11(/^IXGP:?DLZ\E
M),.E/%0L0*W@F'3!9*!,D:7I7%P0BH6Q',&4@^/GYXR9B2),3\BKKKF*%,9$
MFPZT2HQ5I*`H)-AXK"_!G,=YBFVE`X.8\SY]'CD$Z8(M!!8*8LS5J;Y&<AZ+
MK5#-S2%VAEPOI7_B]'[F1/NN6E.YKEV3W(B\VEEDT@CCQ^Z\*R7Y[,QCK`#Y
MP.J#%".8^8:$"ED>DCPRQ(,^5V&11^Y`;^6Z7Z0\TD2Y5:!1A>K80)X,4$[D
M::N$QO?(!O(I0#1E4):/C.7%K0<3CMRY-&(JNF@'Y^Q=@P:P%0EN7IWKFO(;
M(A=B/8=EQ$V-FL1)TM\XS?DYT&\T34/.SXTUA&%D1X2K*@*+@=S*[G4!NFDR
M.C%34&OEN\]FFGRPCA!+%DUL<4AGNA'EC9[<O1GUE/?39X>X`#"[\L980>$J
MDH(N&AWU\(KI$8U*GUT4U"!E]XO*6!<33A&8>OE9`N\)*+L`&V3YG'SZ]JTS
MD]\"V6OD?T3K29R';@G\?#6;2\RRG"*6*9AU0J,8\U;K=!O3J"/HUI^A\\.:
M]!)NAA;.%@:=$`EHZTB.X<%!G>B0MK:E54/D]LB#$NK/YZ3Y@V2'H4YGQXLA
ME3+[7KT\8.]WZD9)=.7`;X368S15ZRW*K<98\Y:%M#/WF+A=34LH"H=IS"I#
M,P+8=1P]"$)YE28^\J:Q>H1:F.C02[]Q/MM0RA-^T8,Q"PQ8Z,5_0UB@0Q21
M;U]RI!5SK%)*RP15@F!8."3N5-#F>R,5,+>',Y$#:>B5F0)D:WPK2<C2V2=C
MQTY`;QV;)G,;3#77-!YU&*J'F9B1IG&@B*`:PNC6`6\O/.-XQX'@29`74#T8
M<[P;/R-U_WV7?O3PF[GWENJVQKIFI`RT=4+]JUF5L.[M:Y*.O57I-:7H$$!0
M190,]V'CX,NX.^$!KNQ#I`,58H\%%M[S0EZAS^^5E!'TX*TO*QM++$,"1(:,
M(&1H=D8HN;+FI/N"$4[9MZV`;%REJ9>'06[ICZ=\<5VJPRR*ND2[TR=5_DHO
M-FGW]3045%YN#'JH;QTA;>NW3XF`[?I%!KO"@>39QJ"P^'MV#W(I<2_U<;_4
MRSV%[JYGE-S=%R.;Q;FS!%&>@J&1JC/@YP%Z#-B$;<1Y/RC"D`6-KDW!1>Z+
M+ELPS]&%:]'X\X6_^<+1^H299&;&FH'(;C%W]S01=Q\H=[V@Z!MR['$FW(ON
MMHFY3-7>$7,SO!SM6"5T]D;DSG=92!#DEG`[AIU;(EN8$3ZQ^U^C&=%()_!P
M'!WX&P%N-[:[AP0>#3L'\ML$'M_0+#LH.=T]QGR-6JIOZ+')^YVF;?>[NY\E
M^C:AT@7(CO%''][;J@J<V<\AE.ZC)%CY#U,KL5[8.6+L?+R[WY;G^:/>Q_1N
M<3HDD1,>H4*</<+NQ8/(":3B,MWC_?<P.L4,(<%GMXW+;:I'BIT-$/30OM>V
MQ9X^?6CD-/I^U9!??[46"%V=5GTH1OH%BO;\T^9]2I>C6P1*SI^P?718BM+D
M'SKZ#(GD0#],V!-@?4`QI.@40$7PZ9)&8R>-9D/28/NWX5+J%N,:VJ;<9;/L
M#5=RVRUA=+GLHVVW+B#Z8=!Q=])Q4UUQ'^D0/X4_Z,&DHN`8Z>\-?)+I#"VO
MW7RA,U0?R1F<*/0"H,?>@<_P][^Z0.5M0-;,#@+U-*0CPLR>R<RUB8M)*[(<
ME[--M+S#2'*L][%3K+JX>UU!MMH!S$="<ULX5Q:>*S>@JQ^'*/N-1T](O2]!
M)O#X`M[5T!]^&403Y2$@^7,#$R_*20?8Q=!%;(3OVM!#O?F%*B@_>9#WS06M
M`8CHCTU;Q/F&!TX=.MY_%ME.ZBZ!A:%WLB+P99!O8QN7[YOF<8BE!4$G_NI8
M7QML%1"&0)MD$>99[1@;CQ\<#XR.5?_@6+EC8_6]0V/5*S)67=9COS'K9SQ\
MRI&=4\6CH.PI?NMN#J5TBTX?-J/U"%XGO="$4+7`V_T>U!2T0C'H(OV>I7(^
MTBN\=5OBZ)HS/CTOGX@:J[]Y-NI(-BC9H9^VGEW)=6E)EQ6_!'R4NW?0Z[AW
MMU5M+1R$<@I,&=6[=[)WB]MW?(Y96@M6/_TM/`N)/B"XRFO\)>?>T/J__R7[
M0>]_(<<GXPC?__+R[/0X.CZ)\/TO9]'I\/Z7'_#^E\S]`IBS\VAX`<SP`ICA
M!3##"V"&%\`,+X`97@`SO`!F>`$,JV^&0\;0AC:TH0UM:$,;VM"&-K2A#6UH
I0QO:T(8VM*$-;6A#&]K0AC:TH0UM:$,;VM"&-K0?U/X']A<7(`!X``"A
`
end