[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":
> <http://www.pgbovine.net/PhD-memoir.htm>
> 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 mailing list