Explanations about the mechanics of a simple factorial function

Question

I'm new to Haskell, so I'm both naive and curious.

There is a definition of a factorial function:

factorial n = product [1..n]

I naively understand this as: make the product of every number between 1 and n. So, why does

factorial 0

return 1 (which is the good result as far as my maths are not too rusted)?

Thank you

Answer 1

Not sure I understand your question, are you asking how to write such a function?

Just as an exercise, you could use pattern matching to approach it like this:

factorial :: Int->Int
factorial 0 = 1
factorial n = product [1..n]

The first line is the function declaration/type signature. The second two lines are equations defining the function - Haskell pattern matching matches up the actual runtime parameter to whichever equation is appropriate.

Of course as others have pointed out, the product function handles the zero case correctly for you.

Answer 2

That's because of how product is defined, something like:

product []     = 1
product (n:ns) = n * product ns

or equivalently

product = foldr (*) 1

via the important function foldr:

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

Read up on folding here. But basically, any recursion must have a base case, and product's base case (on an empty list) clearly has to be 1.

Answer 3

It's traditional to define the product of all the elements of the empty list to be 1, just as it's traditional to define the sum of all the elements of the empty list to be 0. That way

(product list1) * (product list2) == product (list1 ++ list2)

among other convenient properties.

Also, your memory is correct, and 0! is defined to be 1. This also has many convenient properties, including being consistent with the definition of factorials in terms of the gamma function.

Answer 4

The story about empty product is long and interesting.

• It has many sense to define it as 1.
• Despite of that, there is some more debate about whether we are justified to define 0⁰ as 1, although 0⁰ can be thought of also as an empty product in most contexts. See the 0⁰ debate here and also here.

Now I show an example, when empty product conventions can yield a surprising, unintuitive outcome.

How to define the concept of a prime, without the necessity to exclude 1 explicitly? It seems so unaesthetic, to say that "a prime is such and such, except for this and that". Can the concept of prime be defined with some handy definition which can exclude 1 in a "natural", "automatic" way, without mentioning the exclusion explicitly?

Let us try this approach:

Let us call a natural number c composite, iff c can be written as a product of some a₁, ..., ⋅ a_n natural numbers, so that all of them must be different from c.

Let us call a natural number p prime, iff p cannot be written as a product of any a₁, a_n natural numbers each differing from p.

Let us test whether this approach is any good:

6 = 6 ⋅ 1
      3 ⋅ 2
6 is composite, this fact is witnessed by the following factorisation: 6 can be written as the product 3 ⋅ 2, or with other words, product of the ⟨3, 2⟩ sequence, notated as Π ⟨3, 2⟩.

Till now, our approach new is O.K.

5 = 5 ⋅ 1
      1 ⋅ 5
5 is prime, there is no sequence ⟨a₁, ... a_n⟩ such that

• all its members a₁, ... a_n would differ from 5
• but the product itself, Π ⟨a₁, ... a_n⟩ would equal 5.

Till now, our new approach is O.K.

Now let us investigate 1:

1 = Π ⟨⟩,

Empty product is a good witness, with it, 1 satisfies the definition of being a composite(!!!) Who is the witness? Where is the witnessing factorization? It is no other than the empty product Π ⟨⟩, the product of the empty sequence ⟨⟩.

• Π ⟨⟩ equals 1
• All factors of the empty product Π ⟨⟩, i.e. the members of the empty sequence ⟨⟩ satisfy that each of them differ from 1: simply because empty sequence ⟨⟩ does not have any members at all, thus none of its member can equal 1. (This argumentation is simply a vacuous truth, with members of the empty set).

thus 1 is a composite (with the trivial factorization of the Π ⟨⟩ empty product).

Thus, 1 is excluded being a prime, naturally and automatically, by definition. We have reached our goal. For this, we have exploited the convention about empty product being 1.

Some drawbacks: although we succeeded to exclude 1 being a prime, but at the same time, 0 "slipped in": 0 became a prime (at least in zero-divisor free rings, like natural numbers). Although this strange thing makes some theorems more concise formally (Goldbach conjecture, fundamental theorem of arithmetic), but I cannot stand for that it is not a drawback.

A bigger drawback, that some concepts of arithmetic seem to become untenable with this new approach.

In any case, I wanted only to demonstrate that defining the empty product as 1 can yield formalizing unintuitive things (which is not necessarily a problem, set theory abounds with unintuitive things, see how to produce gold for free), but at the same time, it can provide useful strength in some contexts.