Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!news.albasani.net!.POSTED!not-for-mail From: Melzzzzz Newsgroups: comp.lang.forth Subject: Re: FORTH on the Advanced Placement Computer Science ! Date: Wed, 24 Dec 2014 05:31:54 +0100 Organization: albasani.net Lines: 43 Message-ID: <20141224053154.6bf7528d@maxa-pc> References: <67e78e28-e415-46f4-b3b1-d3072e74f392@googlegroups.com> <75OdnQZOi_GsPgvJnZ2dnUU7-fmdnZ2d@supernews.com> <7x4msmqry6.fsf@ruckus.brouhaha.com> <7xa92ew16a.fsf@ruckus.brouhaha.com> Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Trace: news.albasani.net uQfSjgo1Y9zSEDRjKxETn8OmJGpz22D0Ok4CgmGONx7+KHhLR6K9yNLHfwTwrnJM3KXIKVa1SJcS8PNWrGzjNiBdv3qI2aL++BS2suwY9gGkOjSGt542blc3MYSUG+Cx NNTP-Posting-Date: Wed, 24 Dec 2014 04:31:55 +0000 (UTC) Injection-Info: news.albasani.net; logging-data="FoXCAjLmiuguHyajMxGzwdIKTAA4e/eL9uOUCzquEMWj/yBUGNNBLTo1uwvCpT+k37on9llR45xZrMQafmlpyJWfAkxGnHzeCKihmTrrlLdIAHsTNKho0f6t+2kxtKOL"; mail-complaints-to="abuse@albasani.net" X-Newsreader: Claws Mail 3.11.0 (GTK+ 2.24.25; x86_64-unknown-linux-gnu) Cancel-Lock: sha1:NzFd19V+yAMxNpQ2wUlr4SQoM48= Xref: csiph.com comp.lang.forth:35168 On Tue, 23 Dec 2014 15:16:09 -0600 Andrew Haley wrote: > Paul Rubin wrote: > > Here is the notorious Quicksort example in Haskell: > > And it's a terrible implementation of quicksort. It's not that it is terrible quicksort, it is data structure used (singly linked list) terrible. > > > quicksort [] = [] > > quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort > > greater) where > > lesser = filter (< p) xs > > greater = filter (>= p) xs > > > > Like any small program this doesn't rely much on types, but it > > relies on GC to clean up intermediate results, and it uses a > > higher-order function (filter) that takes more cognitive overhead > > in assembler. Someone familiar with the algorithm could have > > written the above in about 2 minutes. I don't think even an expert > > could implement something comparable in assembler in less than 10x > > that much time. > > Probably not, but it would be much better. It would be in-place so it > wouldn't generate any garbage, and it would make a more intelligent > choice of pivot, and it would only stack what was necessary, and it > would have the tight inner loop which is what really makes quicksort > fast. It's like comparing a little toy car that you push along with > your feet with something you'd drive to work. Try that on singly linked list and result would be even slower :p Function is also generic so that means you have to call provided function every time comparison is needed, which means much slower :p In Haskell, several lists can contain same node as nothing is mutable so generated garbage would be at minimum. > > Andrew.