Javascript - deepEqual Comparison

Question

Question (From Eloquent Javascript 2nd Edition, Chapter 4, Exercise 4):

Write a function, deepEqual, that takes two values and returns true only if they are the same value or are objects with the same properties whose values are also equal when compared with a recursive call to deepEqual.

Test Cases:

var obj = {here: {is: "an"}, object: 2};
console.log(deepEqual(obj, obj));
// → true
console.log(deepEqual(obj, {here: 1, object: 2}));
// → false
console.log(deepEqual(obj, {here: {is: "an"}, object: 2}));
// → true

My code:

var deepEqual = function (x, y) {
  if ((typeof x == "object" && x != null) && (typeof y == "object" && y != null)) {
    if (Object.keys(x).length != Object.keys(y).length)
      return false;
    for (var prop in x) {
      if (y.hasOwnProperty(prop))
        return deepEqual(x[prop], y[prop]);
    /*This is most likely where my error is. The question states that all the values
    should be checked via recursion; however, with the current setup, only the first
    set of properties will be checked. It passes the test cases, but I would like
    to solve the problem correctly!*/
      }
    }
  else if (x !== y)
    return false;
  else
    return true;
}

I think I have the general idea down; however, like I stated in the comment, the program will not check the second property in the objects. I feel like I have a structural/logic problem and am simply using recursion in the wrong way, as I originally intended to loop through the properties, use recursion to compare the values of the first property, then continue on in the loop to the next property and compare again. Although, I'm not sure if that's even possible?

I've given a good amount of thought and tried a couple different approaches, but this was the most correct answer I've come to so far. Any possible tips to point me in the right direction?

Answer 1

Feel that this version is a bit more readable (easier to comprehend). The logic is very similar with the top answer though. (ES6 this time)

function deepEqual(obj1, obj2) {

    if(obj1 === obj2) // it's just the same object. No need to compare.
        return true;

    if(isPrimitive(obj1) && isPrimitive(obj2)) // compare primitives
        return obj1 === obj2;

    if(Object.keys(obj1).length !== Object.keys(obj2).length)
        return false;

    // compare objects with same number of keys
    for(let key in obj1)
    {
        if(!(key in obj2)) return false; //other object doesn't have this prop
        if(!deepEqual(obj1[key], obj2[key])) return false;
    }

    return true;
}

//check if value is primitive
function isPrimitive(obj)
{
    return (obj !== Object(obj));
}

By the way, there is a cheater version of deep equal which works like a charm)) However, it's approximately 1.6 times slower.

As noticed by zero298, this approach is sensitive to the properties ordering and shouldn't be taken seriously

function cheatDeepEqual(obj1, obj2)
{
    return JSON.stringify(obj1) === JSON.stringify(obj2);
}

Answer 2

You can use a variable outside the for loop to keep track of the comparison:

var allPropertiesEqual = true;
for (var prop in x) {
    if (y.hasOwnProperty(prop)) {
        allPropertiesEqual = deepEqual(x[prop], y[prop]) && allPropertiesEqual;
    } else {
        allPropertiesEqual = false;
    }
}
return allPropertiesEqual;

The previous example is not optimized on purpose. Because you're comparing objects, you know that you can return false as soon as you find an inequality, and you can keep looping while all the previous checked properties are equal:

for (var prop in x) {
    if (y.hasOwnProperty(prop)) {
        if (! deepEqual(x[prop], y[prop]) )
            return false; //first inequality found, return false
    } else {
        return false; //different properties, so inequality, so return false
    }
}
return true;

Answer 3

I am quite new to JS but this is the way I solved it:

function deepEqual(obj1, obj2) {
if (typeof obj1 === "object" && typeof obj2 === "object") {
    let isObjectMatch = false;
    for (let property1 in obj1) {
        let isPropertyMatch = false;
        for (let property2 in obj2) {
            if (property1 === property2) {
                isPropertyMatch = deepEqual(obj1[property1], obj2[property2])
            }

            if(isPropertyMatch){
                break;
            }
        }

        isObjectMatch  = isPropertyMatch;

        if (!isObjectMatch) {
            break;
        }
    }

    return isObjectMatch;
} else {
    return obj1 === obj2;
}
}

And here are my tests:

var obj = {here: {is: "an"}, object: 2};
console.log(deepEqual(obj, obj));
// ? true
console.log(deepEqual(obj, {here: 1, object: 2}));
// ? false
console.log(deepEqual(obj, {here: {is: "an"}, object: 2}))
// ? true
console.log(deepEqual(obj, {object: 2, here: {is: "an"}}));
// ? true
console.log(deepEqual(obj, {object: 1, here: {is: "an"}}));
// ? false
console.log(deepEqual(obj, {objectt: 2, here: {is: "an"}}));
// ? false
console.log(deepEqual(2, 2));
// ? true
console.log(deepEqual(2, 3));
// ? false
console.log(deepEqual(2, null));
// ? false
console.log(deepEqual(null, null));
// ? false
console.log(deepEqual(obj, null));
// ? false

Answer 4

