[Haskell-cafe] finding "good work" in CS
Richard A. O'Keefe
ok at cs.otago.ac.nz
Mon Dec 9 03:00:11 UTC 2013
On 8/12/2013, at 12:54 PM, Dennis Raddle wrote:
> It's me again, guy aged 45 thinking about doing graduate work in CS.
> I read this ebook about a guy's CS PhD, "The PhD Grind":
> It was enlightening. I used to think that software in the C.S. academic world must be well-written, seeing as it was written by computer scientists.
There is a huge difference between *computer science* and
*programming*. I remember two excellent computer scientists
I used to know, neither of whom had any idea of indentation.
(Seriously, one of them began each function on a new line,
and pressed the RETURN key only at the very end of it.)
Come to think of it, I met another computer scientist who was
writing a library for an exotic flavour of priority queue --
which he understood to a depth I shall never reach -- and was
interested in comparing it against some other priority queue
implementations, and asked me for some advice about the
coding. I suggested including the classic binary-heap-in-an-
array as a baseline. It beat the pants off _all_ the other
priority queue implementations.
Here's a piece of computer science that I would like some help
with. I call it the Indirect Cycle Detection problem.
Given: Domains P and E,
functions f : P -> Maybe P
g : P -> E
Define to_list :: Maybe P -> [E]
to_list Nothing = 
to_list (Just p) = g p : to_list (f p)
Given: That f is cyclic starting at p0.
Find: The shortest alpha, beta such that
to_list p0 is alpha ++ cycle beta
and do so *efficiently*.
Now, I can use tortoise-and-hare to find a cycle in f
and then use brute force to find a shortest prefix and
cycle of to_list ... The stuff I've checked so far
about periods in strings has nothing to say about
periods that begin _after_ a non-empty prefix.
The point here is that this is a computer science question
which can be answered by someone who has no knowledge of
any programming language. Indeed, I don't see any reason
to expect that programming skill would help.
> (I didn't like the poorly organized and simple-minded code involved in my last job at NASA.)
And yet we hear amazing things about NASA code quality.
> Turns out that academic code can be very poor indeed, sometimes just a hacked prototype meant to demonstrate an idea to get it published.
Since the declared *aim* of Universities is *published* research,
it is *rational* for code quality to be no higher than is required
to get that job done.
Basically, Sturgeon's Revelation
-- see http://http://en.wikipedia.org/wiki/Sturgeon's_Law --
is a universal truth.
I remember a certain company whose compilers and operating system
were gems of care and readability, yet provided a statistics package
whose code was _nightmarish_, pointlessly bulky, and would
happily invert a singular matrix and keep running.
Had you considered building software checking tools as a topic?
More information about the Haskell-Cafe