Chapel: Add procedure `==` overload to LinkedLists Standard Module

[krishnadey30]

I believe LinkedLists should have a == overload. Current scenario

use LinkedLists;
var x : LinkedList(int);
var y : LinkedList(int);
x.append(1,2,3);
y.append(1,2,3);
writeln(y==x);

gives output

false

but for

writeln(x==x);

prints

true

[ben-albrecht]

In case it's not clear, this is because LinkedList is implemented as a class, which does a pointer comparison by default. It seems like a no-brainer for the LinkedLists module to provide an overload for this.

[bradcray]

I suspect that the LinkedList class should be wrapped in a linkedList record to give it value semantics by default and support operators like ==. Note that we've generally been opposed to supporting overloads of == on classes (being discussed recently on #13048), but have never done a good job of outlawing them either.

[ben-albrecht]

I suspect that the LinkedList class should be wrapped in a linkedList record to give it value semantics by default and support operators like ==

I admittedly came to my earlier conclusion before checking the docs to confirm that LinkedList is implemented as a class. Turns out it is implemented as a record.

I suspect the pointer comparison between ListNode fields of the LinkedList records is causing the behavior reported in this issue. In any case, I think LinkedList record needs a == overload.

[krishnadey30]

I don't find any of inline overloads defined for LinkedLists. We should have either an inline == overload or a function like LinkedList.equals() as we have array.equals().

[bradcray]

I think if LinkedList is a record, we should just add the == overload to it (and !=?). We could also add an .equals to it where the former would compare node data using == and the latter using .equals, but that will probably only become useful once more / all types support .equals...?

[edit: I'm assuming that nobody would argue that the result of == on a linked list should be a linked list of booleans]

[rahulghangas]

I had a go at this.

proc ==(const ref l1: LinkedList(?t), const ref l2: LinkedList(?t2)) : LinkedList(bool) where t == t2 {
  private use HaltWrappers only;
  if l1.length != l2.length {
    HaltWrappers.boundsCheckHalt("Element-wise equality comparison on linked lists of different lengths (" +
        l1.length:string + ") and (" + l2.length:string + ")" );
  }
  var bool_linkedlist = new LinkedList(bool);
  if l1.length == 0 {
    return bool_linkedlist;
  }
  var el_l1 : borrowed listNode(t)? = l1.first.borrow();
  var el_l2 : borrowed listNode(t2)? = l2.first.borrow();
  do {
    bool_linkedlist.append(el_l1.data == el_l2.data);
    el_l1 = el_l1.next;
    el_l2 = el_l2.next;
  } while (el_l1 != nil);
  return bool_linkedlist;
}

[bradcray]

Nice! Want to put together a PR that adds this capability as well as a short test or tests of it?

[EL-SHREIF]

Why this issue is still Open not Closed?

[krishnadey30]

Why this issue is still Open not Closed?

I think @rahulghangas is working on it.

[bradcray]

Why this issue is still Open not Closed?

@EL-SHREIF: Because (as far as I know) a PR has not been merged that addresses it. But as @krishnadey30 indicates, my understanding is that @rahulghangas is working on it.

[lydia-duncan]

It looks like Rahul opened a PR (#15063) on it but didn't ping anyone to review

[lydia-duncan]

Dunno if that means the PR is ready for review or not

[rahulghangas]

I've been meaning to add tests but didn't get around to it for quite a while. Closed the old one because the changes were on my master branch. Recently created a new PR with a separate branch, which is still a draft until tests get added

[maheshkulkarni17]

@krishnadey30 i made a PR.
please review it.

[cassella]

I think if LinkedList is a record, we should just add the == overload to it (and !=?). We could also add an .equals to it where the former would compare node data using == and the latter using .equals, but that will probably only become useful once more / all types support .equals...?

[edit: I'm assuming that nobody would argue that the result of == on a linked list should be a linked list of booleans]

Hmm. So if LinkedList's == is to return a single bool, and it compares its elements with ==, there would need to be special code specifically to support a LinkedList of arrays. When LinkedList == compares two of its nodes' arrays with ==, it'll get an array of bools back, and need to reduce it. Or it could use .equals() to compare arrays, but it would have to know to use .equals() only on arrays, or only on types that have .equals().

Are arrays the only case where == doesn't return just a simple bool?

[bradcray]

it would have to know to use .equals() only on arrays, or only on types that have .equals().

This is probably the approach that I'd propose taking. And maybe it's time for us to define a standalone equals() function that uses reflection to determine whether a type supports .equals(), to call it if it does, and to fall back to == if it doesn't (asserting that whatever it calls returns a bool).

Are arrays the only case where == doesn't return just a simple bool?

I think at present, arrays are the only case, but I suppose a user-defined type could define its == in the same manner in the future. But it seems that we're also making an assumption that types defining .equals() will always have it return a bool (where this is something constrained generics could help us enforce once they're available).

[Shahwez-Ahmad]

I also work on this issue