The very basic tool in programming is to be able to create a variable or a parameter that we can use in many contexts just by replacing it with different values. This is a strange way to say the definition of Lambda calculus which is the basis for most programming languages today. At least those languages that use functions.
The next few examples will show how we can go from value level functions to type level functions and how is this syntax "distinction" represented in languages like TypeScript, C#, Scala, Haskell and Idris.
Video: https://youtu.be/-p1QqAilZoI
Languages like JavaScript or Python, function parameters are always on the value level.
// JavaScript
// `x` can be any type. We cannot specify the type of `x`.
const myFunc = x => x
// When calling the function only the value arguments can be supplied, there is no type arguments.
myFunc(42)Languages like Go, Java 1 or C# 1. We have a way to specify parameter to a function which correspond to type level syntax.
// TypeScript
// `number` is type level constant.
const myFunc = (x: number) => x
// When calling the function we still supply only the value and type `number` is always the same (constant).
myFunc(42)The interesting things in typed languages starts with variables on the type level. Called generics in languages like TypeScript, Java, C#, Kotlin. Very hot feature in Go language - fingers crossed. ;)
// TypeScript
// `A` and `x` are two parameters for this function.
// `A` on the type level
// `x` on the value level
const myFunc = <A>(x: A) => x
// Because argument `A` can be inferred from value `x`, it can be omitted.
myFunc(42)
// We can also supply both arguments.
myFunc<number>(42)Here we see this difference between value and type syntax. E.g. type cannot be supplied as an argument to a function or used like a value.
// C#
// Calling function with type as an argument.
myFunc(Integer) // _Syntax_ error!
// Assigning type to a variable.
var x = Int32 // _Syntax_ error!
// Value in position of generic argument.
myFunc<"wrong">(42) // _Syntax_ error!In Idris which is dependently-typed language, values and types are on the same syntactic level and "type" parameter A is defined in the same way as "value" parameter x.
The built-in type Type is the source of all types (universe). Parameters in {} braces are implicit and can be omitted if they can be inferred.
-- Idris
-- `A` and `x` are two parameters for this function.
myFunc : {A : Type} -> (x : A) -> A
myFunc x = x
-- Because argument `A` can be inferred from value `x`, it can be omitted.
myFunc 42
-- We can also supply both arguments.
myFunc {A=Int} 42But even in TypeScript we can see the motivation to erase this distinction. String or number literal types are simple examples where instance of a type is used on the type level.
// TypeScript
// String litarals (as types)
type Color = "Dark Red"
// String instance used in type and value position. Valid syntax.
myFunc<Color>("Dark Red")
myFunc<"Orange">("Orange")
myFunc<"Light Blue">("Dark Red")
// error TS2345: Argument of type '"Dark Red"' is not assignable to parameter of type '"Light Blue"'.
myFunc<Color>("Orange")
// error TS2345: Argument of type '"Orange"' is not assignable to parameter of type 'Color'.So now we can make one step further and imagine type level variable to be a function. Just like we have "normal" value level functions.
In Scala or Haskell higher-kinded types are the abstraction that represents these type level functions. Although they are very restrictive, especially in Scala. In addition, Haskell has a special syntax to define these functions as standalone statements.
Here is one example of a simple state machine written in Idris with translation to Haskell with the help of special type level syntax.
https://gist.github.com/tgrospic/29f0ce0cb63a2ead93aeaccbbf530800
In Scala, we can read F[_] as a function F which accepts one argument. Similary F[_, _] is a function with two arguments. So when we have F[_] and e.g. String we can create a new type F[String].
Examples of instances for this type are List[_], Option[_] or Task[_]. They are defined with generic parameter and all defined operations are independent of the type chosen for this parameter.
// Scala
// `F`, `A` and `x` are three parameters for this function.
def myFunc[F[_]: Applicative, A](x: A): F[A] = x.pure
// If `F` and `A` cannot be inferred, they can be supplied explicitly.
myFunc[List, Int](42)In Haskell we are free from so many required brackets but essentially syntax is very similar.
-- Haskell
-- `f`, `a` and `x` are three parameters for this function.
-- Haskell forces lowercase letters in these positions.
myFunc :: Applicative f => a -> f a
myFunc x = pure x
-- If `f` and `a` cannot be inferred, they can be supplied explicitly.
myFunc @Maybe @Int 42In Idris, again this is much more visible. F is defined as any other function with one parameter, accepting a Type and returns a Type.
-- Idris
-- `F`, `A` and `x` are three parameters for this function.
myFunc : {F : Type -> Type} -> Applicative F => {A : Type} -> (x : A) -> F A
myFunc x = pure x
-- If `F` and `A` cannot be inferred, they can be supplied explicitly.
myFunc {F=List} {A=Int} 42Video: https://youtu.be/xBDN3sczl2c
I wrote similar examples in Haskell. The same as here, starting from deep embedding (also called initial encoding) and abstracting to shallow embedding (final encoding). This is the source of final in tagless final.
https://github.com/tgrospic/rholang-hs/blob/0d8eb81/src/DeepShallow/DeepShallow.hs
import cats.syntax.all._
// Example of effectful function
def isNatOption(x: Int): Option[Boolean] = (x > 0).some
// We are starting from very specific types used in this example function.
// This means that `List` and `Option` implementations are used directly, function
// is dependent on these implementations.
def example1(d: List[Int]): Option[List[Int]] = {
import cats.instances.list._ // imports TraverseFilter[List]
import cats.instances.option._ // imports Applicative[Option]
d.filterA(isNatOption)
}
val r1a = example1(List(1, 2, 3))
// r1a: Option[List[Int]] = Some(List(1, 2, 3))
val r1b = example1(List(-2, -1, 0, 1, 2, 3))
// r1b: Option[List[Int]] = Some(List(0, 1, 2, 3))/*
* We can abstract the result type.
*/
import cats.Applicative
// Instead of specific result type, we introduce `F` as a type level variable.
def isNatF[F[_]: Applicative](x: Int): F[Boolean] = (x > 0).pure
// Applicative is written with "context-bounds" syntactic sugar which is
// replacement for additional implicit parameter to the function.
// https://docs.scala-lang.org/tutorials/FAQ/context-bounds.html#how-are-context-bounds-implemented
def isNatF_[F[_]](x: Int)(implicit ap: Applicative[F]): F[Boolean] = (x > 0).pure
// Calling `pure` is using extension method, we can use Applicative argument directly.
def isNatF_[F[_]](x: Int)(implicit ap: Applicative[F]): F[Boolean] = ap.pure(x > 0)
// We can do this with "context-bounds" style also (with the existence of additional constructor).
def isNatF_[F[_]: Applicative](x: Int): F[Boolean] = Applicative[F].pure(x > 0)
// So now we only depend on TraverseFilter instance for the List,
// F is a parameter and must implement Applicative interface (trait).
def example2[F[_] : Applicative](d: List[Int]): F[List[Int]] = {
import cats.instances.list._ // imports TraverseFilter[List]
d.filterA(isNatF[F])
}
// Ups, do we have Applicative instance in scope?? It seems that we get one by default from _cats_.
// `Id` is the simplest type, the only thing it can do is to wrap a _pure_ value.
val r2 = example2(List(-2, -1, 1, 2, 3))
// r2: cats.package.Id[List[Int]] = List(1, 2, 3)
// We can specify this instance explicitly.
val r2a = example2(List(-2, -1, 1, 2, 3))(cats.catsInstancesForId)
// r2a: cats.Id[List[Int]] = List(1, 2, 3)
val r2b = {
// If list instance is imported it will take precedence.
import cats.instances.list._ // imports Applicative[List]
example2(List(-2, -1, 1, 2, 3))
}
// r2b: List[List[Int]] = List(List(1, 2, 3))
val r2c = {
// Because our function is now parametric in Applicative type we can
// return result wrapped in Option type just by importing different instance.
// We can import just one instance and not all as with wildcard _.
import cats.instances.option.catsStdInstancesForOption // imports Applicative[Option]
example2(List(-2, -1, 1, 2, 3))
// example2(List(-2, -1, 1, 2, 3))(cats.instances.option.catsStdInstancesForOption)
}
// r2c: Option[List[Int]] = Some(List(1, 2, 3))
val r2d = {
// We can "manually" define implicit argument for Applicative implementation.
// This is exactly what `import cats.instances.option.catsStdInstancesForOption`
// will do because `catsStdInstancesForOption` is defined as implicit value.
implicit val ap = cats.instances.option.catsStdInstancesForOption
example2(List(-2, -1, 1, 2, 3))
// example2(List(-2, -1, 1, 2, 3))(ap) // which will execute this
}
// r2d: Option[List[Int]] = Some(List(1, 2, 3))/*
* We can do the same technique and abstract the input type also.
*/
import cats.TraverseFilter
// List is now type variable G that must implement TraverseFilter trait.
def example3[F[_]: Applicative, G[_]: TraverseFilter](d: G[Int]): F[G[Int]] =
d.filterA(isNatF[F])
val r3a = {
// If we add list instance in scope result will be List.
import cats.instances.list._ // imports Applicative[List], TraverseFilter[List]
example3(List(-2, -1, 1, 2, 3))
}
// r3a: List[List[Int]] = List(List(1, 2, 3))
val r3b = {
// If option instance is in scope result will be Option.
import cats.instances.option._ // imports Applicative[Option], TraverseFilter[Option]
example3((-2).some)
}
// r3b: Option[Option[Int]] = Some(None)
val r3c = {
// If multiple instances can satisfy implicit parameter an error is thrown.
import cats.instances.list._ // imports Applicative[List], TraverseFilter[List]
import cats.instances.option._ // imports Applicative[Option], TraverseFilter[Option]
// example3(2.some)
}
// Error:(99, 11) ambiguous implicit values:
// both value catsStdInstancesForList in trait ListInstances of type => cats.Traverse[List] with cats.Alternative[List] with cats.Monad[List] with cats.CoflatMap[List] with cats.Align[List]
// and value catsStdInstancesForOption in trait OptionInstances of type => cats.Traverse[Option] with cats.MonadError[Option,Unit] with cats.Alternative[Option] with cats.CommutativeMonad[Option] with cats.CoflatMap[Option] with cats.Align[Option]
// match expected type cats.Applicative[F]
// example3(2.some)
val r3d = {
// We can "pick" only instances that we want to use and ensure they don't overlap.
import cats.instances.list.catsStdTraverseFilterForList
import cats.instances.option.catsStdInstancesForOption
example3(List(-2, -1, 1, 2, 3))
}
// r3d: Option[List[Int]] = Some(List(1, 2, 3))L.G. Meredith - Monadic Design Patterns for the Web
https://channel9.msdn.com/Series/C9-Lectures-Greg-Meredith-Monadic-Design-Patterns-for-the-Web
Beautiful, Simple, Testable Functional Effects for Scala
https://degoes.net/articles/zio-environment
Monad in cats - sequential execution flow.
https://typelevel.org/cats/typeclasses/monad.html
Effects in cats. Monad + suspend + concurrent execution flow.
https://typelevel.org/cats-effect/typeclasses/
Lambda World 2018 - A roadtrip with monads: from MTL, through tagless to BIO - Paweł Szulc
https://youtu.be/eth4y015BCU
Advanced Tagless Final - Saying farewell to Free (Luka Jacobowitz)
https://youtu.be/E9iRYNuTIYA