List Equality

[Sam Reid]

I was surprised to find that fj.data.List does not implement equals/
hashcode. For instance, this equality test returns false:

public class TestList {
public static void main( String[] args ) {
final java.util.List<Integer> myList = Arrays.asList( 1, 2,
3 );
boolean equal =
iterableList( myList ).equals( iterableList( myList ) );
System.out.println( "equal = " + equal );//prints false
}
}

Ted Neward also said he was surprised by this behavior in a Thread in
Aug, 2010:
http://groups.google.com/group/functionaljava/browse_thread/thread/241dea5f89f99f0b/2c5afaf1e8652dbb?lnk=gst&q=list+equals#2c5afaf1e8652dbb

The problem with having to use Equal.listEqual is that AFAIK it
doesn't work with existing tools like IntelliJ idea's "generate equals/
hashcode" or lombok's @EqualsAndHashCode.

What is the argument against adding a List.equals() that delegates to
member equals() methods? It seems like doing that could (a) decrease
surprise and (b) make it easier to use with other tools/API's. Going
the additional mile and overrloading all methods that require
Equals<A> with a version that delegates to .equals() could also make
List easier to use in typical situations but would not be absolutely
necessary.

I am new to this API and mailing list so please let me know if there
has been other discussion.

Thanks!
Sam

[Runar Bjarnason]

Well, we do want to discourage using .equals and .hashCode because,
strictly speaking, they are a lie. E.g. the equals method assumes that
*for all* X, you can compare two List<X> for equality. But that is
only true if you can compare Xs for equality.

So if you had, say, a List<Foo>, and you had an Equal<Foo> instance
available, you would want your List equality to use that. But .equals
has no way of knowing about it.

So I propose a compromise. How about a wrapper? This wrapper would
take three arguments in its constructor: List<A>, Equal<A>, Hash<A>.
It could implement .equals and .hashCode because it has all the
information it needs.

I'm not terribly bothered by not working the way IntelliJ and Lombok
expect. But it would be nice to be able to use an fj.data.List as,
say, a key in a java.util.HashMap, and this requires implementing
.equals and .hashCode. Having a wrapper like described above would
accomplish this.

What do you think of that?

Runar

> --
> You received this message because you are subscribed to the Google Groups "Functional Java" group.
> To post to this group, send email to functio...@googlegroups.com.
> To unsubscribe from this group, send email to functionaljav...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/functionaljava?hl=en.
>

[Sam Reid]

A wrapper may solve the problem, but my main concerns would be:

1. Would it be easy to instantiate and use (nearly as easy as List?)

2. Would it be difficult to create/maintain?

3. Would it integrate with existing functionaljava collections?  For instance, we would probably want a WrappedList.map() to return a WrappedList instead of a List.

> E.g. the equals method assumes that *for all* X, you can compare two List<X> for equality. But that is only true if you can compare Xs for equality.

This argument doesn't seem convincing because the Java API requires that every object must implement an equals method, and hence you can perform an equality test on any two objects at runtime.  It is up to the developer to make sure the equals method is implemented properly for the object.

Isn't this an issue of "convention over configuration"?  It seems the way that fj is set up now, it requires developers to always provide a specific configuration instead of defaulting to a sensible convention.

What is the probability that existing code would break by the addition of List.equals()?

If we do proceed with a wrapper, then I would also recommend adding a ToString<A> instance to it, so that it can have a nice default toString implementation.

Thanks for your thoughts!

Sam

[Runar Bjarnason]

On Sat, Feb 11, 2012 at 3:27 PM, Sam Reid <samr...@gmail.com> wrote:
> A wrapper may solve the problem, but my main concerns would be:
> 1. Would it be easy to instantiate and use (nearly as easy as List?)

Sure. You'd want a constructor that takes an Equal<A>, Hash<A>, and
List<A>. That sounds pretty easy.

> 2. Would it be difficult to create/maintain?

Not nearly as difficult as .equals and .hashCode. To quote my friend
Daniel Spiewak: "There is no more heinous crime against humanity" than
these two methods.

> 3. Would it integrate with existing functionaljava collections?  For
> instance, we would probably want a WrappedList.map() to return a WrappedList
> instead of a List.

Or just: `wrap(wrapped.list.map(f))` to unwrap and rewrap. I'd be fine
with that, although having delegations to List's methods would be fine
too.

> This argument doesn't seem convincing because the Java API requires that
> every object must implement an equals method, and hence you can perform an
> equality test on any two objects at runtime.

This does not seem convincing to me because, well, it actually does
not require it. And besides, it assumes that there is only one
implementation of equality for any given type. Basically .equals,
.hashCode, and .toString are a design flaw in the standard library.
The fact that we are having this conversation demonstrates this flaw.

