Updating a list of 2-tuples in SML

Question

I'm trying to update a running list of 2-tuples in SML. This is the same problem as: How can I update lists in SML using functions?

Unfortunately, the answer doesn't help. First, here is my code:

fun member(a, []) = false
  | member((a, b), (c, d)::cds) = a = c orelse member((a, b), cds);

fun update([], (loc, v)) =  [(loc, v)]
  | update((y, z)::yzs, (loc, v)) =
    if member((loc, v), (y, z)::yzs) then 
    if loc = y then (loc, v)::yzs
    else (y, z)::update(yzs, (loc, v))
    else (y, z)::yzs@[(loc, v)];

I am able to call the update function on FLR to create new values, but can only update the last value. In addition, when the last value is added and I call the update function again, it has not appended to FLR. Here's my example:

- val FLR = [(1,1),(2,4),(3,9),(4,16),(5,25)];
val FLR = [(1,1),(2,4),(3,9),(4,16),(5,25)] : (int * int) list
- update(FLR, (6,36));
val it = [(1,1),(2,4),(3,9),(4,16),(5,25),(6,36)] : (int * int) list
- update(FLR, (7,42));
val it = [(1,1),(2,4),(3,9),(4,16),(5,25),(7,42)] : (int * int) list

Instead of assigning the value to "it," is there a way for me to assign the value of the new list to FLR? In addition, I'm not able to add new values to an empty list? Any suggestions on that?

update doesn't actually change its inputs, it returns a new output which contains the desired change. To get the new value, just bind it to FLR again, e.g. val FLR = update(FLR, (6, 36)); — Yawar
Hi @Oshua, and welcome to StackOverflow! Don't create duplicates of existing problems. Rather, if you have a question so related to an existing question as this, ask a clarifying question in a comment like "I am able to call the update function FLR to create new values, but can only update the last value. [...]" — Simon Shine

Simon Shine Simon Shine · Accepted Answer · 2018-04-11T05:15:13

As Yawar pointed out, your code seems to work, but the idea of mutating variables to see updates must be replaced with shadowing bindings with newly created values that slightly different.

Your code can be simplified:

fun member ((x,_), xs) = List.exists (fn (y,_) => x = y) xs

fun update ([], (x,v)) = [(x,v)]
  | update ((y,w)::pairs, (x,v)) =
      if x = y
      then (x,v) :: pairs  (* replace (y,w) with (x,v), stop *)
      else (y,w) :: update (pairs, (x,v)) (* keep (y,w), continue *)

That is, you don't need memberinside update to tell you whether the list needs updating or not, since that will require member to recurse through the list and return true or false with not much else to show for where the insert/replace should occur.

It seems a little asymmetric that member takes the pair first and the list second, while update takes the list first and the pair second. When designing APIs, try and make things consistent.

Doing yzs@[(loc, v)] is bad and probably, in your case, unnecessary. This insertion of a single element will loop through the entire list with the effect of the new pair ending at the end of the list. Instead of (y, z)::yzs@[(loc, v)] you could do (loc, v)::(y, z)::yzs to reduce this to a constant-time operation.

Updating a list of 2-tuples in SML

1 Answers