Refactoring to remove dependency on LazyList

[jimka]

This is a suite of questions discussed on discord, but I’m moving it here to better document the discussion. I have an abstract class Magma which I’d like to refactor to remove the dependency on LazyList, thus allowing a larger set of generated collections. I’m omitting a few things from the class definition, which I hope are not important.

abstract class Magma[T] {

  import HeavyBool._

  def gen(): LazyList[T] // a generator of objects of the Magma

  def isClosed(): HeavyBool = {
    forallM("a", gen()){ a:T =>
      forallM("b", gen()) { b: T =>
        member(op(a, b)) ++ Map("op(a,b)" -> op(a, b))
      }}}.annotate("closed")
}

With the help of balmungsan3 (thanks BalmungSan (Luis Miguel Mejia)) I refactored it to this.

import cats.Foldable

abstract class Magma[T] {
  import HeavyBool._

  def gen[C[_]:Foldable]()(implicit ev:Foldable[C]): C[T]

  def isClosed(): HeavyBool = {
    forallM("a", gen()){ a:T =>
      forallM("b", gen()) { b: T =>
        member(op(a, b)) ++ Map("op(a,b)" -> op(a, b))
      }}}.annotate("closed")
  ...
}

Now, I don’t know how to refactor the subclasses. How should I override gen in subclasses, 1) when I still want to be collection agnostic, and 2) when I want to specify a particular collection such as LazyList[Int]?

abstract class ModP(p: Int) extends Magma[Int] {
  override def toString: String = s"ModP($p)"

  override def gen()(implicit ev: Foldable[LazyList[_]]): LazyList[Int] = Magma.genFinite(p - 1)
...
}

class AdditionModP(p: Int) extends ModP(p) {
   ...
}

I get several errors I don’t understand.

First, how do I write methods in Magma class which make calls to gen?

Next, how can I specify an implementation for gen to have a specific type in a subclass ModP of Magma?

Third, how can I create a subclass of ModP where I don’t override gen?

[jimka]

Perhaps the definition of forallM will be helpful. Here it is.

The class HeavyBool

sealed abstract class HeavyBool(val because:Reason) {
  ...

  def ++(any: Map[String,Any]): HeavyBool = {
    this match {
      case HeavyTrue(because) => HeavyTrue(any :: because)
      case HeavyFalse(because) => HeavyFalse(any :: because)
    }
  }

  def annotate(reason:String): HeavyBool = {
    this.conjTrue(Map{"success" -> reason}).conjFalse(Map("failure" -> reason))
  }

  def conjTrue(another: Map[String,Any]): HeavyBool = {
    this match {
      case HeavyTrue(_) => this ++ another
      case HeavyFalse(_) => this
    }
  }

  def conjFalse(another: Map[String,Any]): HeavyBool = {
    this match {
      case HeavyTrue(_) => this
      case HeavyFalse(_) => this ++ another
    }
  }
}

A couple of subclasses of HeavyBool

case class HeavyTrue(override val because: Reason) extends HeavyBool(because) {}

case class HeavyFalse(override val because: Reason) extends HeavyBool(because) {}

And then the companion object

object HeavyBool {
  type Reason = List[Map[String, Any]]
  
  ...
  def forallM[T, C[_]](tag:String, items: C[T])( p: T => HeavyBool)(implicit ev: Foldable[C]): HeavyBool = {
    import cats._
    import cats.syntax.all._

    def folder(_hb:HeavyBool, item:T):Either[HeavyBool,HeavyBool] = {
      val hb = p(item)
      if (hb.toBoolean)
        Right(HTrue) // not yet finished
      else
        Left(hb ++ Map("witness" -> item,
                  "tag" -> tag)) // finished
    }

    items.foldM(HTrue:HeavyBool)(folder).merge
  }

  def existsM[T, C[_]](tag:String, items: C[T])(p: T => HeavyBool)(implicit ev: Foldable[C]): HeavyBool = {
    !(forallM[T,C](tag, items)(x => !(p(x)))(ev))
  }

  ...
}

[tarsa]

@jimka

import cats.Foldable

abstract class Magma[T] {
  import HeavyBool._

  def gen[C[_]:Foldable]()(implicit ev:Foldable[C]): C[T]

