CODEWITHSUNDEEP
listfunctiondesign-patternsmatchingsml
Dovday
Dovday

Reputation: 13

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

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:

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

Upvotes: 1

Views: 108

Answers (1)

Chris
Chris

Reputation: 36611

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.

Upvotes: 1

Related Questions