Loop Patterns (cs.duke.edu)

Now I finally know how to refer to a “Loop and a Half”:

http://www.cs.duke.edu/~ola/patterns/plopd/loops.html#loop-a...

(Link seen at http://eli.thegreenplace.net/2010/06/30/python-internals-add... .)

ola is the best professor I had at college, period. He teaches data structures, (the second cs class in the curriculum) and does a fantastic job of getting everyone excited. He has another great paper on why bubble sort should never be taught. (it's a bit silly, but that is the point.) his class definitely set me on the path to study computers.

It would be fun to see these all expressed in Common Lisp's LOOP language, and interesting if any of them didn't work very well.

LOOP is a form of crack.

  ;; Linear Search
  (defun find-a-grade (grades)
    (loop for grade in grades
       when (char= grade #\a)
       return grade))

  ;; Guarded Linear Search
  ; should use condition system to signal exhaustion
  (defun surely-find-a-grade (grades)
    (loop for grade in grades
         when (char= grade #\a)
         return grade
         finally (return "not found")))  
  
  
  ;; Definate process all items
  ; fn is a unary function that gets applied to each element in sequence
  (defmethod search-all ((objects sequence) fn)
    (loop for item in objects do
         (funcall fn item)))
  
  ;fn is a BINARY function that gets applied to each key/value pair
  (defmethod search-all ((objects hash-table) fn)
    (maphash fn objects))
  
  
  ;; Polling loop
  (defun amy-poller (eof question)
    (loop for answer = (yes-or-no-p question)
       when answer 
       return "bye"))
  
  ;; extreme values
  (defun maximum (values)
    (loop for val in values
         maximize val))
  
  (defun minimum (values)
    (loop for val in values
         minimize val))

This was a disconcerting read - as I read it I realised that I was used to skimming over paragraphs to get the important point of each. In this article every sentence, every clause, is important. I had to concentrate, and I enjoyed it.

There is a slight problem with one of the examples:

  void findMinMax(istream & input, double & min, double & max)
  	// postcondition: min is the minimal value in stream input, 
  	// max is the maximal value in stream input
  {
  	double min = DBL_MAX; // #include <float.h> for DBL_MAX 
  	double max = DBL_MIN;
  	double current;
  	while (input >> current) {
  		if (current <= min) min = current;
  		if (current >= max) max = current;
  	}
  }
  

The DBL_MIN should be -DBL_MAX if non-positive numbers should be found, as DBL_MIN is the positive double value closest to zero, not the most-negative double value.

That article is fantastic. Although it may seem obvious and pedantic, I am always amazed at how many people get this stuff wrong.

Everyone spends all their time worrying about object oriented this and design pattern that and test driven agile the other thing, yet they don't grok the basics of procedural programming.

I HaveThisPattern. :) It is good to see that more people than me search for such... lets call them control flow patterns, because they reduce how much you have to think about mundane things during programming in a language which does not provide such primitives. You can just think "ok, iterate this array", and while your fingers note down this pattern, you can already figure what to put in there.

Of course, one needs to consider the loop constructs the language has. I would be annoyed if someone wrote the first loop in java, instead of using a for-each loop.

I just have some patterns differntly. For example, by now, I use a method to implement the guarded linear search, as it requires less branches and allows to hide the handling of the not-found-case:

  for (i = 0; i < students.size(); i++)
      if (student[i].hasGoodGrade()) return student[i];
  return noStudentFound;

For the polling loop, I'd just extract a conditional. do { readValue(); } while(!valueValid());

But yes, I recognize that these are minor stylistic quibbles :)