Ошибочный код Scala с использованием полиморфных проверок типа ADT

Question

Я делаю несколько упражнений для лучшего понимания IO-монад (после Functional Programming in Scala) и сумел написать какой-то ошибочный код, который каким-то образом передал компиляцию и вызвал у меня головную боль.

В приведенном ниже примере, я пишу стек безопасный интерпретатор в качестве монады IO . Код находится в сопоставлении шаблонов в полиморфном Алгебраическом типе данных (FlatMap[A, B]). Ошибка в коде: k1 andThen k2; две функции не могут составить, потому что k1 возвращает другой тип (IO[B]), чем k2 ожидает (B). Код по-прежнему задает тип, и это, очевидно, ошибка проверки типа, поскольку во время выполнения есть ClassCastException при автоматическом распаковке (точно так же, как если бы я использовал небезопасный перевод на Java). Также не существует предупреждений о компиляторе.

код (также можно найти на gist):

object IOMonadExercise extends App { 

    sealed trait IO[A]  
    case class Return[A](value: A) extends IO[A]  
    case class Suspend[A](f:() => A) extends IO[A]  
    case class FlatMap[A, B](io: IO[A], cont: A => IO[B]) extends IO[B] 

    object IO { 
    def apply[A](a: => A): IO[A] = Suspend(() => a) 
    } 

    object Interpreter { 
    def run[A](io: IO[A]): A = { 
     io match { 
     case Return(a) => a 
     case Suspend(f) => f() 

     case FlatMap(Return(a), cont) => run(cont(a)) 
     case FlatMap(Suspend(f), cont) => run(cont(f())) 

     // this case compiles for whatever reason but shouldn't type check (k1 returns IO[B] and k2 expects just B) 
     // accordingly, there is a ClassCastException in the runtime 
     case FlatMap(FlatMap(io1, k1), k2) => run(FlatMap(io1, k1 andThen k2)) 

     // this case is the one that actually works 
//  case FlatMap(FlatMap(io1, k1), k2) => run(flatten(io1, k1, k2)) 
     } 
    } 

    def flatten[A, B, C](io: IO[A], k1: A => IO[B], k2: B => IO[C]): FlatMap[A, C] = { 
     FlatMap(io, a => FlatMap(k1(a), k2)) 
    } 
    } 


    def sum(i: Int): IO[Int] = { 
    Stream.range(0, i).foldLeft(IO(0))((io, i) => FlatMap(io, (s: Int) => IO(s + i))) 
    } 

    val n = 100000 
    val sumNIO: IO[Int] = sum(n) 
    val sumN: Int = Interpreter.run(sumNIO) 
    println(s"sum of 1..$n by IO loop : $sumN") 
    println(s"sum of 1..$n by math expr: ${n * (n - 1)/2}") 
    assert(sumN == n * (n - 1)/2) 
} 

Что происходит? Это ошибка компилятора? Или это известное ограничение вывода типа? Или есть объяснение этому?

Я тестировал как на Scala 2.11.8, так и на 2.12.0, и поведение похоже одно и то же: код компилируется без предупреждений.

Answer 1

Я думаю, что это случай ошибки SI-5195. Если вы построите вложенный FlatMap вручную, вы не можете записать это andThen, потому что все типы известны и k1 и k2, очевидно, не могут быть скомпонованы.

Но в том, что шаблон соответствия типов io1, k1 и k2 не известны заранее, они должны быть установлены и, как мы видим, что они выводятся неправильно. [...]

EDIT Вот еще пытаются объяснить, как типовые проверки: если вы начинаете Выведение типов для k1 и k2 себя, вы придумаете

• k1: X => IO[Y] и k2: Y => IO[A] для некоторого X и Y
• плюс от k1 andThen k2 вам нужно IO[Y] <: Y

Значит, существует ли какой-либо тип Y который удовлетворяет этим ограничениям? Да, это Any. Но когда вы применяете его, IO[Y] становится Suspend[Int] и Y - это просто Int, для которого отношение подтипа не выполняется.