Using the addition function over the natural numbers, give a recursive definition of multiplication of natural numbers?

I have the following exercise but am not sure on how I should begin. The wording doesn't make sense to me:

Using the addition function over the natural numbers, give a recursive definition of multiplication of natu开发者_如何学Pythonral numbers.

You can think of 3 * 5 as 5 + 5 + 5, i.e. adding 5 for 3 times. If you want to do it recursively, then you can think of it like this: the result of a * b is equal to adding b to the result of (a-1) * b. From here to a Haskell recursive function, the step is small :)

mul(n,1) = n
mul(n,m) = mul(n,m-1) + n

something like this

One definition would be:

mul m n = sum $ replicate m n

Here replicate a b creates a list containing a copies of b, e.g. replicate 3 5 = [5,5,5]. sum gives the sum of a list, e.g. sum [5,5,5] is 15. Bingo!

Of course using the built-in functions would be cheating, so how could you write these functions yourself? I'll give you some hints:

replicate' 0 x = [] 
replicate' n x = x : ??? 

sum' [] = 0
sum' (x:xs) = ???

Generally it is a good homework strategy to look for predefined functions (e.g. using Hoogle) in order to solve the general problem, and to substitute that functions one by one. This helps to divide the problems in manageable steps, and gives you a free introduction of the Haskell API.

Multiplication of i, j is nothing but adding i, j times. this is java code, but you can take the logic from this.

    public int mul(int i, int j) {
        if(j==1) return i;
        return i + mul(i, j-1);
    }