Was sind Typ Lambdas in Scala und was sind ihre Vorteile?

152

Irgendwann stolpere ich in die halb mysteriöse Notation von

def f[T](..) = new T[({type l[A]=SomeType[A,..]})#l] {..} 

in Scala-Blog-Posts, die eine Handwelle "Wir haben diesen Typ-Lambda-Trick verwendet" geben.

Obwohl ich eine gewisse Intuition darüber habe (wir erhalten einen anonymen Typparameter, Aohne die Definition damit verschmutzen zu müssen?), Habe ich keine eindeutige Quelle gefunden, die beschreibt, was der Typ-Lambda-Trick ist und welche Vorteile er hat. Ist es nur syntaktischer Zucker oder eröffnet es neue Dimensionen?

Ron
quelle
Siehe auch .
Shelby Moore III

Antworten:

148

Typ Lambdas sind ziemlich wichtig, wenn Sie mit höherwertigen Typen arbeiten.

Betrachten Sie ein einfaches Beispiel für die Definition einer Monade für die richtige Projektion von Entweder [A, B]. Die Monaden-Typklasse sieht folgendermaßen aus:

trait Monad[M[_]] {
  def point[A](a: A): M[A]
  def bind[A, B](m: M[A])(f: A => M[B]): M[B]
}

Jetzt ist entweder ein Typkonstruktor mit zwei Argumenten, aber um Monad zu implementieren, müssen Sie ihm einen Typkonstruktor mit einem Argument geben. Die Lösung hierfür besteht darin, einen Lambda-Typ zu verwenden:

class EitherMonad[A] extends Monad[({type λ[α] = Either[A, α]})#λ] {
  def point[B](b: B): Either[A, B]
  def bind[B, C](m: Either[A, B])(f: B => Either[A, C]): Either[A, C]
}

Dies ist ein Beispiel für das Currying im Typsystem. Sie haben den Typ "Entweder" festgelegt. Wenn Sie also eine Instanz von "Entweder" erstellen möchten, müssen Sie einen der Typen angeben. Der andere wird natürlich zu dem Zeitpunkt geliefert, an dem Sie point oder bind aufrufen.

Der Typ-Lambda-Trick nutzt die Tatsache aus, dass ein leerer Block an einer Typposition einen anonymen Strukturtyp erstellt. Wir verwenden dann die # -Syntax, um ein Typmitglied zu erhalten.

In einigen Fällen benötigen Sie möglicherweise anspruchsvollere Lambdas, die nur schwer inline geschrieben werden können. Hier ist ein Beispiel aus meinem Code von heute:

// types X and E are defined in an enclosing scope
private[iteratee] class FG[F[_[_], _], G[_]] {
  type FGA[A] = F[G, A]
  type IterateeM[A] = IterateeT[X, E, FGA, A] 
}

Diese Klasse existiert ausschließlich, damit ich einen Namen wie FG [F, G] #IterateeM verwenden kann, um auf den Typ der IterateeT-Monade zu verweisen, die auf eine Transformatorversion einer zweiten Monade spezialisiert ist, die auf eine dritte Monade spezialisiert ist. Wenn Sie anfangen zu stapeln, werden diese Arten von Konstrukten sehr notwendig. Ich instanziiere natürlich nie eine FG; Es ist nur ein Hack, mit dem ich ausdrücken kann, was ich im Typensystem will.

Kris Nuttycombe
quelle
3
Interessant zu bemerken, dass Haskell Lambdas auf Typebene nicht direkt unterstützt , obwohl einige Newtype-Hacker (z. B. die TypeCompose-Bibliothek) Möglichkeiten haben, dies zu umgehen.
Dan Burton
1
Ich wäre gespannt, wie Sie die bindMethode für Ihre EitherMonadKlasse definieren. :-) Abgesehen davon, wenn ich Adriaan hier für eine Sekunde kanalisieren darf, verwenden Sie in diesem Beispiel keine höherwertigen Typen. Du bist dabei FG, aber nicht dabei EitherMonad. Sie verwenden vielmehr Typkonstruktoren , die kind haben * => *. Diese Art ist von Ordnung 1, die nicht "höher" ist.
Daniel Spiewak
2
Ich dachte, diese Art wäre *Ordnung 1, aber auf jeden Fall hat Monad Art (* => *) => *. Sie werden auch feststellen, dass ich "die richtige Projektion von Either[A, B]" angegeben habe - die Implementierung ist trivial (aber eine gute Übung, wenn Sie es noch nicht getan haben!)
Kris Nuttycombe
Ich vermute, Daniels Argument, nicht *=>*höher zu rufen, wird durch die Analogie gerechtfertigt, dass wir keine gewöhnliche Funktion (die Nichtfunktionen Nichtfunktionen zuordnet, dh einfache Werte einfachen Werten zuordnen) Funktion höherer Ordnung rechtfertigen.
Jhegedus
1
Pierces TAPL-Buch, Seite 442:Type expressions with kinds like (*⇒*)⇒* are called higher-order typeoperators.
Jhegedus
52

