Nick Mudge Ignition Software Consulting & Development

In studying Haskell, the term primitive recursion keeps coming up without any definition really. Haskell seems to have this vast advanced mathematics background that seeps into the language and into the literature of the language. This can be balking and repelling for a programmer wanting to learn Haskell but without an advanced degree in math. But maybe it has benefits like maybe this definitive, discrete, articulate, specific knowledge is useful. Perhaps it keeps only smart people part of the user community of Haskell.

So I set out to find out what primitive recursion is. With math and computer science terms Wikipedia is often harder to understand than the term you're looking up.

In my search for knowledge that a mere mortal could digest, I found this online dictionary by NIST called Dictionary of Algorithms and Data Structures that is surprisingly human and well structured.

I followed a highly educational trail on the subject of function definitions. Let's look at some definitions from this dictionary:

Function: "(1) A computation which takes some arguments or inputs and yields an output. Any particular input yields the same output every time. More formally, a mapping from each element in the domain to an element in the range."

Yes, but what is meant by domain, and range?

Domain: "(1) The inputs for which a function or relation is defined. For instance, 0 is not in the domain of reciprocal (1/x). (2) The possible values of a variable."

Relation?

Relation: "A computation which takes some inputs and yields an output. Any particular input may yield different outputs at different times. Formally, a mapping from each element in the domain to one or more elements in the range."

Ah, for any input a function always returns the same result. Whereas a relation can return the same or different results. A relation is more generalized than a function. A function is a specialization of a relation.

Range: "The possible results of a function or relation. For instance, the range of cosine is [-1,+1]."

Under the definitions of words this dictionary provides lists of words under headings such as Generalization, which gives words that are generalizations of the word you are looking up, and Specialization, which are words that are specializations of the word, and Aggregate child, which shows you what words the word is contained in. Showing these relations of words is extremely useful in understanding the relations, similarities and differences between related words. Awesome.

Okay, let's look at the definition of primitive recursion.

Primitive recursion: "A total function which can be written using only nested conditional (if-then-else) statements and fixed iteration (for) loops."

Woah, I almost undertood that. Total function?

Total function: "A function which is defined for all inputs of the right type, that is, for all of its domain." It has an example: "Note: Square (x²) is a total function. Reciprocal (1/x) is not, since 0 is a real number, but has no reciprocal."

There's a "See also partial function."

Partial function: "A function which is not defined for some of its domain. For instance, division is (usually) a partial function since anything divided by 0 is undefined."

Wow, now I understand! and a whole lot of other things!

Comments

Dan Piponi
12 September 2007

Your sources contradict each other :-)

You say:

> For instance, 0 is not in the domain of reciprocal (1/x)

So what is the domain of reciprocal? It must be the real numbers with 0 removed, ie. R-{0}.

Now reciprocal is defined everywhere on R-{0}. So reciprocal is a total function on R-{0}. Contradicting:

> For instance, division is (usually) a partial function since anything divided by 0 is undefined.

So which is it? Either the domain is "The inputs for which a function or relation is defined", in which case all functions are total. Or a partial function is "A function which is not defined for some of its domain", in which case the domain must include values where the function is not defined.
Nick Mudge
nickmudge.info/
13 September 2007

Dan,

You are quite correct about the contradiction. I did some more research on what exactly a domain is for a function. From multiple sources I found a domain of a function is all input values that will result in real values. So input values that would result in division by 0 or imaginary numbers are not part of any function's domain.

A total function is a function that can take any argument and always return a real value.

A partial function is a function that can take an input value outside its domain, which results in division by 0 or an imaginary number.
Paul E. Black
13 September 2007

Dan,

I changed the definitions of partial (and total) function to defined for some(all) of *a* function.
Name: (required)
Email: (required)
Website:
What has four legs, rhymes with bat and says, "Meow?" (One word answer.)
Spam Filter: