How can I update lists in SML using functions?

Question

I need to write an SML function that looks like this:

update(FLR, (x,y))

Where FLR is a finite list of tuples that looks like the following:

[(1,1),(2,4),(3,9),(4,16)]

But it can contain any number of tuples. What this update function needs to do is take in the list of tuples as the first argument and an x / y tuple as the second argument. If there is a tuple in the list that has the same x value as the one given to the function, it needs to update the y value of the list to the y value given to the function. If there is not a tuple with the x value given, the function needs to create a new tuple in the list at the appropriate location. For example, if the FLR has the values:

FLR = [(1,1),(2,4),(3,9),(4,16),(5,25)]

and the function is called as update(FLR, (2,3)); The new list should be [(1,1),(2,3),(3,9),(4,16),(5,25)]. Also, if the function is called as update(FLR, (6,36)); The new list should be [(1,1),(2,4),(3,9),(4,16),(5,25), (6,36)].

I am very new to functional programming and SML and I am not sure how to do this. I have written some memberOf functions that I'm sure I will need to use but my main concern is how to do all of this using recursion. Any help is greatly appreciated!

Have you written map yet? It's pretty similar: you need to walk through the list, working with one element at a time, and producing a new list with elements that correspond 1:1 to elements in the original list. — ephemient
That's what I am having trouble with. Could you provide some insight on how to write this function? — user5910724

molbdnilo molbdnilo · Accepted Answer · 2017-04-11T10:24:15

You shouldn't use memberOf, but you should apply what you learned about lists and recursion while implementing it and similar functions.

That is, how to do case analysis on the structure of a list;

Do something for the empty list
For a non-empty list, do something with its head and combine the result with the result of recursing on its tail.

A list transformation function often looks like this:

fun transform [] = []
  | transform (x::xs) = (do something with x) :: (transform xs)

For instance, a function that replaces every 0 with a given number:

fun replace_zero (a, []) = []
  | replace_zero (a, x::xs) = (if x = 0 then a else x) :: (replace_zero (a, xs))

That should hopefully get you back on track.

How can I update lists in SML using functions?

1 Answers