forall type scala3 (kind bound errors)

Question

I'm trying to write some of the core datatypes from a Haskell library called 'Rock' in Scala.

As mentioned in the README for the above linked project, the ideas for the library are based loosely on the paper found here.

Here are the core types used in the Rock library (Haskell):

// in src/Core.hs (
type Rules f = GenRules f f

-- | A function which, given an @f@ query, returns a 'Task' allowed to make @g@
-- queries to compute its result.
type GenRules f g = forall a. f a -> Task g a

-- | An @IO@ action that is allowed to make @f@ queries using the 'fetch'
-- method from its 'MonadFetch' instance.
newtype Task f a = Task { unTask :: ReaderT (Fetch f) IO a }
  deriving
    (Functor, Applicative, Monad, MonadIO, MonadBase IO, MonadFix)

newtype Fetch f = Fetch (forall a. f a -> IO a)

Some appear simpler than those present in build systems a la carte paper linked (e.g.: the Task type which is a thin abstraction over IO)

I'm curious whether it is possible/feasible to model this in a similar way in Scala.

After doing some reading on 'forall' types in Scala (and referring to older threads such as this one, I started with the following:

object Core {

  type Rules[F[_]] = GenRules[F[_], F[_]]  //<- scala err: "Type argument F[?] does not have the same kind as its bound [_$2]"

  type GenRules[F[_], G[_]] = [A] => (F[_] => Task[G[_], A])

  type Task[F[_], A] = ReaderT[Fetch[F[_]], A]

  type Fetch[F[_]] = /*forall*/ [A] => (F[A] => IO[A])

}

I'm having difficulty understanding why I cannot specialize the GenRules type with F[_]...

Also: Down the road, whatever formulation these types take in Scala 3 (or 2), the goal would be to reproduce the Spreadsheet example illustrated in the Rock repo's homepage. Below is a snippet of the haskell version with some initial work on the scala version below

// Spreadsheet.hs (https://github.com/ollef/rock/blob/master/examples/Spreadsheet.hs)
data Query a where
  A :: Query Integer
  B :: Query Integer
  C :: Query Integer
  D :: Query Integer

rules :: Rock.Rules Query
rules key = do
  liftIO $ putStrLn $ "Fetching " <> show key
  case key of
  ...             -- rest elided

Scala version:

// GADT for the sample/example `Query` type
enum Query[A]:
    case A extends Query[Int]
    case B extends Query[Int]
    case C extends Query[Int]
    case D extends Query[Int]

def rules() : Core.Rules[Query] =
   // ????

In the original haskell code, the key mentioned in the rules function is of type Query a. One thing: the rules function takes no input.. so is Core.Rules[Query] some kind of partially applied type?

Any insight into into these questions would be helpful -- I'm not necessarily concerned with arriving at 'idiomatic' scala code

Answer 1

F[_] in type parameter definition means "type constructor * -> *". F[_] in type application means "existential type". Scala 3 prefers to have 2 distinct syntax for those, but old syntax from Scala 2 is still parsed. Drop [_] in F application because its kindness doesn't match expected.

GenRules should apply the A obtained from [A] =>.

// definitions in more sane order
object Core {
  type Fetch[F[_]] = [A] => F[A] => IO[A]

  type Task[F[_], A] = ReaderT[IO, Fetch[F], A]
                  // = Fetch[F] => IO[A] (what this ReaderT actually is)

  type GenRules[F[_], G[_]] = [A] => F[A] => Task[G, A])
                         // = [A] => F[A] => ReaderT[IO, Fetch[G], A] (dealias)

  type Rules[F[_]] = GenRules[F, F]
                // = [A] => F[A] => ReaderT[IO, Fetch[F], A] (dealias)
}

Once we do the dealiasing excercise we know what kind of value we need to define:

val rules: Core.Rules[Query] =
  [A] => (key: Query[A]) => {
    // here create value of type:
    // Task[Query, A] dealiased to
    // ReaderT[IO, Fetch[Query], A]
    ???
  }

EDIT:

Actually, if we dealias further one implementation becomes kinda obvious:

val rules: Core.Rules[Query] =
  [A] => (key: Query[A]) =>
    ReaderT[IO, Fetch[Query], A] {
   // (fetch: Fetch[Query]) =>
      (fetch: [B] => Query[B] => IO[B]) =>
        fetch[A](key) // IO[A]
    }

What you have here is a type-parametric method which takes the value (key) and later takes another type parametric method to apply that value. Since the type of Rules is a polymorphic function, the fact that it takes arguments is hidden in its definition, but when you instantiate it, you have to pass these arguments somehow. And then you would define then. In Haskell all functions are curried, so if you define only the first parameter, it is assumed that you will return something which will consume remaining ones.