[Haskell-cafe] General Advice Needed ..
Richard O'Keefe
ok at cs.otago.ac.nz
Thu Jan 14 22:00:31 EST 2010
On Jan 15, 2010, at 3:38 AM, Ian675 wrote:
>
> Pretty much yeah.. Im going through the book and things like :
>
> Define a function rangeProduct which when given natural numbers m
> and n,
> returns the product m*(m+1)*....*(n-1)*n
Case analysis and recursion.
If m > n, the answer is 1 (the product of an empty sequence is 1).
If m <= n, the answer is m * the product of m+1 .. n.
range_product m n = if m > n then 1 else m * range_product (m+1) n
Try it in C:
int range_product(int m, int n) {
return m > n ? 1 : m * range_product(m+1, n);
}
Same thing.
Of course the most direct way to express it in Haskell is
range_product m n = product [m..n]
> I got the solution from my lecture notes but I still dont understand
> it..
>
> rangeProduct :: Int -> Int -> Int
> rangeProduct m n
> | m > n = 0
> | m == n = m
> | otherwise = m * rangeProduct (m+1) n
>
> Totally lost! Haha..
One reason you're totally lost is that the code in the book is WRONG.
The product of an empty sequence is 1, not 0.
There are two basic ways of "thinking functionally", and they are
actually both important in practically every kind of programming.
(1) programming-by-combination:
look for existing functions that are "close" to what you want and
plug them together.
In this case, looking for "product of a sequence of numbers" leads
to 'product' and looking for "sequence of consecutive numbers"
leads to [ .. ] syntax, and plugging them together leads to the
product [m..n] version.
(2) programming-by-case-analysis (including recursion):
look for a way of classifying the problem into alternative cases,
at least some of which are obviously simpler to solve.
Recursion is just the special case where some of the alternatives
can be handled using the function you are trying to define.
By the way, the problem here is ambiguous.
I look at m * (m+1) * ... * (n-1) * n and think
"n to the falling n-m+1" (see "Concrete Mathematics" by Graham,
Knuth, and Patashnik) and this is actually defined (and not identically
1) when m > n. So there are at least two reasonable definitions of
what the function should do for m > n. (Returning 0 is NOT reasonable.)
More information about the Haskell-Cafe
mailing list