Die Vorteile sind genau die gleichen wie die, die durch anonyme Funktionen gewährt werden.

def inc(a: Int) = a + 1; List(1, 2, 3).map(inc)

List(1, 2, 3).map(a => a + 1)

Eine beispielhafte Verwendung mit Scalaz 7. Wir möchten eine verwenden Functor, die eine Funktion über das zweite Element in a abbilden kann Tuple2.

type IntTuple[+A]=(Int, A)
Functor[IntTuple].map((1, 2))(a => a + 1)) // (1, 3)

Functor[({type l[a] = (Int, a)})#l].map((1, 2))(a => a + 1)) // (1, 3)

Scalaz bietet einige implizite Konvertierungen, auf die das Typargument schließen kann. Daher Functorvermeiden wir es oft, diese vollständig zu schreiben. Die vorherige Zeile kann wie folgt umgeschrieben werden:

(1, 2).map(a => a + 1) // (1, 3)

Wenn Sie IntelliJ verwenden, können Sie Einstellungen, Codestil, Scala, Falten und Typ Lambdas aktivieren. Dies verbirgt dann die muffigen Teile der Syntax und präsentiert die schmackhafteren:

Functor[[a]=(Int, a)].map((1, 2))(a => a + 1)) // (1, 3)

Eine zukünftige Version von Scala unterstützt eine solche Syntax möglicherweise direkt.

Retronym
quelle
Das letzte Snippet sieht wirklich gut aus. IntelliJ Scala Plugin ist sicherlich super!
AndreasScheinert
1
Vielen Dank! Das Lambda fehlt möglicherweise im letzten Beispiel. Warum haben Tupel-Funktoren den letzten Wert transformiert? Ist es Konvention / ein praktischer Standard?
Ron
1
Ich leite Nightlies für Nika und habe die beschriebene IDEA-Option nicht. Interessanterweise gibt es eine Inspektion für "Applied Type Lambda kann vereinfacht werden."
Randall Schulz
6
Es wird zu Einstellungen -> Editor -> Code-Faltung verschoben.
Retronym
@retronym, ich habe beim Versuch (1, 2).map(a => a + 1)in REPL einen Fehler erhalten : `<Konsole>: 11: Fehler: Wertzuordnung ist kein Mitglied von (Int, Int) (1, 2) .map (a => a + 1) ^`
Kevin Meredith
41

Um die Dinge in einen Zusammenhang zu bringen: Diese Antwort wurde ursprünglich in einem anderen Thread veröffentlicht. Sie sehen es hier, weil die beiden Threads zusammengeführt wurden. Die Fragestellung in diesem Thread lautete wie folgt:

