CODEWITHSUNDEEP
recursionfunctional-programmingsmlsmlnj
macalaca
macalaca

Reputation: 1048

Remove duplicates from a list in SML

I just started learning functional programming in SML and I want to know how I can combine the following two functions into a single function. The function isolate deletes the duplicates of a list of any type ('a) using the helper function 'removes'.

fun isolate [] = []
  | isolate (l as x::xs) = x::isolate(remove(x,xs))

fun remove (x,[]) = []
  | remove (x,l as y::ys) = if x = y then remove(x,ys) else y::remove(x,ys)

So, for the purpose of better understanding the constructs in the SML, how would you include the function remove within isolate? This may seem trivial, but I have thinking about it and can't figure it out. Thank you for your help!

Upvotes: 8

Views: 10262

Answers (4)

Jonny Kong
Jonny Kong

Reputation: 196

My idea is to first sort the list, then recursively return a new list without duplicates:

fun remove_duplicates(l: int list) =
if null(l)
then []
else if null(tl l)
then l
else
    let
        fun compare(x: int, y: int) = x > y
        fun sort(l: int list) = ListMergeSort.sort(compare) l
        val l_sorted = sort(l)
    in
        if (hd l_sorted) = (hd (tl l_sorted))
        then remove_duplicates(tl l_sorted)
        else (hd l_sorted)::remove_duplicates(tl l_sorted)
    end

Upvotes: 0

Xinyi Li
Xinyi Li

Reputation: 1022

My idea: define a nested function to check if there are duplicated elements in the list:

fun set(nums:int list)=
  let fun duplicate(x:int, l:int list)=
    if null l
    then false
    else hd l=x orelse duplicate(x,tl l)
  in
      if null nums
      then []
      else
      let val s=set(tl nums)
      in if duplicate(hd nums,s)
         then s
         else hd nums::s
      end
  end

But it will give a list that only remains the last one for every duplicated elements.

Upvotes: 1

qaphla
qaphla

Reputation: 4743

One method would be to just define remove inside isolate.

fun isolate [] = []
  | isolate (l as x::xs) =
      let fun remove (x,[]) = []
            | remove (x,l as y::ys) = if x = y
                                      then remove(x,ys)
                                      else y::remove(x,ys)
      in
        x::isolate(remove(x,xs))
      end

Alternately, to make deduplication one function, though all this really does is use the library function List.filter to do the same thing that remove does.

fun isolate [] = []
  | isolate (x::xs) = x::isolate(List.filter (fn y => y <> x) xs)

Upvotes: 10

Igor
Igor

Reputation: 515

I want to propound the following solutions of this problem:

fun remove_duplicates(xs: int list) = 
    let
        fun check(xs: int list, item: int) =
            if null xs
            then false
            else if hd xs = item
            then true
            else check (tl xs, item)
        fun go_through_list(xs: int list) =
            if null xs
            then []
            else if check(tl xs, hd xs)
                 then go_through_list(tl xs)
                 else hd xs :: go_through_list(tl xs)
    in
        go_through_list(xs)
    end

It's more lines of code than in the solution propounded by @qaphla

Upvotes: 0

Related Questions