CODEWITHSUNDEEP
smlsmlnj
user14587195
user14587195

Reputation:

Currying and summation of two lists of varying size

I'm self-learning SML and am currently am stuck with the concept of recursion between two lists of varying sizes.

Suppose you have two int lists of varying size, and a function that multiplies two numbers, like so:

val mul = fn(a, b) => a * b;

I want to use this function to be passed as a parameter into another function, which multiplies the numbers in the same index recursively until at least one of the lists is empty. So

val list1 = [1, 3, 5, 7]; 
val list2 = [2, 6, 3];

would be passed through that same function with mul and 35 would be returned, as 1*2 + 3*6 + 5*3 would be calculated.

My knowledge of how SML works is a bit limited, as I'm not exactly sure how to carry the result of the sum forward during the recursion, nor how to handle the base case when one of either lists terminates early. Could someone point me in the right direction in thinking of this problem?

Upvotes: 0

Views: 41

Answers (2)

sshine
sshine

Reputation: 16125

To add to Chris' answer, recursion over two lists at once can also be achieved with map and zip which are higher-order list combinators (i.e. functions that take another function as argument and operate on lists):

fun add (x, y) = x + y
fun mul (x, y) = x * y
fun sum xs = foldl add 0 xs
val zip = ListPair.zip

fun mulAndSum xs ys = sum (map mul (zip xs ys))

zip will also throw away elements if one of its input lists is longer than the other.

Upvotes: 0

Chris
Chris

Reputation: 36611

You can use pattern-matching and recursion to operate over two lists simultaneously. You then need an accumulator to pass the sum along.

fun mulAndSum acc ([], []) = ...
  | mulAndSum acc ([], _) = ...
  | mulAndSum acc (_, []) = ...
  | mulAndSum acc ((x::xs), (y::ys)) = mulAndSum (...) (xs, ys)

Then when you call the function, you provide zero as the initial state of the accumulator.

mulAndSum 0 ([1, 3, 5, 7], [2, 4, 6])

Upvotes: 1

Related Questions