Example 2 Prelude> let fac n = if n == 0 then 1 else n * fac (n-1) How does it know to stop ? and why does fac 2.5 hang? thanks Eoin -- -- Eoin C. Bairéad Dublin, Ireland Áth Cliath, Éire
On Thursday 02 September 2010 14:49:12, Eoin C. Bairéad wrote:
Example 2
Prelude> let fac n = if n == 0 then 1 else n * fac (n-1)
How does it know to stop ?
It tests for n == 0. If that returns True, the recursion stops.
and why does fac 2.5 hang?
Because 2.5 is not an integer, so fac gets called with 2.5 1.5 0.5 -0.5 -1.5 -2.5 ... but never with 0, so you get infinite recursion.
Hi!
2010/9/2 Eoin C. Bairéad
Example 2
Prelude> let fac n = if n == 0 then 1 else n * fac (n-1)
How does it know to stop ?
When fac is called with n=0 it returns 1 and stops the recursion.
and why does fac 2.5 hang?
fac, as you defined it, is only defined for integers. As you repeatedly subtract 1 from n you will never get to 0 (you will get to 0.5 and then -0.5) and thus the recursion will never terminate.\
02.09.2010 16:49, Eoin C. Bairéad пишет:
Example 2
Prelude> let fac n = if n == 0 then 1 else n * fac (n-1)
How does it know to stop ?
To stop what? It's not "doing" anything, it's just an equation. So "fac" is the "least" function which satisfies this equation - meaning that it's value would be (_|_) (which is a special value called "bottom") whenever possible. When you ask for "fac 3", for example, it's not possible for it to be (_|_), because it has to be 3*fac(2), according to this equation; and "fac 2" isn't bottom either, because it has to be 2*fac(1); and fac(1) has to be 1*fac(0), which is also not bottom, because the equation states explicitly that fac 0 = 1.
and why does fac 2.5 hang?
Because there isn't anything to prevent "fac 2.5" from being equal to (_|_); and when you ask for value that happens to be (_|_), your program can either crash or hang forever, it's the only special thing about bottom value.
Eoin C. Bairéad wrote:
Example 2
Prelude> let fac n = if n == 0 then 1 else n * fac (n-1)
How does it know to stop ?
Becuase you said "if n == 0 then 1". In other words, if n is zero then return one and stop. Only if n does *not* equal zero does it recursively so "n * fac (n-1)".
and why does fac 2.5 hang?
Because the n == 0 condition never holds. fac 3 yields n=3, n=2, n=1, n=0, stop. fac 2.5 yeilds n=2.5, n=1.5, n=0.5, n=-0.5, n=-1.5... forever. Note carefully that fac (-6) also loops forever. Now, if you were to change the condition to "n < 1" rather than "n == 0" then it would halt in all circumstances. You could also use a type signature to state that fac accepts only whole numbers, since this function only gives a meaningful answer in that case. (If you wanted a mathematically correct function, you need the Gamma function. But that's scary stuff, and this is a Haskell lesson not an advanced math lesson.)
participants (5)
-
Andrew Coppin -
Daniel Fischer -
Eoin C. Bairéad -
Johan Tibell -
Miguel Mitrofanov