functional-programminglisp

What should be the domain of a 'minimum' function in functional programming?


So I'm studying systems engineering and we're currently going over different programming paradigms. We started playing with functional programming last class and we were asked to code a recursive 'minumum' function in Lisp. This is what I delivered:

(DEFUN minimum (l)
  (cond
    ((null l) nil)
    ((null (REST l)) (FIRST l))
    ((< (FIRST l) (minimum (REST l)) (FIRST l)))
    (t (minimum (REST l)))
  )
)

Out of all the things wrong with this, the one thing the professor corrected was the base case ((null l) nil) because "an empty list is not in the domain of the function", but that explanation wasn't enough for me since every other similar function we went through included this base case.

Should the empty list be part of the domain of the function?


Solution

  • One way to look at it is to try to see what the mathematical definition would be. And if you look around (e.g. Wikipedia), you will see that we usually do not define a minimum function. The definition goes like: if x belongs to S and x is not greater than any other element, then it is a minimum of S. That allows zero, one or more elements to be minimal in a set, and if you talk for example about min(S), this is always assuming that such a value exists. Sometimes you see actual functions, like min(a, b), where you take the least of two values a and b. So there is no obvious way to define how in general a minimum function over sets should be defined mathematically. We can assume for example that it would be undefined for an empty set, as your professor said. But just because that would be true in mathematics doesn't mean it is the same for the programming function minimum.

    A lot of functions defined in programming languages must be total, ie. accept all values of a type, because you cannot guarantee that you will never call them with a value outside of their domain (static typing systems can bring the implementation domain closer to the specification domain, but they have their limitations too). For example:

    (defun minimum (list)
      (check-type list cons) 
      ;; etc.
    )
    

    The above functions is able to accept any kind of value, and throws an error if that value is not a cons, i.e. a non-empty list. Your intuition to cover the case where the list is empty is right in my opinion, because even if it is not meaningful to call minimum on an empty list, you don't know that it will never happen, and it's better to give a useful return value or proper error in that case. There are other invalid cases, like the list containing values that are not in the domain of <: here too you could add a check in your code, or let the < function report the error itself (this should be enough in that case).

    Failing to detect an invalid case will eventually raise an error in a way that is not necessarily easy to decipher (worse, you could even proceed with invalid data without ever reporting an error). You could say that it's not your fault but the one of the function caller, who should know better. But it's not very nice. Certainly at some point the risk of people doing really really wrong things with the code drops and it doesn't pay to cover all possible mistakes from a risk analysis point of view, but ideally there is some level of robustness that is nice to have.

    In Common Lisp, returning nil in the above case is often considered the sensible thing to do, because numbers are distinct from symbols, and so nil is not going to be a problem. You will find some common idioms like this one, too:

    (or (minimum list) default-value)
    

    Since or returns the first non-nil value among its subterms (and evaluates them in sequence), you can cover the case where the list is empty in an elegant way.

    If however minimum in your language is defined to be the element that minimizes a cost function, then nil might be such an element (e.g. minimizing the length of symbol names in (nil defun defmacro) would be nil with a length of 3). There are such functions in Common Lisp too, and in that case it is better to error, or return a secondary value.

    All this to say that in practice, you are going to care about users of your programming interface, not just the mathematical definition of a function, and you may have to properly handle cases that "should never happen".