> What is the probability that existing code would break by the addition of
> List.equals()?

Very small. But it would encourage the writing of poorly factored code.

> If we do proceed with a wrapper, then I would also recommend adding a
> ToString<A> instance to it, so that it can have a nice default toString
> implementation.

Good idea.

Just out of curiosity, what is it that you need the .equals and
.hashCode methods for, specifically? You said you were surprised by
their absence. Were you looking for them out of academic curiosity, or
was there some code that didn't work properly because they weren't
there?

Runar

[Jason Zaugg]

On Sat, Feb 11, 2012 at 9:45 PM, Runar Bjarnason <runar...@gmail.com> wrote:

Just out of curiosity, what is it that you need the .equals and
.hashCode methods for, specifically? You said you were surprised by
their absence. Were you looking for them out of academic curiosity, or
was there some code that didn't work properly because they weren't
there?

My story, shared by a few colleagues: I picked up FJ because I wanted to avoid null and I wanted map/filter/bind. I didn't have time to retrofit Equal/Hash on all my types; nor the discipline to wire them together manually as one needs to do in Java. I used a wrapper, which I forgot to do some of the time, leading to runtime surprises.

We recently added a equals() in scalaz.NonEmptyList after the same discussion. Let's encourage better code with a carrot rather than a stick.

-jason

[Sam Reid]

> Were you looking for them out of academic curiosity, or was there some code that didn't work properly because they weren't there?

When I ported from using another list collection to fj.data.List my code broke because the old list used .equals equality test and fj.data.List didn't.  To be specific, I went from using:

@Data public class ContainerSet {

    public final java.util.List<Container> containers;

[other fields]

}

to using:

@Data public class ContainerSet {

    public final fj.data.List<Container> containers;

[same other fields]

}

I am evaluating Lombok, which is automatically generating the equals() and hashcode() implementation from the fields (like Scala case classes).  In my case, this caused the rendering subsystem performance to degrade significantly because it was always detecting that the state was different even when it hadn't really changed. Another reason the missing equals implementation in fj.data.List is surprising is that it is present in many other JVM collections:

java.util.List<E>

scala.collection.immutable.List<E>

com.google.common.collect.ImmutableList<E>

I agree with Spiewak that equals and hashcode are tricky, and that why I'd like to be able to use automated tools for generating them, so I can be sure they are correct.  That is one reason it would be nice if fj.data.List followed the conventions of the Java API (even if wrong or questionable)--then I wouldn't have to code equals/hashcode myself and run the risk of error.

You said it would be difficult to correctly implement equals() and hashcode() for fj.data.List.  Maybe there are bugs in it, but wouldn't this be pretty close to a correct (while inefficient) content-based equals implementation?

    @Override public boolean equals( Object obj ) {

        return obj != null && obj instanceof List && new ArrayList<A>( toCollection() ).equals( new ArrayList( ( (List) obj ).toCollection() ) );

    }

> You'd want a constructor that takes an Equal<A>, Hash<A>, and List<A>. That sounds pretty easy.

Sure, but if I am duplicating new WrappedList<A>(new ContentBasedEquals(), new ContentBasedHash(), new ContentBasedString()) in many places then it might be nice to factor that out into class DefaultList extends WrappedList with the above implementations.  I am still a bit concerned about how smoothly this would integrate with existing code without duplicating too much code in the library, but maybe it would work.  But maybe it would simply be less work to just add equals() to List?  If others need the previous behavior, they could override equals() to use == for list reference equality?

Sam

[Runar Bjarnason]

> You said it would be difficult to correctly implement equals() and
> hashcode() for fj.data.List.

No, that's not what I meant at all. But if we do add them, they should
be compatible with List's Equal instance. So the implementation should
be the same as:

https://github.com/functionaljava/functionaljava/blob/master/core/src/main/java/fj/Equal.java#L247

Feel free to add .equals and .hashCode this way and submit a pull
request. If you're feeling generous, add them to Stream, NonEmptyList,
Tree, etc. as well. :)

Runar

[Sam Reid]

Thanks, I posted a pull request here:

https://github.com/functionaljava/functionaljava/pull/15 

I added equals, hashCode and toString implementations for fj.List which delegate to the corresponding Equal, Hash and Show classes which use the member values.  I have been using this fork in my application for a while and it works as prescribed in my application.  I'm unfamiliar with Stream, NonEmptyList, Tree and other fj implementations, so I didn't add to those, but they could probably use a similar implementation strategy.  This pull request does not add any scalacheck properties, let me know if I should add those (if I did so, it would probably just check that the delegation was working properly).  Right now my application is built on this fork, but would be nice if we could build on a new production version of functionaljava when we publish--we hope to deploy by May 2012, so let me know if there's anything I can do to help out.

Thanks for your nice project!

Sam