SML: Implementing Multiply with Restrictions

Question

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?

Maybe change m - multiply(m, n - 1); to m - multiply( n - 1,m);? The recursion might be getting messed up? It's been 4 years since I touched SML, so sorry I can't be more useful — Parker
@Parker Why do you suggest that? (Not saying it's wrong, but interested in your reasoning too) — anon_swe
Just a quick glance looks like you're handling things based on the two values being positive or negative, if you keep recursing and n and m keep changing spots, it might mess up the logic. Like the function always expects (n,m), but you're passing it (m,n). Again, I may have forgotten SML functions — Parker
Ah, I see what you're saying. Yeah I flipped them inadvertently although I still have the same issue with calling multiply(~3, 10) heh — anon_swe

Parker Parker · Accepted Answer · 2015-08-15T18:23:26

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);

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

SML: Implementing Multiply with Restrictions

1 Answers