2

Update

This question is about replacing Any with A in step(x.flatMap((a: Any) => f(a).flatMap(g))). Type erasure in pattern matching seems to make this difficult.

def step[F[_], A](freeFA: Free[F,A]): Free[F,A] =
  freeFA match {
    case FlatMap(
      FlatMap(x, f), g
    ) => step(x.flatMap((a: Any) => f(a).flatMap(g)))
    .
    .
    .

  }

I appreciate the points in the comments that the Free monad is irrelevant to the crux of the question. My example needed include a generic type A and a generic type F[_] (a higher kinded type?).

It's a pedantic question and I'm interested to know "how to get around type erasure" (How do I get around type erasure on Scala? Or, why can't I get the type parameter of my collections?), even though the code compiles. I couldn't figure out how to apply TypeTags to this by myself.

The mention of static type checking is useful. Would someone explain why Any is set to A by static type checking and not dynamic type checking? I believed that type erasure was making static type checking impossible here, and that the compiler was retreating to dynamic type checking to resolve Any to A. Thank you

I have three case classes,

case class Return[F[_],A](a: A) extends Free[F, A]
case class Suspend[F[_],A](s: F[A]) extends Free[F, A]
case class FlatMap[F[_],A,B](s: Free[F, A],
  f: A => Free[F, B]) extends Free[F, B]

which inherit from trait Free:

sealed trait Free[F[_],A] {
  def flatMap[B](f: A => Free[F,B]): Free[F,B] =
    FlatMap(this, f)
  def map[B](f: A => B): Free[F,B] =
    flatMap(f.andThen(Return(_)))
  }

step, and the classes above, are part of an exercise in chapter 13 of "Functional Programming in Scala" to implement trampolining.

Because type erasure discourages type annotations within case FlatMap(FlatMap(x, f), g), the generic types within this case are left unspecified and become Any when made concrete. Then, the required signature of the anonymous function given to x.flatMap becomes Any=>Free[F,A]. I'd like the required signature of this function to be A=>Free[F,A] -- the true signature at runtime. 

def step[F[_], A](freeFA: Free[F,A]): Free[F,A] =
  freeFA match {
    case FlatMap(
      FlatMap(x, f), g
    ) => step(x.flatMap((a: Any) => f(a).flatMap(g)))
    .
    .
    .

  }

Annotating the input type of the anonymous function given to flatMap as A makes compilation fail,

step(x.flatMap((a: A) => f(a).flatMap(g)))

and I understand this is because A is only a subset of Any:

 [error]  found   : A => fpinscala.iomonad.IO3.Free[F,A]
 [error]  required: Any => fpinscala.iomonad.IO3.Free[F,A]

Type erasure prevents me from narrowing down Any to A like so:

def step[F[_], A](freeFA: Free[F,A]): Free[F,A] =
  freeFA match {
    case FlatMap(
      FlatMap(
        x: Free[F,A],
        f: Function1[A,Free[F,A]]
      ),
      g: Function1[A,Free[F,A]]
    ) => step(x.flatMap((a: A) => f(a).flatMap(g)))
   .
   .
   .
  }

Annotating the case statement this way serves no purpose other than documentation, and even causes problems, written up here: Scala: type annotations make tail recursion check fail

I can't figure out how to apply TypeTags to this situation.

How can I annotate this case statement to knock down Any to A? Thanks!!

Community
  • 1
  • 1
Peter Becich
  • 989
  • 3
  • 14
  • 30
  • 2
    Do you need to knock down `Any` to `A`? It seems that `step`'s type arguments are correctly inferred as `F` and `A`, and not `F` and `Any`, so your code compiles fine.... – dcastro Sep 04 '15 at 08:24
  • Thanks for the quick response. It does compile fine without the annotations, and `step`'s arguments are correctly inferred. It's a pedantic question. I'm trying to find stronger type checking within `case` statements, perhaps through TypeTags. – Peter Becich Sep 04 '15 at 08:31
  • It is a good question though, +1. I too am learning scala, and reading that same book (I'm in chapter 15 atm), and I've also noticed that type inference often fails inside case statements. Things compile fine, but IntelliJ inserts squiggly lines everywhere, like "Type mismatch: Expected Nothing, actual Any". Hope someone more experienced is able to help you/us. – dcastro Sep 04 '15 at 08:36
  • Good deal. It's a great book. About IntelliJ, I use Emacs and ENSIME and encounter similar error messages and squiggly lines. – Peter Becich Sep 04 '15 at 08:47
  • I don't understand what your problem is. The types are correctly inferred. `step(x.flatMap(f(_).flatMap(g)))` works fine. You don't need type tags, because your types are statically checked. – 0__ Sep 04 '15 at 09:00
  • 1
    @0__ Say you remove the type parameter `A`, and use an `Int` instead: `def step[F[_]](freeFA: Free[F,Int]): Free[F,Int]`. Inside the case statement, you should then be able to replace `f(a)` with `f(a + 1)`, since `a` is expected to be an `Int`. But you can't, because `a` is `Any`. – dcastro Sep 04 '15 at 09:20
  • 1
    Ok, then you should probably rephrase your question, because your intention is entirely unclear otherwise. Then it has very little to do with the Free monad, it's just asking how to transport the type tag for `A`. – 0__ Sep 04 '15 at 10:14
  • 1
    @0__ Well this was *my* interpretation of Peter's intention ^^ I guess the core of his question was exactly that, how to type `a` correctly. Perhaps his example wasn't the best, it compiles fine. – dcastro Sep 04 '15 at 10:23
  • @dcastro, that's correct. That's the core of my question. – Peter Becich Sep 04 '15 at 20:17
  • 1
    @PeterBecich Consider writing a new question, where the intent/problem is made clear. Creating a *minimal* example with no unnecessary code (as 0__ said, this "has very little to do with the Free monad") will make it easier for readers to understand the actual issue. This page may also help: [MCVE](http://stackoverflow.com/help/mcve) – dcastro Sep 07 '15 at 12:16

0 Answers0