So lösen Sie diese Typdefinition auf: Pure [({type? [A] = (R, a)}) #?]?

Was sind die Gründe für die Verwendung einer solchen Konstruktion?

Snipped stammt aus der Scalaz-Bibliothek:

trait Pure[P[_]] {
  def pure[A](a: => A): P[A]
}

object Pure {
  import Scalaz._
//...
  implicit def Tuple2Pure[R: Zero]: Pure[({type ?[a]=(R, a)})#?] = new Pure[({type ?[a]=(R, a)})#?] {
  def pure[A](a: => A) = (Ø, a)
  }

//...
}

Antworten:

trait Pure[P[_]] {
  def pure[A](a: => A): P[A]
}

Der eine Unterstrich in den Feldern danach Pimpliziert, dass es sich um einen Typkonstruktor handelt, der einen Typ verwendet und einen anderen Typ zurückgibt. Beispiele für Typkonstruktoren dieser Art: List, Option.

Geben Sie Listein Int, einen konkreten Typ, und es gibt Ihnen einen List[Int]weiteren konkreten Typ. Gib Listein Stringund es gibt dir List[String]. Etc.

Also List, Optionkann in Betracht gezogen werden Typ - Level - Funktionen von arity sein 1. Formal wir sagen, sie haben eine Art * -> *. Das Sternchen kennzeichnet einen Typ.

Jetzt Tuple2[_, _]ist ein Typkonstruktor mit kind, (*, *) -> *dh Sie müssen ihm zwei Typen geben, um einen neuen Typ zu erhalten.

Da ihre Signaturen nicht übereinstimmen, können Sie nicht ersetzen Tuple2für P. Was Sie tun müssen, ist teilweise Tuple2 auf eines seiner Argumente anzuwenden , wodurch wir einen Typkonstruktor mit kind erhalten * -> *, und wir können ihn ersetzen P.

Leider hat Scala keine spezielle Syntax für die teilweise Anwendung von Typkonstruktoren, weshalb wir auf die Monstrosität zurückgreifen müssen, die als Typ Lambdas bezeichnet wird. (Was Sie in Ihrem Beispiel haben.) Sie werden so genannt, weil sie analog zu Lambda-Ausdrücken sind, die auf Wertebene existieren.

Das folgende Beispiel könnte helfen:

// VALUE LEVEL

// foo has signature: (String, String) => String
scala> def foo(x: String, y: String): String = x + " " + y
foo: (x: String, y: String)String

// world wants a parameter of type String => String    
scala> def world(f: String => String): String = f("world")
world: (f: String => String)String

// So we use a lambda expression that partially applies foo on one parameter
// to yield a value of type String => String
scala> world(x => foo("hello", x))
res0: String = hello world


// TYPE LEVEL

// Foo has a kind (*, *) -> *
scala> type Foo[A, B] = Map[A, B]
defined type alias Foo

// World wants a parameter of kind * -> *
scala> type World[M[_]] = M[Int]
defined type alias World

// So we use a lambda lambda that partially applies Foo on one parameter
// to yield a type of kind * -> *
scala> type X[A] = World[({ type M[A] = Foo[String, A] })#M]
defined type alias X

// Test the equality of two types. (If this compiles, it means they're equal.)
scala> implicitly[X[Int] =:= Foo[String, Int]]
res2: =:=[X[Int],Foo[String,Int]] = <function1>

Bearbeiten:

Weitere Parallelen auf Wertebene und Typenebene.

// VALUE LEVEL

// Instead of a lambda, you can define a named function beforehand...
scala> val g: String => String = x => foo("hello", x)
g: String => String = <function1>

// ...and use it.
scala> world(g)
res3: String = hello world

// TYPE LEVEL

// Same applies at type level too.
scala> type G[A] = Foo[String, A]
defined type alias G

scala> implicitly[X =:= Foo[String, Int]]
res5: =:=[X,Foo[String,Int]] = <function1>

scala> type T = World[G]
defined type alias T

scala> implicitly[T =:= Foo[String, Int]]
res6: =:=[T,Foo[String,Int]] = <function1>

In dem von Ihnen vorgestellten Fall ist der Typparameter Rfür die Funktion lokal Tuple2Pureund kann daher nicht einfach definiert werden type PartialTuple2[A] = Tuple2[R, A], da es einfach keinen Ort gibt, an dem Sie dieses Synonym einfügen können.

Um mit einem solchen Fall umzugehen, verwende ich den folgenden Trick, bei dem Typelemente verwendet werden. (Hoffentlich ist das Beispiel selbsterklärend.)

scala> type Partial2[F[_, _], A] = {
     |   type Get[B] = F[A, B]
     | }
defined type alias Partial2

scala> implicit def Tuple2Pure[R]: Pure[Partial2[Tuple2, R]#Get] = sys.error("")
Tuple2Pure: [R]=> Pure[[B](R, B)]
fehlender Faktor
quelle
0

type World[M[_]] = M[Int]Ich denke, dass alles, was wir Ain X[A]das implicitly[X[A] =:= Foo[String,Int]]eingeben, immer wahr ist.

wiesiu_p
quelle