tag:blogger.com,1999:blog-22587889.post251966199964820080..comments2024-02-11T13:21:47.930+05:30Comments on Ruminations of a Programmer: Collector Idiom in Scheme - Is this a Design Pattern ?Anonymoushttp://www.blogger.com/profile/01613713587074301135noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-22587889.post-62365180365144538282008-06-10T13:49:00.000+05:302008-06-10T13:49:00.000+05:30There is little I can add to Matthias' exposition ...There is little I can add to Matthias' exposition and I wouldn't presume to do so... but for fellow Scheme neophytes who might google this at a later date, it's worth stressing the point that in addition to TLS being all about the poetry of computation, both *let and named let are not introduced or used in this book* - because TLS is all about recursion and functions... it's turtles (oops lambdas!) all the way down.<BR/><BR/>Once you have let and named let, you can recur on your list of input data *and* update other list(s) of collected stuff at the same time - without the mind-bending collector function.<BR/><BR/>I'm glad to have now dimly grasped that on some meta level this ties in with continuation passing.... and whilst lambdas all the way down might be beautiful, I'm going to be using let/named let for until further enlightenment is achieved.Genjihttps://www.blogger.com/profile/11481136830742188059noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-91346587821989373122008-06-09T21:00:00.000+05:302008-06-09T21:00:00.000+05:30In the last few weeks I've actually had the need ...In the last few weeks I've actually had the need to do just this kind of collection in a non-toy program I'm re-implementing in Scheme in an attempt to get my programming brain a bit more functionalised.<BR/><BR/>I'd read TLS a few months before and my brain exploded somewhere in the middle of this chapter (what was left didn't survive the Y-combinator stuff later on!)<BR/><BR/>Anyway a bell rang later when I need to collect values and I went back to TLS and worked through some multirember&co examples by hand until I got it... so I munged the code around to make it do what I needed and everything was fine.<BR/><BR/>But ever since, I've had this nagging doubt about whether or not this was the canonical pattern for doing this in Scheme... having been doing some Lisp reading, I was more than sure that 'there is more than one way to do it'... so I googled and found your blog.<BR/><BR/>So a belated thanks to you and Matthias for formulating the question better than I could have and answering it (which I obviously could not have:))!Genjihttps://www.blogger.com/profile/11481136830742188059noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-43134165503471280672007-08-15T04:33:00.000+05:302007-08-15T04:33:00.000+05:30You're welcome.And don't trust the Haskell guy. He...You're welcome.<BR/><BR/>And don't trust the Haskell guy. He didn't even bother to run the program that he posts; otherwise he would have discovered the typo. If he actually read the discusssion, he would have realized that it is not about libraries :-)matthiashttps://www.blogger.com/profile/00000181081270224360noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-10290325051239291692007-08-15T03:51:00.000+05:302007-08-15T03:51:00.000+05:30In Haskell:multirememberandco :: Eq a => a -> [a] ...In Haskell:<BR/><BR/>multirememberandco :: Eq a => a -> [a] -> ([a] -> [a] -> b) -> b<BR/>multirememberandco a ls f = uncurry f $ parition (==a) ls<BR/><BR/>easy as pie :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-22587889.post-81267893422250701592007-08-14T23:38:00.000+05:302007-08-14T23:38:00.000+05:30Hi Matthias -Thanks a lot for your enlightening co...Hi Matthias -<BR/><BR/>Thanks a lot for your enlightening comment. I feel flattered! I am an absolute newbie trying to learn Lisp and functional programming coming from a 10+ years background of Java and C++. Your explanation of the philosophy behind the design of multirember&co() as in TLS, will indeed help me in a deeper understanding of the poem that Lisp is.<BR/>Thanks and Regards.Anonymoushttps://www.blogger.com/profile/01613713587074301135noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-7397886809203138062007-08-14T21:37:00.000+05:302007-08-14T21:37:00.000+05:30Here is the response from the author:First, TLL/TL...Here is the response from the author:<BR/><BR/>First, TLL/TLS uses 'poems' to discuss insights into program design and the programmng language per se. It is <EM>not</EM> about expressing things concisely, using some library. <BR/><BR/>Second, TLL/TLS does not use concise Scheme/Lisp notation for historical reasons. If you were to use such a notation in DrScheme, it might look like this: <BR/><BR/>[please pardon the mess, your blog doesn't accept pre and code tags]<BR/><BR/>(define (multirember&co a L col)<BR/> (cond<BR/> ((null? L) <BR/> (col (quote()) (quote())))<BR/> ((eq? (car L) a)<BR/> (multirember&co a (cdr L) (λ (newlat seen) (col newlat `(,(car L) . ,seen)))))<BR/> (else <BR/> (multirember&co a (cdr L) (λ (newlat seen) (col `(,(car L) . ,newlat) seen))))))<BR/><BR/>or perhaps like that: <BR/><BR/>(require (lib "match.ss"))<BR/><BR/>(define (multirember&co.v2 a L col)<BR/> (match L <BR/> (() <BR/> (col (quote()) (quote())))<BR/> (((? (λ (x) (eq? a x)) H) . T)<BR/> (multirember&co a T (λ (notHas has) (col notHas `(,H . ,has)))))<BR/> ((H . T)<BR/> (multirember&co a T (λ (notHas has) (col `(,H . ,notHas) has))))))<BR/><BR/>Now it starts looking like Erlang or any other FPL with pattern matching except that the clauses of the function are surrounded by a pair of parens, which I very much like. Of course, <EM>real programming language reserachers never discusss syntax, only semantics and pragmatics. </EM><BR/><BR/>Third, if you asked me to write this function in a concise manner, using standard libraries, I'd come up with this in 20 seconds: <BR/><BR/>(define (multirember&co a l col)<BR/> (define (pred x) (eq? x a))<BR/> (col (filter (compose not pred) l) (filter pred l)))<BR/><BR/>If you gave me another minute, I'd look in Olin Shivers's library whether it provides listpartition. <BR/><BR/>Fourth if you wanted to save a factor of 2, you would write a local iterative function (using let loop) that accumulates two lists (with tc), and applies col via another tc to the reverse of the two accumulators. <BR/><BR/>Finally, the example introduces the idea of "fourth" via CPS. If you follow some more language lore from the 1980s, you can <EM>derive</EM> the "fourth" solution from the poem, which is the point of these books.matthiashttps://www.blogger.com/profile/00000181081270224360noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-70042285881746336612007-08-14T17:06:00.000+05:302007-08-14T17:06:00.000+05:30Ignoring the continuation passing style that is th...Ignoring the continuation passing style that is the point of this example, here is how you can do this using the iterate package in Common Lisp<BR/><BR/>(defun remove-multiple-members (a list) <BR/> (iter (for x in list) <BR/> (if (eq a x) <BR/> (collect x into matched) <BR/> (collect x into unmatched)) <BR/> (finally (return (values matched unmatched)))))Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-22587889.post-23448062347801529532007-08-14T11:09:00.000+05:302007-08-14T11:09:00.000+05:30Thanks a lot for all your suggestions .. as I ment...Thanks a lot for all your suggestions .. as I mentioned in the blog, I have just started learning Erlang. Hence all your suggestions will help me a lot.<BR/><BR/>Reddit has also picked up this post .. the comments thread is <A HREF="http://programming.reddit.com/info/2eppy/comments" REL="nofollow">here</A>.Anonymoushttps://www.blogger.com/profile/01613713587074301135noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-11865044160735796142007-08-13T20:03:00.000+05:302007-08-13T20:03:00.000+05:30There are two bugs in your Erlang rewrite of the S...There are two bugs in your Erlang rewrite of the Scheme funtion. Has and NotHas need to be reversed, as has already been pointed out, and Col is supposed to take the list of unequal atoms as its first argument.<BR/><BR/>An improved version might look like this:<BR/><BR/>filter_atom(A, L, Col) -><BR/> filter_atom(A, L, Col, [], []).<BR/><BR/>filter_atom(_, [], Col, NotHas, Has) -><BR/> Col(lists:reverse(NotHas), lists:reverse(Has));<BR/><BR/>filter_atom(A, [A|T], Col, NotHas, Has) -><BR/> filter_atom(A, T, Col, NotHas, [A|Has]);<BR/><BR/>filter_atom(A, [H|T], Col, NotHas, Has) -><BR/> filter_atom(A, T, Col, [H|NotHas], Has).<BR/><BR/>However, if you <I>really</I> want to match what the Scheme implementation is doing, this would be even better:<BR/><BR/>filter_atom(_, [], Col) -><BR/> Col([], []);<BR/><BR/>filter_atom(A, [A|T], Col) -><BR/> filter_atom(A, T, fun(NotHas, Has) -> Col(NotHas, [A|Has]) end);<BR/><BR/>filter_atom(A, [H|T], Col) -><BR/> filter_atom(A, T, fun(NotHas, Has) -> Col([H|NotHas], Has) end).JeremyHussellhttps://www.blogger.com/profile/15173599414676384132noreply@blogger.comtag:blogger.com,1999:blog-22587889.post-28587398603672277982007-08-13T17:49:00.000+05:302007-08-13T17:49:00.000+05:30In fact, there is a more concise way, using lists:...In fact, there is a more concise way, using lists:partition/2 from the stdlib of OTP:<BR/><BR/>filter_atom(A, L, Col) -><BR/> {Has, NotHas } = lists:partition(fun(X) -> X == A end, L),<BR/> Col(Has, NotHas).<BR/><BR/>But, lists:partition/2 does exactly the same thing as your code, except it reverses the lists at the end of the partitioning, so the order is respected.tofhttps://www.blogger.com/profile/11109340532633596703noreply@blogger.com