jeudi 16 juin 2022

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:

  • 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

I apologize if this is a banal error but this is my first week trying to learn SML. Thanks in advance to everyone who will contribute to get to the solution. Peace đŸ™đŸŒ

Aucun commentaire:

Enregistrer un commentaire