Re: Okasaki's "Purely Functional Data Structures" translated to

Re: Okasaki's "Purely Functional Data Structures" translated to

[Markus Mottl]

Hello,

> I have translated the Random Access List structure, and have
> written equivalents for most of the Ocaml list library functions.
> 
> If you wish, I'll send what I have done to you.
> 
> I would have liked to translate more of the code, but I am still waiting
> for the book to arrive (I have ordered it several months ago).

As it seems, Okasaki's book is out-of-print at the moment - by some
miracle I was able to get one at our university book shop.

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

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!

Until now, OCAML's standard library only contains the most basic data
structures. I am sure many people would like to see some more to choose
from.

As someone has already mentioned, the interfaces of the modules in the
sources are everything else but "fat". They support basic functionality
only. But it shouldn't be too difficult to add some further functions
to make things comfortable - the really tricky things are already mostly
implemented (though, hidden behind module interfaces).

Porting the sources is not difficult - should be possible for people
with basic knowledge in OCAML. I have not yet used SML, but it's (nearly)
always clear, what has to be changed.

Regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: Okasaki's "Purely Functional Data Structures" translated to

[Pierpaolo Bernardi]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 5448 bytes --]


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

Re: Okasaki's "Purely Functional Data Structures" translated to

[Markus Mottl]

Hello,

> >   * A somewhat bigger change: the type of the list is not:
> > 
> >       type 'a ralist = Nil | Root of int * 'a tree * 'a ralist
> > 
> >     but now:
> > 
> >       type 'a t    = (int * 'a tree) list
> > 
> >     I think that new users will understand details of implementation
> >     easier with this change. It also comes closer to Okasaki's version.
> 
> Okasaki in his paper on RALs presents both versions.  The one I
> used is faster for Ocaml, so I suggest that you use the version I sent.
> Users should use the book or the paper to understand details.

I haven't read his paper, I just know his book - there is nothing about
the second possibility in it (maybe I have overlooked it).

Anyway, I have compared performance between the two (just for some
common operations). Your version was about 3% faster - not really much,
but I added it again to the repository and renamed the former version to
"sb_ralist2". This should satisfy both the speed-hungry and the advocats
of elegance...

By the way, chapter seven is now available, too. And I have made the
necessary changes so that "PhysicistsQueue" (chapter six) works.

As always:

  http://miss.wu-wien.ac.at/~mottl/ocaml_sources/intro.html

Best regards,
Markus

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: Okasaki's "Purely Functional Data Structures" translated to

[Pierpaolo Bernardi]

On Thu, 21 Jan 1999, Markus Mottl wrote:

> Although this implementation seems to be quite perfect, I have allowed
> myself to make some very small changes, so that it can be immediately
> used as a module and fits better to the way modules are implemented in
> the standard library.

Good.

> The following changes should be noted:

>   * The type of these lists is not "ralist" anymore in the module but
>     "t". This corresponds to the way this is handled in the standard
>     modules.

Rigth. 

>   * A somewhat bigger change: the type of the list is not:
> 
>       type 'a ralist = Nil | Root of int * 'a tree * 'a ralist
> 
>     but now:
> 
>       type 'a t    = (int * 'a tree) list
> 
>     I think that new users will understand details of implementation
>     easier with this change. It also comes closer to Okasaki's version.

Okasaki in his paper on RALs presents both versions.  The one I
used is faster for Ocaml, so I suggest that you use the version I sent.
Users should use the book or the paper to understand details.

>   * The rest of the changes concern mainly layout (hardly noticable).

De gustibus...  8-)

Cheers,
Pierpaolo