CODEWITHSUNDEEP
recursionfunctional-programmingsmlsmlnj
anon_swe
anon_swe

Reputation: 9355

SML: Implementing Multiply with Restrictions

I'm trying to implement multiply in SML with a few restrictions. I'm given the following add function:

fun add (0 : int, m : int) : int = m
    | add (n : int, m : int) : int = 1 + add(n-1, m)

I'm trying to write a function such that mult (m, n) recursively calculates the product of m and n, for any two natural numbers m and n. Your implementation may use the function add mentioned above and - (subtraction), but it may not use + or *.

Here's my attempt:

fun multiply(0 : int, m : int) = 0
    | multiply(n : int, 0 : int) = 0
    | multiply(1 : int, m : int) = m
    | multiply(n : int, 1 : int) = n
    | multiply(~1 : int, m : int) = ~m
    | multiply(n : int, ~1 : int) = ~n
    | multiply(n : int, m : int) =
        if (n > 0 andalso m > 0) then
            add(add(0, n), multiply(n, m - 1))
        else
            if (n < 0 andalso m < 0) then
                multiply(~n, ~m)
            else
                if (n < 0 andalso m > 0) then
                    n - multiply(n, m - 1)
                (* n > 0 and m < 0 *)
                else
                    m - multiply(m, n - 1);

It works when n and m are both positive or both negative but not when one is positive and the other negative but I can't seem to figure out my bug. For instance,

multiply(3, ~10) evaluates to 0. So I think my recursive call is getting to 0 and causing it to evaluate to 0. Having said that, my base cases take care of this so I'm not sure how it'd be possible.

Ideas?

Upvotes: 2

Views: 1361

Answers (1)

Parker
Parker

Reputation: 8851

Change the m - multiply(m, n - 1); to m - multiply(~m, n - 1);. (and the same for the other n -... line) The way you have it, you're subtracting a negative number from itself, so you're effectively canceling it out, and triggering a base case of 0.

Trace:

= multiply (3, -10)
= -10 - multiply (2, -10)
= -10 - (-10) - multiply (1, -10)
= -10 - (-10) - (-10)

As soon as there's a (-10) - (-10) you're setting off multiply(0 : int, m : int) which results in the 0, so your intuition about it being triggered was correct.

I realized you can't use +, so here's code that follows that. Becaase you need to multiply, we keep the basic logic the same, but instead of recursing with the same numbers, we turn the negative number positive before passing it to the recursive call.

fun multiply(0 : int, m : int) = 0
    | multiply(n : int, 0 : int) = 0
    | multiply(1 : int, m : int) = m
    | multiply(n : int, 1 : int) = n
    | multiply(~1 : int, m : int) = ~m
    | multiply(n : int, ~1 : int) = ~n
    | multiply(n : int, m : int) =
        if (n > 0 andalso m > 0) then
            add(add(0, n), multiply(n, m - 1))
        else if (n < 0 andalso m < 0) then
            multiply(~n, ~m)
        else if (n < 0 andalso m > 0) then
            n - multiply(~n, m - 1)
        else  (* n > 0 and m < 0 *)
            m - multiply(n - 1, ~m);

Console output

Also, a minor nitpick, but you can change add(add(0, n), multiply(n, m - 1)) to add(n, multiply(n, m - 1))

Upvotes: 1

Related Questions