SML “('a list * int) -> ('a list, boolean)”

Question

So this is my question: i wanna make a function that takes a list and and int, it then recursively moves through the list, and if it finds an element in the list equal to the int, then it should return the entire list with the element removed, and a boolean indicating wether something was removed. this is what i got so far:

fun foo ([], n) = ([],false)
  | foo ((x::xs), n) = if x = n 
                       then (xs,true)
                       else ([x] @ foo(xs,n),false);

my idea was to make the function cons the needed elements inside the tuple like this:

([x0] @ [x1] @ [x2] @ [xs], true)

so is there any way to make this function? keep in mind that it has to stop once it hits the element equal to n, but still retain the rest of the list, and be able to return a boolean. run time is key.

Matt S Matt S · Accepted Answer · 2012-09-21T20:26:42

Your current code is close to correct logically, but as you know it doesn't type-check because of [x] @ foo (xs, n). foo returns a tuple, which can't be directly appended. Here's how to fix it:

fun foo ([], n) = ([], false)
  | foo (x::xs, n) = if x = n
                     then (xs, true)
                     else let val (xs', tf) = foo (xs, n) in (x::xs', tf) end

The let is needed to extract the list from the tuple and find out if n was found in the tail of the list. Then we simply put the tuple back together with x consed back on to the front.

SML “('a list * int) -> ('a list, boolean)”

1 Answers