tag:blogger.com,1999:blog-6655746112052720933.post8408805081088828237..comments2017-04-01T20:34:27.899-05:00Comments on Notes on Haskell: Fundamental Ideas of ComputingAdam Turoffhttp://www.blogger.com/profile/11941071792943377879noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-6655746112052720933.post-81263598846771727282007-04-13T15:12:00.000-05:002007-04-13T15:12:00.000-05:00I would consider Decidability to be the fundamenta...I would consider Decidability to be the fundamental idea of the theory of computation.<BR/><BR/>Remember that questions about the nature of computation arose from the attempts to answer mathematical problems, where it was wondered first "How can we prove theorems?" and then later "Can we prove this theorem at all?"<BR/><BR/>When suitably formalized, the question can be expressed in terms of set or language membership: Does a string belong in a language or not?<BR/><BR/>Exploration of the mechanical process by which such a question may be decided (or not be capable of decision) became the basis for the theory of computation.Matthewnoreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-66665600069145858172007-04-13T00:56:00.000-05:002007-04-13T00:56:00.000-05:00Very nice post: captures my own sentiments exactly...Very nice post: captures my own sentiments exactly.<BR/><BR/>However, this "optimized for terseness" seemed like a bit of a challenge! Surely it could use a bit more work to abstract out the common code:<BR/><BR/>qsort [] = []<BR/>qsort (x:xs) = rec (<) ++ x : rec (>=)<BR/> where rec (#) = qsort (filter (#x) xs)<BR/><BR/>Or even more terse (and I hesitate to post this publicly, but it <I>does</I> kinda take me back to my APL days):<BR/><BR/> q[]=[];q(x:y)=(\r->r(<)++x:r(>=))(\(#)->q(filter(#x)y))<BR/><BR/>Ouch! Sorry ... :) !<BR/><BR/>(Note that the where clause in the first example should be indented, I just can't get blogger to allow code or pre tags ... .)Fritzhttp://www.blogger.com/profile/07287120856377258774noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-16708663979626194072007-03-16T09:15:00.000-05:002007-03-16T09:15:00.000-05:00While it's true that those are very elegant and ac...While it's true that those are very elegant and accurate implementations of those two classic algorithms, the quicksort algorithm isn't one that you would want to use on very large lists, at least according to <A HREF="http://en.literateprograms.org/Quicksort_(Haskell)" REL="nofollow">this Haskell wiki</A>.<BR/><BR/>Their most efficient, unstable quicksort is still considerably more readable than any C implementation I've seen, but it is more complicated and further removed from the essence of quick-sort.Peterhttp://www.blogger.com/profile/03799579139256306118noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-13192464862787456482007-03-13T15:15:00.000-05:002007-03-13T15:15:00.000-05:00You did not mention function application. I would...You did not mention function application. I would consider function application *the* fundamental concept of CS, perhaps it's only equal being boolean algebra.Paulhttp://www.blogger.com/profile/07086384170577013095noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-80949332070633997392007-03-13T13:07:00.000-05:002007-03-13T13:07:00.000-05:00The reason that we don't memorize "basic" algorith...The reason that we don't memorize "basic" algorithms has nothing to do with C versus Haskell. It rather has to do with the fact that the responsibility of programmers is to reuse code. In a perfect world of code reuse and interoperability, quick sort would have been written exactly once and included by reference forever after. <BR/><BR/>If I had to write Quicksort in every program I had ever written that had sorting, you can bet I'd have it memorized character for character, whether programming in Haskell, C, or assembly language.<BR/><BR/>Think of it this way: how well would people remember their multiplication tables if every test they ever took allowed calculators? Computer programmers are both calculator users and calculator builders. So we'll never be good at memorizing things. We make the tools that allow people to forget. There is no reason to be ashamed of that.Paulhttp://www.blogger.com/profile/15412258048017521995noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-84200195334038381882007-03-13T10:03:00.000-05:002007-03-13T10:03:00.000-05:00Quicksort is a specific example of a problem that ...Quicksort is a specific example of a problem that can be solved using the fundamental ideas, like the pendulum or hydrogen atom problems in physics. If you're interested in the fundamental ideas of computing that are more analagous to high level concepts like Newton's laws, read the <A HREF="http://www.cs.cmu.edu/ct/" REL="nofollow">Computational Thinking</A> site at CMU or read Peter Denning's <A HREF="http://www.cs.gmu.edu/cne/pjd/GP/" REL="nofollow">Great Principles of Computing</A>. Computing is an infant field compared to physics, so these ideas are a long way from their final forms, but at least we're starting to think about them.Jameshttp://www.blogger.com/profile/13311908219056432735noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-45754607480623446612007-03-13T09:16:00.000-05:002007-03-13T09:16:00.000-05:00Nice essay! I agree that quicksort is especially e...Nice essay! I agree that quicksort is especially elegant in Haskell.<BR/><BR/>Once, just for kicks, I wrote a destructive quicksort in Haskell using the ST monad to encapsulate local state inside of a pure function.<BR/><BR/>I haven't posted it, though, because some programs are just too vile to unleash upon the world.emkhttp://www.randomhacks.net/noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-26639804021097093892007-03-13T08:53:00.000-05:002007-03-13T08:53:00.000-05:00As you were optimising for terseness, did you inte...As you were optimising for terseness, did you intend to optimise in a bug at the same time? [y | y = x] should be [y | y >= x]. (I guess it does demonstrate your point, though... and I'd also like to thank you for demonstrating that a Haskell program can be buggy and still type-check just fine!)<BR/><BR/>But it's also worth noting a few other points:<BR/>. This implementation of qsort has a horrid worst-case (nearly sorted lists); that can be improved by better pivot choice, but doing so introduces an additional layer of complexity - and the risk of more bugs<BR/>. In languages where recursion is expensive or limited, qsort usually gets rewritten iteratively, which is a really great way to introduce bugs to any algorithm<BR/>. qsort's main strength is that it sorts in-place; if that's not required, mergesort has slightly better overall performance, and doesn't have the nasty worst-case behaviour - and is even simpler to implement<BR/>. Trying to solve all of those in Haskell would probably result in an implementation significantly larger, more complicated and more error-prone than the existing one, just as it would in any other language; likewise, this "naive" implementation can be expressed as concisely in many other languages as it can in Haskell<BR/>. In any case, the fundamental idea is NOT any particular implementation of sorting, nor even sorting itself - but the recursive, divide-and-conquer approach to algorithm design, of which decent sorting and bsearch algorithms happen to be really good examplesgwenhwyfaerhttp://www.isle-of-avalon.co.uknoreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-87958007162243328042007-03-13T06:50:00.000-05:002007-03-13T06:50:00.000-05:00Ok, I like your post. However, as neat and concise...Ok, I like your post. <BR/><BR/>However, as neat and concise as the haskell code snippet for the tree is, it does make me wonder what layer of abstraction there is in Haskell. Is the tree automagically weighted? When? What are the conditions of the balancing etc?<BR/><BR/>I like my C/C++ and even Java for allowing me more control over my data-structures - even the libraries often give you sufficient flexibility.Jakenoreply@blogger.com