Tuple* => Iterable #34

Closed
sritchie opened this Issue Jan 7, 2013 · 8 comments

Projects

None yet

3 participants

@sritchie
Twitter, Inc. member

Something like

class Tuple2ToColl[A,B,C](implicit a2c: Bijection[A,C], b2c: Bijection[B,C])
extends Bijection[(A,B),Iterable[C]] {
  override def apply(tuple: (A,B)) = {
    val (a,b) = tuple
    Iterable(a2s(a), b2s(a))
  }
  override def invert(iter: Iterable[C]) = {
    val a :: b = iter
    (a2c.invert(a), b2c.invert(b))
  }
}
@johnynek

any collection with the CanBuildFrom[Nothing, C, T] probably is better, right?

@sritchie
Twitter, Inc. member

Yup

@tonymorris

You want

class Tuple2ToColl[A,B,C](implicit a2c: Bijection[A,C], b2c: Bijection[B,C], s: Semigroup[C])
extends Bijection[(A,B),C]
@johnynek

@tonymorris Can you explain more clearly how a semigroup on C allows one to convert from C -> (A,B)? Not clear at all to me.

What I think we need here is something like List[T] @@ Rep[Size2] where we create Size0, Size1, ... Size22 classes to allow the type-system to see the size of the collection.

@tonymorris

Hi @johnynek
OK, the real operation you want is typically called *** and pronounced: tensor.

// type-alias for use in infix position
type ~>[A, B] = Bijection[A, B]

trait Bijection[A, B] {
  def ***[C, D](q: C ~> D): (A, B) ~> (C, D) = error("omitted")
}

This generalises the operation in question. If you then supply a semigroup:

trait Semigroup[A] {
  // must be associative!
  def op(a1: A, a2: A): A
}

then you can collapse on your output side:

trait Bijection[A, B] {
  def ***[C, D](q: C ~> D): (A, B) ~> (C, D) = error("omitted")
  def contrazip[C](q: A ~> C)(implicit S: Semigroup[C]): (A, B) ~> C = error("omitted")
}

What you definitely do not want is going to Iterable or any collection at all, since you will end up without a bijection and since any useful guarantees are lost, you will have some pretty unwelcome practical issues.

On this note, I must point out issue #41 for which @jedws submitted a patch. Jed and I have discussed this patch and I am unclear on what he is doing. However, my understanding is that he has taken all non-surjective Bijection values and modelled them as the pair (A => B, B => Option[A]). I may be misunderstanding, but this is going to require a new data type (PartialIsomorphism) or it is still going to be problematic.

If it is still the case that your data type instances are not properly bijective, then you are going to hit troubles in production when you start implementing these libraries on top. Note that this was always the problematic point in raising issue #41, not so much the misnaming as some noisy minors like to short-sightedly maintain.

Regarding the comments on issue #41, I must admit that I fell to my knees and so I failed to continue to contribute further (except to help @jedws out to some small extent). However, I have recovered today.

I do not know if the practical consequences need to be demonstrated here if the values are not bijective, since they are quite trivial to imagine. All I know is, without bijectivity, you will run into serious problems in production and especially if you start implementing libraries on top. I really hope I am putting enough emphasis here on the dangers of implementing libraries on top of this library as it currently stands (and as I currently understand it to be).

In short, I would strongly advise sound resolution of issue #41 before this issue (of library support in any form) is addressed, otherwise, implementing the suggestions in this issue will exacerbate the problem detailed in #41.

To be clear, I am in a bind here, because I know what is going to happen if issue #41 is not addressed properly and I do not want to feel responsible for that. Hopefully we can all learn in any case. Excuse my ranting :)

@johnynek

@tonymorris Totally appreciate your passion here, man. Let me take it a step at a time, because I'm totally slammed at work.

Can we do this:

1) Can you confirm that Jed's approach works? It looks really good to me.
2) I'll add a few stronger tests that indeed are the laws for bijections (which we skipped the first time around because we didn't know Jed's trick).

Then we'll take the next steps.

Of course I agree with you that implicit typeclasses that are NOT bijections could cause us headaches down the road (I think we can fix that quickly with Jed's tool, and I'm working on that now). We might have a disagreement about thee usefulness of casts (and unsafeIO, etc...) but let's save that for later.

@tonymorris

Yes, I just had a quick chat with Jed and it appears his solution improves things a lot. I think the only thing remaining would be to remove those that are not left-invertible (and so the trick does not work). I don't expect there would be many of those.

@sritchie
Twitter, Inc. member

Handled in #75

@sritchie sritchie closed this Feb 11, 2013
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment