CODEWITHSUNDEEP
listsml
Katarzyna Piecielska
Katarzyna Piecielska

Reputation: 13

How to return item index from list SML?

I have go a problem with function in SML. This function should return list index of number which will not be summed, but was taken to sum. A call of a function: index(10, [1,2,3,4,5,6,7]) Result should be 3 (10 is a sum of numbers, we seek an index from the list which gives us 10, e.g: 1+2+3=6, 1+2+3+4=10, and return previuos one)

fun index (sum : int, numbers : int list) =
    if null numbers
    then 0
    else if hd(numbers) > sum
    then 0
    else 1 + index(sum, (hd(numbers)+(hd(tl numbers)))::(tl numbers))

It seems to work, but result is wrong. Function increments the result every two calling even if it should not. Can anybody tell me how to fix this?

Upvotes: 1

Views: 1306

Answers (2)

Annie Lagang
Annie Lagang

Reputation: 3235

You're almost there. While I agree with @koodawg that adding a counter and a running total is another solution for this problem, having those in your code will complicate it more than it needs to be.

First, I have a few comments about your code. You must remove the unnecessary parens. hd(numbers) is same as hd numbers and (hd(tl numbers)) is equal to hd(tl numbers). So your (hd(numbers)+(hd(tl numbers))) could be simplified to (hd numbers + hd(tl numbers)). Also, you can combine if null numbers and if hd(numbers) > sum in a single condition for code brevity since they yield the same result: 0.

I'll try to explain how code works and I hope you'll get the idea where you have to amend your code.

Using your example, index(10, [1,2,3,4,5,6,7]), your code execution will be like this:

1) 

 fun index(10, [1,2,3,4,5,6,7]) =
     if 1 > 10 
     then 0 
     else 1 + (10, [1 + 2] append to [2,3,4,5,6,7])

new list: [3,2,3,4,5,6,7]
result: 1

2) 

 fun index(10, [3,2,3,4,5,6,7]) =
     if 3 > 10 
     then 0 
     else 1 + (10, [3 + 2] append to [2,3,4,5,6,7])

new list: [5,2,3,4,5,6,7]
result: 1

3) 

 fun index(10, [5,2,3,4,5,6,7]) =
     if 5 > 10 
     then 0 
     else 1 + (10, [5 + 2] append to [2,3,4,5,6,7])

new list: [7,2,3,4,5,6,7]
result: 1

4) 

 fun index(10, [7,2,3,4,5,6,7]) =
     if 7 > 10 
     then 0 
     else 1 + (10, [7 + 2] append to [2,3,4,5,6,7])

new list: [9,2,3,4,5,6,7]
result: 1

5) 

 fun index(10, [9,2,3,4,5,6,7]) =
     if 9 > 10 
     then 0 
     else 1 + (10, [9 + 2] append to [2,3,4,5,6,7])

new list: [11,2,3,4,5,6,7]
result: 1

6) 

 fun index(10, [11,2,3,4,5,6,7]) =
     if 11 > 10 
     then 0

result: 0

To sum all results: 1 + 1 + 1 + 1 + 1 + 0 = 5 (just like what you said that your function adds 2 to the expected result)

The correct code must behave like this:

1) 

 fun index(10, [1,2,3,4,5,6,7]) =
     if 1 > 10 
     then 0 
     else 1 + (10, [1 + 2] append to [3,4,5,6,7])

new list: [3,3,4,5,6,7]
result: 1

2) 

 fun index(10, [3,3,4,5,6,7]) =
     if 3 > 10 
     then 0 
     else 1 + (10, [3 + 3] append to [4,5,6,7])

new list: [6,4,5,6,7]
result: 1

3) 

 fun index(10, [6,4,5,6,7]) =
     if 6 > 10 
     then 0 
     else 1 + (10, [6 + 4] append to [5,6,7])

new list: [10,5,6,7]
result: 1

4) 

 fun index(10, [10,5,6,7]) =
     if 10 > 10 
     then 0

result: 0

To sum all results: 1 + 1 + 1 + 0 = 3 which is the expected answer.

HINT: You always make sure that the new list your function is processing must be smaller than the previous list/original list.

I hope I explained clearly why your code isn't working. I didn't include the code because I know this is a homework for an online class.

Upvotes: 2

Mike Makuch
Mike Makuch

Reputation: 1838

You need to keep a counter and total. Counter that increments with every recursive call, total equal to sum of each hd(numbers) as you go, then return the counter when your total > sum.

Something like this;

if (total + hd numbers) >= sum
then counter
else recursivecall(total + hd numbers, tl numbers, counter + 1)

Upvotes: 2

Related Questions