# Discrete function is also a math function?

Here is a table of the Staten Island subway:

| STOP | STATION         |
|------+-----------------|
|    1 | St. George      |
|    2 | Tomkinsville    |
|    3 | Stapleton       |
|    4 | Clifton         |
|    5 | Grasmere        |
|    6 | Old Town        |
|    7 | Dongan Hills    |
|    8 | Jefferson       |
|    9 | Grant           |
|   10 | New Dorp        |
|   11 | Oakwood Heights |
|   12 | Bay Terrace     |
|   13 | Great Kills     |
|   14 | Eltingville     |
|   16 | Hugenot         |
|   17 | Prince’s Bay    |
|   18 | Pleasant Plains |
|   19 | Richmond Valley |
|   20 | Arthur Kill     |
|   21 | Tottenville     |


and here is an Elisp function that maps a number to a name:

(defun sisubstops (s)
(pcase s
((guard (or (< s 1) (> s 21))) (message "Hey, just stops 1 through 21, please!"))
('1 (message "St. George"))
('2 (message "" Tomkinsville))
('3 (message "Stapleton"))
('4 (message " Clifton"))
('5 (message " Grasmere"))
('6 (message " Old Town"))
('7 (message " Dongan Hills"))
('8 (message " Jefferson"))
('9 (message " Grant"))
('10 (message " New Dorp"))
('11 (message " Oakwood Heights"))
('12 (message " Bay Terrace"))
('13 (message " Great Kills"))
('14 (message " Eltingville"))
('16 (message " Hugenot"))
('17 (message " Prince’s Bay"))
('18 (message " Pleasant Plains"))
('19 (message " Richmond Valley"))
('20 (message " Arthur Kill"))
('21 (message " Tottenville"))))


So, when I'm trying to tell students that this is a function of a basically non-continuous phenomenon, i.e., we're not dealing with a function like f(x) = x^2, rather a function that matches stops to names -- but it is still a function -- how can I get this across? One idea would be to got deep into Lambda Calculus and talk about how LC does conditionals. My first goal is to distinguish between continuous versus discrete; and yet I've written a Lisp function that can't really be represented as any sort of normal math function e.g., S(n) = M*nwhere M is some sort of machine or constant that takes a stop number and turns it into a stop name. Any ideas how, yes, this is a function? Or is this just a misnomer, i.e., comp-sci using/abusing the term function. So yes, how is sisubstops really a function?

• Huh, functions are routinely explained via tables, or via set theory where elements of the domain are mapped to elements in the codomain. Without the set theory explanation (which didactically works best with finite sets), it's unnecessarily hard to express properties such as “injectivity” or “surjectivity”. – amon May 4 '19 at 20:04
• This seems like more of a CompSci question than Software Engineering. A better site for this question might be cs.stackexchange.com instead – Ben Cottrell May 4 '19 at 20:56
• In modern maths, functions are pretty much literally nothing but a mapping from arguments to results. Which means, for example, that arrays, maps, and sets are also functions. – Jörg W Mittag May 4 '19 at 21:30
• Yes first teach un-plugged, away from the computer. Link it to what they already know, then translate into a program, then into a programming language. – ctrl-alt-delor May 5 '19 at 8:46

Focus on the idea that the sets can be finite. They don't need to be defined by a formula. Any set of ordered pairs is a relation. If there is a unique second element for any given first element then it is a function.

For example, the set of pairs {(5,2), (5,4)} is not a function, since the value associated with 5 is not unique. This is a relation: a set of ordered pairs.

But {(5,2), (6,2)} IS a function since the value associated with 5 is unique and the same is true of 6. It is a constant function, by the way, since all values map to 2.

Additionally {(5, 2), (6, 3)} is a function and its inverse is {(2, 5), (3, 6)} which is also a function. Thus the original here is called invertible.

You don't need Lambda Calculus or any mathematics to show what a function is. Finite functions can be computed by table lookup or by hash maps. An array is a function from a certain set of integers to some other set (the values).

Actually functions defined by formulas in computing are often problematic since computations of many values (say Real Values) are only approximate.

• @GypsySpellweaver. You misread it. "unique for any given first element". {(5,2), (5,4)} is not a function, but {(5,2), (6,2)} IS a function. For the first element 5 the second element is not unique in the first set (a relation) but it is unique ("for any given first element") in the second set and therefore a function. – Buffy May 5 '19 at 10:28

Actually they are not the same thing at all. In mathematics a function consists of a univalent map between a domain and a range this is a subset of a cartesian product or just as you have described, a table. The continuous case is an extension to infinate domains and ranges, usually over the real numbers.

Functions in computing do not always behave this way. For example the read() "function" can return any number of values depending on the input, functions can make use of clocks and random number generators - results might even depend on instrumentation e.g. thermometers.

Your question was about discrete vs continuous functions for which I have always found this diagram useful :-

An explanation can proceed by considering numbers instead of shapes - abstracting to sets and then considering fractions/reals etc. But beware - the concepts are not the same in maths and computing although "function" composition works in both cases. Just be clear that this has nothing to do with the discreteness or continuousness of the setup. I suppose the real difference is that functions in computing can have side effects and like read() can be multivalued. Usually in computing the inverse function is harder to define too.

• Supposedly, Lambda Calculus is a pure theory of functions -- and, yes, supposedly anything function-wise in a LC-based programming language can be considered real math functions, because they're built from LC. If we stick to, e.g., Haskell, then I believe we don't have to worry about your "instrumentation" functions -- or at least the Haskell folks have a workaround/explanation. – 147pm May 10 '19 at 4:01
• A good point excepting that not all programming languages are purely functional and it is unlikely that beginners will use Haskell. Without wishing to extend the discussion into technicalities outside the range of discourse one could argue that functions in programming are more akin to operators in mathematics than functions in mathematics. Of course as you say, this all depends on the language to some extent. – Jon Guiton May 10 '19 at 10:01

Talk about step functions. This might get the point across that functions do not need to be continuous. (I think going into lambda calculus would just confuse your students here - there's no need.)

As for whether this is really a function - sure it is! To make it clearer, here's something you can do. The written numbers we have - '7', for instance - just stand in for the concept of seven. We could really use the symbol 'a' to stand in for the concept of seven. (Just as we can use any variable name to hold the value inside - though we do tend to choose variable names that 'make sense' to us.)

With that in mind, what keeps us from saying that 'St. George' is just another symbol? Nothing. The symbols don't matter, the relation between them does - that's what makes a function a function.

In math, a function is just an association between each element in a set X and a specific element in set Y. X and Y can be any well defined set: real numbers, rational numbers, integers, even integers, odd integers, all the real numbers except 0, words, names of states, names of cities, etc. Calling a table mapping between between bus stop numbers and bus stop names a function is perfectly sound mathematically as long as no single stop maps to two different names.

I guess I'm slightly confused about what your students are confused about. Did they somehow get tripped up by the definition of function? If so, I can't help but wonder what you did to cause that, because I've never encountered any sort of reaction to the term whatsoever.

As others have addressed, your example is still a perfect set-to-set function. That said, we can certainly code things that at least represent non-functions (such as Random), but calling them "computer functions" seems sufficient to avoid most confusions.

If this comes up in your classroom, I would just say that a mathematical function is a set to set mapping, and that computer functions behave that way often enough to have earned the name "function", even if they're not strictly mathematical functions in the same way. Side-effects (such as mutability) and randomness are two instances where computer functions behave more broadly than mathematical functions.

(Of course, if you want to get down to the level of bits and wires, our non-functions become true functions once again, but that may actually be more confusing depending on the level of the students involved.)

• His students got tripped up by the fact that basic math functions are generally continuous. It's just a failure of imagination, that's all, and there's no need to draw a distinction between computer functions and math functions; they're all the same. – Robert Harvey May 5 '19 at 15:19
• @RobertHarvey They are and they aren't the same. The problem with viewing them as the same is that you must ignore all of the metaphor along the way. A true Random, if it existed, would not fit under any formal definition of a mathematical function, and a computer function that takes no arguments, prints "hello" to the console, sets x to 3, launches a network connection to nasa.gov, and returns PI is a little hard to characterize. What are the domains and codomains, exactly? Calling it a mathematical function serves no models of thinking particularly well in that instance. – Ben I. May 5 '19 at 19:09
• Well, to be fair, most Random functions aren't truly random; they are pseudo-random, a sequence of numbers given a specific starting value (a seed) as input. But even if they were truly random, the distribution of the numbers could still be described mathematically. – Robert Harvey May 5 '19 at 21:29
• @RobertHarvey Described mathematically does not a function make. If we had a true Random generator (which, of course, we don't), it would be a non-function by definition, as the same input would generate a different output. But my real objection is the second one, that we really don't utilize computer functions in ways that are easily described as mathematical functions. How would you describe the computer function I mentioned in my prior comment? – Ben I. May 5 '19 at 22:52
• @BenI. Your prior example of a "function" is not a function, it is a procedure, or algorithm. Some languages differentiate between the two, most no longer do. The prints "hello", and connecting to the network are side effects, while the setting x to 3 is both a mutation and a side effect. Relative to the function it takes two arguments and returns PI. Programmatically the rest are important, as well as bad form, but they are not part of the function. – Gypsy Spellweaver May 6 '19 at 0:32