tag:blogger.com,1999:blog-2564777502681463717.post4783688804692941885..comments2023-12-31T10:17:57.560-05:00Comments on Teaching, Playing, and Programming: Ten Years of Purely Functional Data StructuresChris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.comBlogger35125tag:blogger.com,1999:blog-2564777502681463717.post-64125293636822981982023-09-10T19:40:47.656-04:002023-09-10T19:40:47.656-04:00Hi, Chris.
Thank you! That helps. Sorry for the...Hi, Chris.<br /><br />Thank you! That helps. Sorry for the newbie question. Thank you for your answer.<br /><br />Jeff Kayserhttps://www.blogger.com/profile/00375791643417429076noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-68451014199852817192023-09-09T17:54:13.851-04:002023-09-09T17:54:13.851-04:00Jeff,
The type variables in SML are often written...Jeff,<br /><br />The type variables in SML are often written as Greek letters in typeset documents, but in ASCII code they would be written as 'a (instead of alpha), 'b (instead of beta), etc. Arrows are written as -> (in types) or => (in lambdas).Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-66801644993126855392023-09-09T16:21:02.683-04:002023-09-09T16:21:02.683-04:00Hi, Chris.
First of all, Thank you for writing th...Hi, Chris.<br /><br />First of all, Thank you for writing the book! It is important. I want to work through it, just to learn the concepts.<br /><br />I downloaded and installed sml/nj on my Fedora VM and tried to enter the signature for a stack (Figure 2.1). I didn't know what to substitute for the alpha character, so I just substituted the word "alpha":<br /><br />$ sml<br />fgrep: warning: fgrep is obsolescent; using grep -F<br />Standard ML of New Jersey (64-bit) v110.99.4 [built: Sat Sep 09 12:13:22 2023]<br />- signature STACK = <br />= sig<br />= type alpha Stack<br />= val empty : alpha Stack<br />stdIn:3.6-4.4 Error: syntax error: deleting IDA IDA VAL<br />- <br /><br />Some questions:<br />1) How do I resolve that error?<br />2) There are some non-ASCII characters in the book. Example alpha, arrows, etc. What should I substitute for them when typing the code into the compiler?<br />3) Should I be using a different SML compiler to work through this book?<br />4) Should I work through the book using OCaml instead?<br /><br />Thanks for your help.Jeff Kayserhttps://www.blogger.com/profile/00375791643417429076noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-22953627908200916102019-01-06T17:55:24.922-05:002019-01-06T17:55:24.922-05:00Hi,
I found a errata in your book page 145. in th...Hi,<br /><br />I found a errata in your book page 145. in the function update (match clause about ZERO) was written:<br /><br />fun update (i, e, ZERO ps) =<br /> let val (x, y) = lookup (i div 2, ps)<br /> val p = if i mod 2 = 0 then (e, y) else (x, e)<br /> in ZERO (update (i - 1, p, ps)) end <------------- here<br /><br />the i-1 should be i div 2 , which I can confirm by making a scala code, and/also by checking the fupdate in the next page.<br /><br />Regards,<br /><br />Frank Hyunsok OhHyunsok Ohhttps://www.blogger.com/profile/01408999472890865034noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-56664268831283033032016-01-05T05:32:56.264-05:002016-01-05T05:32:56.264-05:00What's new in purely functional data structure...What's new in purely functional data structures since Okasaki?<br />http://cstheory.stackexchange.com/q/1539/https://www.blogger.com/profile/06835703169605180863noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-41337340240494851402016-01-04T07:41:10.252-05:002016-01-04T07:41:10.252-05:00This comment has been removed by the author.https://www.blogger.com/profile/06835703169605180863noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-69319935762782993892015-11-16T15:33:04.743-05:002015-11-16T15:33:04.743-05:00Alexey Filippov: Thanks. That does appear to be &l...Alexey Filippov: Thanks. That does appear to be < on page 133, but the version on page 134 shows the <=.Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-86055835465195096562015-11-15T12:12:16.945-05:002015-11-15T12:12:16.945-05:00I am trying to get through your book, re-implement...I am trying to get through your book, re-implementing the examples and doing the exercises in Scala. As I’m doing that, I’ve encountered a typo which is most probably already known to you — but if it’s not (and since the books is seemingly printed on demand theses days), it won’t hurt sending it through:<br /><br />On page 133, the source of lookupTree contains the following clause:<br /><br />if i < w div 2 then lookupTree(w div 2, i - 1, t_1)<br />else lookupTree(w div 2, i - 1 - w div 2, t_2)<br /><br />It’s easy to see that since the index in the tree is supposed to be from 0 to w - 1 (inclusive), the initial comparison must be i <= w div 2, lest the logic falls apart.<br /><br />The same typo repeats in Figure 9.7 on page 134<br /><br />Hope it helps — and thank you for the great book!Anonymoushttps://www.blogger.com/profile/13208800385701081197noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-5600411560847519112014-06-14T08:55:35.449-04:002014-06-14T08:55:35.449-04:00STARRY: No. However, many people have posted solu...STARRY: No. However, many people have posted solutions to some of the problems. Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-47235553744935553992014-06-10T08:19:38.024-04:002014-06-10T08:19:38.024-04:00I have been reading this book recently. It is real...I have been reading this book recently. It is really an insightful book. Thank you very much, Dr. Okasaki. Is the solutions to the exercises in the book available for download?STARRYhttps://www.blogger.com/profile/16814037505220054868noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-49006098008370056912013-06-10T11:01:08.659-04:002013-06-10T11:01:08.659-04:00why not LISP? a canonical language survives decade...why not LISP? a canonical language survives decades.Anonymoushttps://www.blogger.com/profile/09118109916964096210noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-15495599739333765712013-05-17T14:40:30.984-04:002013-05-17T14:40:30.984-04:00Chris, isn't it much more of a leap to pretend...Chris, isn't it much more of a leap to pretend to have lazy evaluation extensions in ML or OCaml than it would be to use the real world facilities Haskell provides for specifying lazy vs. strict? Have you thought about contacting Simon Peyton Jones about some of your concerns to see what his thoughts are? I agree with some of the other commenters here that a Haskell edition would garner a much larger audience, again citing the success of Real-World Haskell.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-5061418573857158372013-05-14T08:48:11.521-04:002013-05-14T08:48:11.521-04:00@test4242: Interesting. I had not heard that abou...@test4242: Interesting. I had not heard that about the SML/NJ library.Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-82405435273657533682013-05-14T07:06:49.825-04:002013-05-14T07:06:49.825-04:00Hi,
it is really a wounderful book. And it is rea...Hi, <br />it is really a wounderful book. And it is really nice to read why<br />you did not include the delete method for red-black-trees. Are<br />you aware that the standard library of SML/NJ had a bug in delete<br />operation that resulted in completely unbalanced red-black<br />trees (more a linear list :-)). This bug can be trigged even with<br />very small test cases, see, e.g., page 16 of "A.D. Brucker and<br />B. Wolff, On Theorem Prover-based Testing. Formal Aspects of<br />Computing. doi:10.1007/s00165-012-0222-y" for an example test<br />case that triggers the bug.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-14853562206499289852013-05-14T03:08:18.532-04:002013-05-14T03:08:18.532-04:00If you'll do another version, I hope you use S...If you'll do another version, I hope you use Scala instead :DYtzvan Mastinohttps://www.blogger.com/profile/02839427927798159628noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-55498365438650126302012-08-23T14:54:26.193-04:002012-08-23T14:54:26.193-04:00Do another version!Do another version!jsalvatihttps://www.blogger.com/profile/16509764680257537430noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-27227442118353085942012-05-30T15:22:48.859-04:002012-05-30T15:22:48.859-04:00Is there an implementation of the lazy notations u...Is there an implementation of the lazy notations used in the book? (the $ and lazy/force keyword)Ning Kehttps://www.blogger.com/profile/04382088443772501731noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-51742947610914958532012-05-21T18:50:13.592-04:002012-05-21T18:50:13.592-04:00I'd love to see a second version. One of the l...I'd love to see a second version. One of the languages should still be Haskell, maybe the other could be Scala?<br /><br />I'd also like to see a section on graph data structures including a discussion of hybrid functional / imperative implementations.George Colpittshttps://www.blogger.com/profile/15526399395097722268noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-54555707471739971212009-02-01T10:40:00.000-05:002009-02-01T10:40:00.000-05:00I agree with caracarn11 that your book can help a ...I agree with caracarn11 that your book can help a lot on a way form imperative to FP world. <BR/><BR/>Being an imperative C# programmer, I have always been interested in FP, so reсently I started to play with F#.<BR/>I found it very natural way to functional world for .Net programmer. <BR/><BR/>Luckily, <A HREF="http://blogs.msdn.com/dsyme/archive/2008/12/10/fsharp-to-ship-as-part-of-visual-studio-2010.aspx" REL="nofollow">F# is about to be next mainstream language</A>. <BR/><BR/>I guess, F# is a language of a choice for Second Edition, since all examples can also be cross-compiled with OCaml.Alex Slesarenkohttps://www.blogger.com/profile/10253205349391319347noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-24743516093393005962008-06-12T17:48:00.000-04:002008-06-12T17:48:00.000-04:00First let me say thank you for the book - it opene...First let me say thank you for the book - it opened my eyes on what's possible.<BR/><BR/>Second - I imagine legions of developers like me will thank you for a fuller treatment of hash table, either in an updated edition or blogs.<BR/><BR/>The reason is - hash table is almost indispensible in many developers' day jobs since the internet revolution. The swiss army tool of data structures has shaped many developers' paradigm and it's simply difficult to see how things should and could be done otherwise. <BR/><BR/>While not everyone of them are interested to enhance their skills, a small portion of this group are interested to learn the FP way, and it's simply hard to go from one paradigm to the other directly without a good bridge. <BR/><BR/>A fuller functional hash table treatment, or a set of design principles to convert a imperative solution into a purely functional solutions would be *the* bridge for many of us who rely on hashtable every single day.<BR/><BR/>So - maybe academically there are not much more to say about hash table, practically there are a lot to learn for us who are on the other side of the canyon looking over ;)ychttps://www.blogger.com/profile/11915946249340014269noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-73139105426687939682008-02-27T17:36:00.000-05:002008-02-27T17:36:00.000-05:00Some of the more interesting algorithms (to me, at...Some of the more interesting algorithms (to me, at least) in Dr. Okasaki's book have fleshed out OCaml implementions in the Cf library of my hobby project on sourceforge.net. You can download <A HREF="http://sf.net/projects/ocnae" REL="nofollow">here</A>. There's also an impure, but still functional, persistent real-time, catenable deque that runs pretty fast. It was inspired by Dr. Okasaki's work on the more complicated purely functional variant.s9https://www.blogger.com/profile/08326725206530909278noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-18085881025213151372008-02-26T23:08:00.000-05:002008-02-26T23:08:00.000-05:00I've liked Purely Functional Data Structures for s...I've liked <I>Purely Functional Data Structures</I> for so long and for so much that I made it the subject of my first (and so far only) book review: <A HREF="http://bakins-bits.com/archives/4" REL="nofollow">Persistent Data Structures - now (possibly) practical</A>.<BR/><BR/>I have just started on a Python implementation of the data structures. It would be a good language for a 2nd edition - popular, easy to read/understand (even if you don't know the language that well), and has the functional programming features needed (closures, polymorphism, GC).Davidhttps://www.blogger.com/profile/09358968282816697343noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-40106728487263918862008-02-14T11:58:00.000-05:002008-02-14T11:58:00.000-05:00kHodel, thank you! The second link lists Flying G...kHodel, thank you! The second link lists Flying Geese as an alternate name for the pattern, so maybe that's why I was originally confused. (Flying Geese is usually the name for a more linear pattern of triangles.)Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-89209888045130357362008-02-14T11:51:00.000-05:002008-02-14T11:51:00.000-05:00I did some Google-digging, and it looks like the i...I did some Google-digging, and it looks like the inspiration for the book cover image is a variation of a quilt pattern called "Birds in the Air" (though it may go by other names as well). Here are a few links<BR/><BR/><A HREF="http://www.how-to-quilt.com/patterns/birdsintheair2.pdf" REL="nofollow">birdsintheair2.pdf, from how-to-quilt.com</A><BR/><A HREF="http://www.how-to-quilt.com/patterns/flockofgeese.pdf" REL="nofollow">flockofgeese.pdf, from how-to-quilt.com</A><BR/><A HREF="http://www.onestitchatatime.com/images/BookbirdsintheAir.jpg" REL="nofollow">cover of a birds in the air quilt book</A><BR/><A HREF="http://www.amazon.com/Birds-Air-Quilt-Eleanor-Burns/dp/189177607X" REL="nofollow">the afore-mentioned book on amazon</A><BR/><A HREF="http://www.amishcountrylanes.com/Pages/hs140.shtml" REL="nofollow">picture of a birds in the air quilt on a bed</A>kHodelhttps://www.blogger.com/profile/02232620214904583773noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-1622610198224902712008-02-13T00:20:00.000-05:002008-02-13T00:20:00.000-05:00If you've ever wondered what this sort of thing wo...If you've ever wondered what this sort of thing would look like in a more mainstream language, Eric Lippert has just written part 11 in a huge series of posts about <A HREF="http://blogs.msdn.com/ericlippert/archive/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue.aspx" REL="nofollow">immutability in C#</A>.Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.com