Cosa sono i tipi lambda in Scala e quali sono i loro benefici?

Question

A volte mi inciampare in notazione semi-misterioso

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

in Scala post del blog, che danno un "abbiamo usato quel tipo-lambda trucco" handwave.

Mentre ho qualche intuito su questo (otteniamo un parametro di tipo anonimo A senza dover inquinare la definizione con esso?), Non ho trovato alcuna fonte chiara che descriva il tipo di lambda trick, e quali sono i suoi benefici. È solo zucchero sintattico o apre nuove dimensioni?

Answer 1

I lambda di tipo sono fondamentali un po 'di tempo quando si lavora con tipi di tipo superiore.

Considerare un semplice esempio di definizione di una monade per la proiezione destra di E [A, B]. Il typeclass monade si presenta così:

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

Ora, o è un tipo di costruzione di due argomenti, ma per implementare Monade, è necessario dare un tipo di costruzione di un argomento. La soluzione a questo è quella di utilizzare un tipo di lambda:

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] 
} 

Questo è un esempio di currying nel sistema tipo - è stato al curry il tipo di entrambi i casi, in modo tale che quando si desidera creare un'istanza di EitherMonad, è devi specificare uno dei tipi; l'altro, naturalmente, viene fornito nel momento in cui si chiama punto o bind.

Il tipo lambda trick sfrutta il fatto che un blocco vuoto in una posizione di tipo crea un tipo strutturale anonimo. Quindi usiamo la sintassi # per ottenere un membro del tipo.

In alcuni casi, potrebbero essere necessari tipi di lambda più sofisticati che sono difficili da scrivere in linea. Ecco un esempio dal mio codice da oggi:

// 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] 
} 

Questa classe esiste esclusivamente in modo che possa utilizzare un nome come FG [F, G] #IterateeM per fare riferimento al tipo di IterateeT Monade specializzato per qualche versione del trasformatore di una seconda monade che è specializzata in qualche terza monade. Quando inizi a impilare, questi tipi di costrutti diventano molto necessari. Non istanziamo mai un FG, naturalmente; è proprio lì come un trucco per farmi esprimere ciò che voglio nel sistema di tipi.

Answer 2

I vantaggi sono esattamente uguali a quelli conferiti dalle funzioni anonime.

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

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

Un esempio d'uso, con Scalaz 7. vogliamo usare un Functor che può mappare una funzione sul secondo elemento in un 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 fornisce alcune conversioni implicite che possono dedurre l'argomento di tipo a Functor, così spesso evitare crei questi del tutto. La riga precedente può essere riscritta come:

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

Se si utilizza IntelliJ, è possibile attivare Impostazioni, Codice di stile, Scala, pieghevole, tipo lambda.Questo poi hides the crufty parts of the syntax, e presenta la più appetibile:

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

Una futura versione di Scala potrebbe sostenere direttamente una tale sintassi.

Answer 3

Per mettere le cose nel contesto: questa risposta è stata originariamente pubblicata in un'altra discussione. Lo stai vedendo qui perché i due thread sono stati uniti. La dichiarazione domanda nel detto filo è stato il seguente:

How to resolve this type definition: Pure[({type ?[a]=(R, a)})#?] ?

What are the reasons of using such construction?

Snipped comes from scalaz library:

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) 
    } 

//... 
} 

---

Risposta:

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

Quello sottolineatura nelle caselle dopo P implica che si tratta di un costruttore di tipo richiede un tipo e restituisce un altro tipo. Esempi di costruttori di tipi con questo tipo: List, Option.

Dare List un Int, un tipo concreto e ti dà List[Int], un altro tipo concreto. Dare List a String e ti dà List[String]. Etc.

Quindi, List, Option possono essere considerati funzioni di livello tipo di cortesia 1. Formalmente diciamo che hanno un tipo * -> *. L'asterisco indica un tipo.

Ora Tuple2[_, _] è un tipo di costruttore con tipo (*, *) -> *, ad esempio è necessario dargli due tipi per ottenere un nuovo tipo.

Poiché le loro firme non corrispondono, non è possibile sostituire Tuple2 per P. Quello che devi fare è parzialmente applicareTuple2 su uno dei suoi argomenti, che ci fornirà un costruttore di tipo con il tipo * -> *, e possiamo sostituirlo con P.

Purtroppo Scala non ha una sintassi speciale per l'applicazione parziale dei costruttori di tipi, e quindi dobbiamo ricorrere alla mostruosità chiamata tipo lambda. (Quello che hai nel tuo esempio.) Sono chiamati così perché sono analoghi alle espressioni lambda che esistono a livello di valore.

L'esempio che segue potrebbe aiutare:

// 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> 

Modifica:

livello più valore e il livello di tipo parallelo.

// 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> 

Nel caso che avete presentato, il parametro di tipo R è locale a funzionare Tuple2Pure e quindi non si può semplicemente definire type PartialTuple2[A] = Tuple2[R, A], semplicemente perché non c'è nessun posto dove si può mettere quello sinonimo.

Per risolvere un caso del genere, utilizzo il seguente trucco che utilizza i membri di tipo. (Si spera che l'esempio sia auto-esplicativo.)

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)] 

Answer 4

type World[M[_]] = M[Int] fa sì che tutto ciò che abbiamo messo in A nel X[A] il implicitly[X[A] =:= Foo[String,Int]] è sempre vero credo.