Исправить кодировку этого экзистенциального типа в Scala?

Question

Я заинтересован в кодировании этого типа потока из бумаги Stream Fusion от Coutts et al. Я исследую слияние потоков в Scala, пытаясь использовать макросы вместо правил перезаписи GHC.

data Stream a = ∃s. Stream (s → Step a s) s 
data Step a s = Done 
       | Yield a s 
       | Skip s 

Я пробовал несколько различных подходов, но я не уверен, как кодировать тип потока в Scala таким образом, что оба вхождения S относятся к тому же типу. Я легко написал стиль Step.

sealed abstract class Step[+A, +S] 
case object Done extends Step[Nothing, Nothing] 
case class Yield[A, S](a: A, s: S) extends Step[A, S] 
case class Skip[S](s: S) extends Step[Nothing, S] 

Пока этот тип кажется правильным. Я использовал ковариацию, так что функция типа A => A будет работать, даже если мы получим доходность и вернем Done или Step. Как в Хаскелле.

Моей точкой крепления является подпись Stream. Я пытаюсь определить его как класс класса. Единственной сигнатурой, которая работала до сих пор, является использование оператора типа Exists и Tuple для сохранения равенства типа S в обоих компонентах, как показано ниже.

type Exists[P[_]] = P[T] forSome { type T } 

case class Stream[A](t: Exists[({ type L[S] = (S => Step[A, S], S)})#L]) 

Есть ли способ его кодировать так, чтобы кортеж не нужен? Что-то ближе к (предполагается, что экзистенциальный оператор) в Haskell это:

case class Stream(∃ S. f: S => Step[A, S], s: S) 

, где каждый член может быть отдельное поле.

Это также происходит со мной, что я мог бы закодировать это в стиле/Functor SML модуль следующим образом:

trait Stream[A] { 
    type S <: AnyRef 
    val f: S => Step[A, S] 
    val s: S 
} 

object Stream { 
    def apply[A, S1 <: AnyRef](next: S1 => Step[A, S1], st: S1): Stream[A] = new Stream[A] { 
    type S = S1 
    val f = next 
    val s = st 
    } 

    def unapply[A](s: Stream[A]): Option[(s.f.type, s.s.type)] = Some(s.f, s.s) 
} 

, но это немного сложнее. Я надеялся, что существует более ясный способ, о котором я не знаю. Кроме того, когда я попытался изучить этот путь, мне пришлось сделать несколько вещей, чтобы удовлетворить компилятор, например, добавить привязку AnyRef, а метод unapply не работает. С помощью этого сообщения об ошибке scalac:

scala> res2 match { case Stream(next, s) => (next, s) } 
<console>:12: error: error during expansion of this match (this is a scalac bug). 
The underlying error was: type mismatch; 
found : Option[(<unapply-selector>.f.type, <unapply-selector>.s.type)] 
required: Option[(s.f.type, s.s.type)] 
       res2 match { case Stream(next, s) => (next, s) } 
        ^

Answer 1

Во-первых, Step выглядит идеально подходит для меня. Что касается Stream, я думаю, что вы на правильном пути с абстрактным типом. Вот что я придумал (включая реализации остальных методов в разделе 2.1 статьи Coutts):

abstract class Stream[A] { 
    protected type S 
    def next: S => Step[A, S] 
    def state: S 

    def map[B](f: A => B): Stream[B] = { 
    val next: S => Step[B, S] = this.next(_) match { 
     case Done  => Done 
     case Skip(s)  => Skip(s) 
     case Yield(a, s) => Yield(f(a), s) 
    } 
    Stream(next, state) 
    } 

    def unstream: List[A] = { 
    def unfold(s: S): List[A] = next(s) match { 
     case Done  => List.empty 
     case Skip(s)  => unfold(s) 
     case Yield(a, s) => a :: unfold(s) 
    } 
    unfold(state) 
    } 
} 

object Stream { 
    def apply[A, S0](n: S0 => Step[A, S0], s: S0) = new Stream[A] { 
    type S = S0 
    val next = n 
    val state = s 
    } 

    def apply[A](as: List[A]): Stream[A] = { 
    val next: List[A] => Step[A, List[A]] = { 
     case a :: as => Yield(a, as) 
     case Nil  => Done 
    } 
    Stream(next, as) 
    } 

    def unapply[A](s: Stream[A]): Option[(s.S => Step[A, s.S], s.S)] = 
    Some((s.next, s.state)) 
} 

пар вещи, чтобы отметить:

• Моего unapply имеет зависимый тип метода: он зависит от s.S. Я думаю, это могло быть вашим камнем преткновения.
• Метод unfold в unstream не является рекурсивным.

Вещь, которую я по-прежнему не совсем понятна себе, - это то, почему важно, чтобы S был экзистенциальным/скрытым/безотносительным. Если это не так, вы можете просто написать:

case class Stream[A, S](next: S => Step[A, S], state: S) 

... но я предполагаю, что для этого есть причина. При этом я также не уверен, что этот подход действительно скрывает S так, как вы хотите. Но это моя история, и я придерживаюсь этого.