Resolved: SML - See if two unordered lists are equal (have same values, and the values appear the same amount of times)

Question:

Like the title says, I’m trying to see if two unordered lists include the same values and if these values appear the same amount of times in these lists. The assignment given asks not to order the lists. Here’s what I’ve done so far:

my logic was to compare recursively if the second list (from now on l2 ) includes the hd (= first element) of the first list ( from now on l1 ) if it does, compare the tl of l1. And as long as I call this isEqual function I would remove the hd of l1 and the first position in which the same value appears in l2. My base case would be that the 2 lists have different lengths then I would know for sure they are not equal. Here’s the code:

fun doesExist l =
    List.exists (fn x => x = true) l
; (* returns true if there's at least one 'true' in the list of bool *)

fun getFirstIndex target (a::b) index =
    if (a::b) = []
    then index
    else
        if target = a
        then index
        else getFirstIndex target b index+1
; (* returns the index of the first element = to 'target', in this case 'true', 
looking into the list (a::b) *)

fun delete (_,   nil) = nil
  | delete (0, _::xs) = xs
  | delete (i, x::xs) = x::delete(i-1,xs)
; (* should delete an element from a list, given the index gotten with the function above *)

fun isEqual [] [] = true
 | isEqual [] _ = false
 | isEqual _ [] = false
 | isEqual _ _ = false
 | isEqual l1 l2 =
    if List.length l1 <> List.length l2
    then false
    else
        if doesExist(List.map (fn n => n = hd l1) l2)
        then 
            isEqual(tl l1, delete(getFirstIndex(true, l2, 0), l2))
        else
            false
; (* this function puts altogether and should return either false or true *)

Below the output this function should return based on the lists passed:

isEqual [] []; (* true *)
isEqual [1] [1]; (* true *)
isEqual [1,4,2,8] [8,1,4,2]; (* true *)
isEqual [1,2,4,3] [11,24,56,7]; (* false *)
isEqual [7,5,12,88] [7,88,12,5,5]; (* false *)
isEqual [7,5,12,88,88] [7,88,12,5,5]; (* false *)
isEqual [7,5,12,88] [7,5,12,88,13,15]; (* false *)

The error in which I encounter is the following:

error: Type error in function application.
   Function: delete : int * 'a list -> 'a list
   Argument: (getFirstIndex (true, l2, 0), l2) :
      ((bool * ''a list * int) list -> int -> int) * ''a list
   Reason:
      Can't unify int to (bool * ''a list * int) list -> int -> int
         (Incompatible types)
Found near
  if doesExist (List.map (fn ... => ...) l2) then
  isEqual (tl l1, delete (...)) else false
es13.sml:24: error: Type of function does not match type of recursive application.
   Function:
      fun
         isEqual [] [...] = true |
            isEqual [...] ... = false |
            isEqual ... = false |
            isEqual ... = ... |
            ... : ''a list -> ''a list -> bool
   Variable: isEqual : ''a list * 'b list -> bool
   Reason: Can't unify ''a list to ''a list * 'b list (Incompatible types)
Found near
  fun
     isEqual [] [...] = true |
        isEqual [...] ... = false |
        isEqual ... = false |
        isEqual ... = ... |
        ...
Exception- Fail "Static Errors" raised

Answer:

I think you’re overthinking this problem.

fun isEqual [] [] = true
  | isEqual [] _  = false
  | isEqual _  [] = false

This is good so far, and makes sense.
Now, if neither of the lists are empty, then let’s pattern match that so that we can get to the head and tail of the first list.

fun isEqual [] [] = true
  | isEqual [] _  = false
  | isEqual _  [] = false
  | isEqual (x::xs) lst2 = ...

Now, if we remove the value x from lst2 and run the same function recursively on xs and what’s left of lst2, we should be able to reduce down to a result.
So let’s write a helper remove function. Your delete is on the right track, but it’s reliant on an index, and indexes aren’t really a natural fit with lists.
The option type is a good choice to represent a case where we try to remove a value that is not in a list. Getting NONE would tell us pretty handily that the two are not equal.

fun remove _ [] = NONE
  | remove v (x::xs) =
    if v = x then SOME xs
    else 
      case remove v xs of
        NONE => NONE
      | SOME xs => SOME (x::xs)

I’ll let you use this to complete isEqual.
Of course, you could also just sort both lists, and then this becomes much more straightforward.

If you have better answer, please add a comment about this, thank you!

Resolved: How to compare two text files and and change the sign of the data in powershell?

Resolved: Java Virtual Machines deleted

Resolved: PyCharm cannot see my newly compiled .pyc see on import

Leave A Reply