Based on the accepted answer by Paul Roub, I needed it to also match function values, and I wanted it to be a lot more concise, so I've refactored it.

function deepEqual(x, y, z) {
  return x === y || typeof x == "function" && y && x.toString() == y.toString()
    || x && y && typeof x == "object" && x.constructor == y.constructor
    && (z = Object.keys(y)) && z.length == Object.keys(x).length
    && !z.find(v => !deepEqual(x[v], y[v]));
}

var myFunc = (x) => { return x*2; }
var obj = {here: {is: "an", other: "3"}, object: 2, andFunc: myFunc};
console.log(deepEqual(obj, obj));
// ? true
console.log(deepEqual(obj, {here: 1, object: 2, andFunc: myFunc}));
// ? false
console.log(deepEqual(obj, {here: {is: "an"}, object: 2, andFunc: myFunc}));
// ? false
console.log(deepEqual(obj, {here: {is: "an", other: "2"}, object: 2, andFunc: myFunc}));
// ? false
console.log(deepEqual(obj, {here: {is: "an", other: "3"}, object: 2, andFunc: myFunc}));
// ? true
console.log(deepEqual(obj, {here: {is: "an", other: "3"}, object: 2, andFunc: (x) => { return x*2; }}));
// ? true
console.log(deepEqual(obj, {here: {is: "an", other: "3"}, object: 2, andFunc: (x) => { return x*999; }}));
// ? false

notes:

• You pass in only 2 args: x and y (z is for internal use).
• If one of the variables is null or undefined it returns that value instead of false, but that result is still "falsey" so I'm OK with it. To fix that you could change all occurrences of y && to (y || !1) && and x && to (x || !1) &&
• If you definitely don't expect that functions/callbacks would be supplied in your objects then remove || typeof x == "function" && y && x.toString() == y.toString()

Answer 5

Although that it's more verbose, maybe this option is easier to read:

function deepEqual(elem1, elem2) {
    if(elem1 === elem2) {
        return true;
    }
    if(typeof elem1 == 'object' && typeof elem2 == 'object' && elem1 != null && elem2 != null) {
      if(Object.keys(elem1).length == Object.keys(elem2).length) {
          for(let key of Object.keys(elem1)) {
              if(elem2.hasOwnProperty(key) != true) {
                  return false;
              }
          }
          for(let key of Object.keys(elem1)) {
              if(typeof elem1[key] == 'object' && typeof elem2[key] == 'object' && typeof elem1[key] != null && typeof elem2[key] != null) {
                  return deepEqual(elem1[key], elem2[key]);
              }
              else {
                if(elem1[key] !== elem2[key]) {
                    return false;
                }
              }
          } else {
            return false;
          }
        }
      }
    else {
        return false;
    }
    return true;
  }

Answer 6

All of the previous answers contain subtle errors that will cause them to fail in certain cases. They all either 1) depend on properties being in the same order or 2) return asymmetrical results in some cases, so that deepEqual(a, b) !== deepEqual(b, a). Here is an improved answer, assuming the following:

• We are interested in same-value equality; we want deepEqual(NaN, NaN) to return true, but deepEqual(0, -0) to return false.
• We only care about enumerable, string-keyed properties defined directly on our objects (i.e., those properties returned by Object.keys()).
• Full support for circular references is not needed.

/**
 * Tests whether two values are deeply equal using same-value equality.
 *
 * Two values are considered deeply equal iff 1) they are the same value, or
 * 2) they are both non-callable objects whose own, enumerable, string-keyed
 * properties are deeply equal.
 *
 * Caution: This function does not fully support circular references. Use this
 * function only if you are sure that at least one of the arguments has no
 * circular references.
 */
function deepEqual(x, y) {
    // If either x or y is not an object, then they are deeply equal iff they
    // are the same value. For our purposes, objects exclude functions,
    // primitive values, null, and undefined.
    if (typeof x !== "object" || x === null ||
        typeof y !== "object" || y === null) {
        // We use Object.is() to check for same-value equality. To check for
        // strict equality, we would use x === y instead.
        return Object.is(x, y);
    }

    // Shortcut, in case x and y are the same object. Every object is
    // deeply equal to itself.
    if (x === y)
        return true;

    // Obtain the own, enumerable, string-keyed properties of x. We ignore
    // properties defined along x's prototype chain, non-enumerable properties,
    // and properties whose keys are symbols.
    const keys = Object.keys(x);
    // If x and y have a different number of properties, then they are not
    // deeply equal.
    if (Object.keys(y).length !== keys.length)
        return false;

    // For each own, enumerable, string property key of x:
    for (const key of keys) {
        // If key is not also an own enumerable property of y, or if x[key] and
        // y[key] are not themselves deeply equal, then x and y are not deeply
        // equal. Note that we don't just call y.propertyIsEnumerable(),
        // because y might not have such a method (for example, if it was
        // created using Object.create(null)), or it might not be the same
        // method that exists on Object.prototype.
        if (!Object.prototype.propertyIsEnumerable.call(y, key) ||
            !deepEqual(x[key], y[key])) {
            return false;
        }
    }

    // x and y have the same properties, and all of those properties are deeply
    // equal, so x and y are deeply equal.
    return true;
}