  def isClosed(): HeavyBool = {

i guess that you would need something like this instead:

import cats.Foldable

abstract class Magma[T, C[_]: Foldable] {
  import HeavyBool._

  def gen(): C[T]

  def isClosed(): HeavyBool = {
    ...
  }
}

but that’s just a wild guess. i haven’t thought hard about it

this way you’ll have the implicit foldable instance available in whole class.
of course parametrizing class instead of method means that you need multiple class instances where previously you could use just one and pass different foldable instances to its methods.

[jimka]

does that mean every instance of a given subclass of Magma only supports a single type of generator?

[jimka]

Giving that a try, it is not clear how to create the ModP subclass:

import HeavyBool._
import cats.Foldable

abstract class ModP(p: Int) extends Magma[Int, LazyList[Int]] {
  override def toString: String = s"ModP($p)"

  override def gen()(implicit ev: Foldable[LazyList[_]]): LazyList[Int] = Magma.genFinite(p - 1)

   ...
}

I see the following errors

[jimka]

changing to the following:

abstract class ModP(p: Int) extends Magma[Int, LazyList[_]] {
...
}

I get fewer errors. not sure if fewer is better.

[tarsa]

you need to take variance into account:
example Scastie - An interactive playground for Scala.

object Example1 {
  abstract class Parent {
    def produce: CharSequence
  }

  abstract class Child extends Parent {
    override def produce: String // correct variance, works
  }
}

object Example2 {
  abstract class Parent {
    def produce: String
  }

  abstract class Child extends Parent {
    override def produce: CharSequence // wrong variance
  }
}

object Example3 {
  abstract class Parent {
    def consume(input: String): Unit
  }

  abstract class Child extends Parent {
    override def consume(input: CharSequence): Unit // argument types are invariant?
  }
}

object Example4 {
  abstract class Parent {
    def consume(input: CharSequence): Unit
  }

  abstract class Child extends Parent {
    override def consume(input: String): Unit // argument types are invariant?
  }
}

what would you want to achieve? while complying with variance rules of course.

for example: a subclass must be able to work in all places where superclass works, so if your subclass accepts only a subset of inputs that superclass accepts, then that won’t compile.

[tarsa]

@jimka

def gen[C[_]:Foldable]()(implicit ev:Foldable[C]): C[T]

also here you’ll get the foldable instance twice, once from context bound and second time from explicitly written implicit argument. you should to settle on one or another.

[tarsa]

Covariance and contravariance (computer science) - Wikipedia shows:

Summary of variance and inheritance

The following table summarizes the rules for overriding methods in the languages discussed above.

	Parameter type	Return type
C++ (since 1998), Java (since J2SE 5.0), D, C# (since C# 9)	Invariant	Covariant
C# (before C# 9)	Invariant	Invariant
Scala, Sather	Contravariant	Covariant
Eiffel	Covariant	Covariant

but my example kinda contradicts the table, showing that for methods (as opposed to functions), scala is invariant in parameter type of overriding methods.

[BalmungSan]

I am a bit lost now where the conversation is.
But, this compiles: Scastie - An interactive playground for Scala.

You should be able to move things around and add the implementations that are missing and it should work.
The important thing here is that the compiler showed that it compiles using the current type signature.

[jimka]

@tarsa

also here you’ll get the foldable instance twice, once from context bound and second time from explicitly written implicit argument. you should to settle on one or another.

Sorry, I don’t understand what you mean by this. I sort of copied the example from somewhere else, and I don’t really understand it yet. I was hoping to increase my understanding as I use it and refactor my code accordingly.

[BalmungSan]

@jimka

@tarsa

@jimka

def gen[C[_]:Foldable]()(implicit ev:Foldable[C]): C[T]

also here you’ll get the foldable instance twice, once from context bound and second time from explicitly written implicit argument. you should to settle on one or another.

Sorry, I don’t understand what you mean by this. I sort of copied the example from somewhere else, and I don’t really understand it yet. I was hoping to increase my understanding as I use it and refactor my code accordingly.

Remember what I told you on Discord.

def foo[A : C]()

Is just sugar syntax for:

def foo[A]()(implicit ev: C[A])

This means you either use the context-bound syntax or you don’t and use implicit parameters directly.
But you don’t do both.

def gen[C[_]:Foldable]()(implicit ev:Foldable[C]): C[T]
// This expands into:
def gen[C[_]]()(implicit ev:Foldable[C], ev2: Foldable[C]): C[T]

See the two instances of Foldable, you only need one.
BTW, this is not just an innocent mistake of requesting the compiler to request the instance twice.
This will make everything fail, because now you have an implicit ambiguity.

[jimka]

@BalmungSan

Remember what I told you on Discord.

One reason i moved the conversation here was because I couldn’t follow the conversation spread about 100s of lines of different conversations intertwined.

[jimka]

@BalmungSan

But you don’t do both.

def gen[C[_]:Foldable]()(implicit ev:Foldable[C]): C[T]
// This expands into:
def gen[C[_]]()(implicit ev:Foldable[C], ev2: Foldable[C]): C[T]

See the two instances of Foldable, you only need one.

That’s really interesting and confusing. I had understood from the syntax that gen[C[_]:Foldable] means that I can only use a C which is a subclass of Foldable.

BTW, what is C here? Is it the place holder for List, or Array, or LazyList, or Vector etc? Or is C some intermediate object from cats whose name I don’t need to care about?

[BalmungSan]

@jimka

I had understood from the syntax that gen[C[_]:Foldable] means that I can only use a C which is a subclass of Foldable.

No, that is wrong in two ways.
First, we are talking about types here, not classes. Thus, the right terminology would be subtype, not subclass (this sounds like nitpicking, but the difference is very important; see: Typelevel | There are more types than classes).
Second, the syntax for that would be C <: Foldable. But, we are not using subtyping for polymorphism here. Rather, we are using the typeclass pattern; see: Polymorphism in Scala. · GitHub - Here we are not saying that C IS A Foldable. but that C HAS A Foldable instance, or that C FORMS A Foldable.

@jimka

BTW, what is C here? Is it the placeholder for List, or Array, or LazyList, or Vector etc?

Close enough if you want a casual understanding.
The strict explanation is that C is a type parameter of kind * -> * (informally known as type constructors). Thus, it can then be applied using List, LazyList, or any other * -> * kinded type.
Then, we add a further restriction about the existence of a Foldable instance for that type.
So, for example, even if Array has the right kind, it can’t be used because there is no Foldable[Array].

[spamegg1]

Ah yes, for whatever reason the Scala Discord server does not allow using threads (which is an extremely useful feature!)… I also had issues with this!

[jimka]

I’m trying to prepare a minimum working example… (currently far far from minimum, just first try) I called all my related code into a single file Scastie - An interactive playground for Scala.
The code compile, but has a java exception when running.

However it does not even compile for me on my laptop.

Maybe it is a problem of cats version?

java.lang.NullPointerException: Cannot invoke "cats.Foldable.foldM(Object, Object, scala.Function2, cats.Monad)" because the return value of "cats.Foldable$Ops.typeClassInstance()" is null
	at cats.Foldable$Ops.foldM(Foldable.scala:1047)
	at cats.Foldable$Ops.foldM$(Foldable.scala:1046)
	at cats.Foldable$ToFoldableOps$$anon$6.foldM(Foldable.scala:1080)
	at HeavyBool$.forallM(main.scala:143)
	at Magma.isAbelian(main.scala:194)
	at Magma$$anonfun$isField$1.apply(main.scala:471)
	at Magma$$anonfun$isField$1.apply(main.scala:471)
	at HeavyBool.$amp$amp(main.scala:47)
	at Magma$.isField(main.scala:471)
	at testGaussianInt$$anonfun$main$1.apply(main.scala:632)
	at testGaussianInt$$anonfun$main$1.apply(main.scala:626)
	at scala.collection.SeqView$Map.apply(SeqView.scala:59)
	at scala.collection.IndexedSeqView$IndexedSeqViewIterator.next(IndexedSeqView.scala:60)

[tarsa]

@jimka

Scastie - An interactive playground for Scala.

abstract class Magma[T,C[_]] {

  implicit var ev:Foldable[C] = implicitly[Foldable[C]]
  def gen()(implicit ev:Foldable[C]): C[T]

erm, this doesn’t look good. you should manage the context bounds correctly. this doesn’t seem correct at all.

maybe this will work:

abstract class Magma[T, C[_]: Foldable] {

  def gen(): C[T]

you can run your code under a debugger and figure out where typeclass instances come from.

[jimka]

Finally it compiles if I remove the implicit var ev.
With it I was getting lots of ambiguous errors like this

ambiguous implicit values:
 both value evidence$1 in class Magma of type cats.Foldable[C]
 and variable ev in class Magma of type cats.Foldable[C]
 match expected type cats.Foldable[C]
  implicit var ev:Foldable[C] = implicitly[Foldable[C]]

This code seems to compile, if I also take out the implicit vars from the subclasses.

abstract class Magma[T,C[_]:Foldable] {
  import HeavyBool._

  //implicit var ev:Foldable[C] = implicitly[Foldable[C]]
  def gen()(implicit ev:Foldable[C]): C[T]
...
}

[jimka]

seems to work, at least run without java exception, yipeee!!!

Scastie - An interactive playground for Scala.