Answer 7

<script>
var cmp = function(element, target){

   if(typeof element !== typeof target)
   {
      return false;
   }
   else if(typeof element === "object" && (!target || !element))
   {
      return target === element;
   }
   else if(typeof element === "object")
   {
       var keys_element = Object.keys(element);
       var keys_target  = Object.keys(target);
       
       if(keys_element.length !== keys_target.length)
       {
           return false;
       }
       else
       {
           for(var i = 0; i < keys_element.length; i++)
           {
                if(keys_element[i] !== keys_target[i])
                    return false;
                if(!cmp(element[keys_element[i]], target[keys_target[i]]))
                    return false;
           }
		   return true;
       }
   }
   else
   {
   	   return element === target;

   }
};

console.log(cmp({
    key1: 3,
    key2: "string",
    key3: [4, "45", {key4: [5, "6", false, null, {v:1}]}]
}, {
    key1: 3,
    key2: "string",
    key3: [4, "45", {key4: [5, "6", false, null, {v:1}]}]
})); // true

console.log(cmp({
    key1: 3,
    key2: "string",
    key3: [4, "45", {key4: [5, "6", false, null, {v:1}]}]
}, {
    key1: 3,
    key2: "string",
    key3: [4, "45", {key4: [5, "6", undefined, null, {v:1}]}]
})); // false
</script>

Answer 8

A simple one:
const isObject = (obj) => {
  return typeof obj === "object" && obj !== null;
};

let isEqual = true;
const deepEqual = (objA, objB) => {
  if (!isEqual) {
    return;
  }
  const keysA = Object.keys(objA);
  const keysB = Object.keys(objB);

  if (keysA.length !== keysB.length) {
    isEqual = false;
  }

  for (let i = 0; i < keysA.length; i++) {
    const valA = objA[keysA[i]];
    const valB = objB[keysA[i]];

    if (isObject(valA) && isObject(valB)) {
      deepEqual(valA, valB);
    } else if (valA !== valB) {
      isEqual = false;
    }
  }

  return isEqual;
};

Answer 9

I just went through this chapter and wanted to show my work, too.

The flaw in mine (let me know if there are more) is that the object properties have to be in exact order as well. I much prefer @paul and @danni's solution.

// Deep equal 
const deepEqual = (x, y) => {
  const xType = typeof x;
  const yType = typeof y; 
  
  if ( xType === 'object' && yType === 'object' && ( x !== null && y !== null ) ) {
    const xKeys = Object.keys(x);
    const yKeys = Object.keys(y);
    const xValues = Object.values(x);
    const yValues = Object.values(y);  
    
    // check length of both arrays
    if ( xKeys.length !== yKeys.length ) return false;
    
    // compare keys
    for ( i = 0; i < xKeys.length; i++ )
      if (xKeys[i] !== yKeys[i]) return false;
      
    // compare values
    for ( i = 0; i < xValues.length; i++ )
      if (!deepEqual(xValues[i], yValues[i])) return false;
      
  } else {
    if ( x !== y ) return false;
  }
  return true;
};

// Objects
let obj1 = {
  value: false,
  pets: null
};

let obj2 = {
  value: false,
  pets: null
};


let obj3 = {
  value: false,
  pets: {
    cat: false,
    dog: {
      better: 'yes'
    }
  }
};

let obj4 = {
  value: false,
  pets: { 
    cat: false,
    dog: {
      better: 'yes'
    }
  }
};


let obj5 = {
  value: false,
  dog: true
};

let obj6 = {
  value: false,
  cat: true
};


let obj7 = {
  value: true,
  dog: {
    cat: {
      wow: true
    }
  }
};

let obj8 = {
  value: true,
  dog: {
    cat: {
      wow: false
    }
  }
};


let obj9 = {
  value: true,
  dog: {
    cat: {
      wow: true
    }
  }
};

let obj10 = {
  dog: {
    cat: {
      wow: true
    }
  },
  value: true
};

// Just for building a pretty result, ignore if you'd like
const result = (x, y) => {
  return `For: <br/>
          ${JSON.stringify(x)} <br/>
          and <br/>
          ${JSON.stringify(y)} <br/>
          <span>>> ${deepEqual(x, y)}</span>`;
};

// To print results in
const resultDivs = document.querySelectorAll('.result');

resultDivs[0].innerHTML = result(obj1, obj2);
resultDivs[1].innerHTML = result(obj3, obj4);
resultDivs[2].innerHTML = result(obj5, obj6);
resultDivs[3].innerHTML = result(obj7, obj8);
resultDivs[4].innerHTML = result(obj9, obj10);

body {
  font-family: monospace;
}

span {
  color: #a0a0a0;
}

.result {
  margin-bottom: 1em;
}

<div class="result">
</div>

<div class="result">
</div>

<div class="result">
</div>

<div class="result">
</div>

<div class="result">
</div>