Creazione di una lista HList di tutte le coppie da due liste HL

Question

Sto usando shapeless in Scala e mi piacerebbe scrivere una funzione allPairs che richiederà due HLists e restituirà una lista HList di tutte le coppie di elementi. Ad esempio:

import shapeless._ 
val list1 = 1 :: "one" :: HNil 
val list2 = 2 :: "two" :: HNil 
// Has value (1, 2) :: (1, "two") :: ("one", 2) :: ("one", "two") :: HNil 
val list3 = allPairs(list1, list2) 

Qualche idea su come procedere?

Inoltre, vorrei sottolineare che sto cercando una funzione, non un blocco di codice inline.

Answer 1

Non è possibile utilizzare un for -comprehension o una combinazione di map e flatMap con letterali di funzione qui (come le altre risposte suggeriscono), dal momento che questi metodi su HList richiedono higher rank functions. Se v'è solo due tipizzazione statica liste, questo è facile:

import shapeless._ 

val xs = 1 :: 'b :: 'c' :: HNil 
val ys = 4.0 :: "e" :: HNil 

object eachFirst extends Poly1 { 
    implicit def default[A] = at[A] { a => 
    object second extends Poly1 { implicit def default[B] = at[B](a -> _) } 
    ys map second 
    } 
} 

val cartesianProductXsYs = xs flatMap eachFirst 

che ci dà la seguente (opportunamente digitato):

(1,4.0) :: (1,e) :: ('b,4.0) :: ('b,e) :: (c,4.0) :: (c,e) :: HNil 

Scrivere un metodo che farà questo con HList argomenti è più complicato. Ecco un rapido esempio di come può essere fatto (con alcuni macchinari un po 'più generali).

Inizierò osservando che possiamo pensare di trovare il prodotto cartesiano di due liste ordinarie come "sollevamento" di una funzione che prende due argomenti e li restituisce come una tupla nel funtore applicativo per le liste. Ad esempio, è possibile scrivere the following in Haskell:

import Control.Applicative (liftA2) 

cartesianProd :: [a] -> [b] -> [(a, b)] 
cartesianProd = liftA2 (,) 

Possiamo scrivere una funzione binaria polimorfica che corrisponde a (,) qui:

import shapeless._ 

object tuple extends Poly2 { 
    implicit def whatever[A, B] = at[A, B] { case (a, b) => (a, b) } 
} 

E definire il nostro esempio elenca ancora per completezza:

val xs = 1 :: 'b :: 'c' :: HNil 
val ys = 4.0 :: "e" :: HNil 

Ora lavoreremo su un metodo denominato liftA2 che ci consentirà di scrivere quanto segue:

liftA2(tuple)(xs, ys) 

E ottenere il risultato corretto. Il nome liftA2 è un po 'fuorviante, poiché non abbiamo un'istanza di functor applicativo e poiché non è generico, sto lavorando sul modello dei metodi flatMap e map su HList e sono aperto a suggerimenti per qualcosa meglio.

Ora abbiamo bisogno di una classe tipo che ci permetterà di prendere una Poly2, parzialmente applichiamo a qualcosa, e mappa la funzione unaria risultante su un HList:

trait ApplyMapper[HF, A, X <: HList, Out <: HList] { 
    def apply(a: A, x: X): Out 
} 

object ApplyMapper { 
    implicit def hnil[HF, A] = new ApplyMapper[HF, A, HNil, HNil] { 
    def apply(a: A, x: HNil) = HNil 
    } 
    implicit def hlist[HF, A, XH, XT <: HList, OutH, OutT <: HList](implicit 
    pb: Poly.Pullback2Aux[HF, A, XH, OutH], 
    am: ApplyMapper[HF, A, XT, OutT] 
) = new ApplyMapper[HF, A, XH :: XT, OutH :: OutT] { 
    def apply(a: A, x: XH :: XT) = pb(a, x.head) :: am(a, x.tail) 
    } 
} 

E ora una classe tipo per aiutare con il sollevamento:

trait LiftA2[HF, X <: HList, Y <: HList, Out <: HList] { 
    def apply(x: X, y: Y): Out 
} 

object LiftA2 { 
    implicit def hnil[HF, Y <: HList] = new LiftA2[HF, HNil, Y, HNil] { 
    def apply(x: HNil, y: Y) = HNil 
    } 

    implicit def hlist[ 
    HF, XH, XT <: HList, Y <: HList, 
    Out1 <: HList, Out2 <: HList, Out <: HList 
    ](implicit 
    am: ApplyMapper[HF, XH, Y, Out1], 
    lift: LiftA2[HF, XT, Y, Out2], 
    prepend : PrependAux[Out1, Out2, Out] 
) = new LiftA2[HF, XH :: XT, Y, Out] { 
    def apply(x: XH :: XT, y: Y) = prepend(am(x.head, y), lift(x.tail, y)) 
    } 
} 

E infine il nostro metodo stesso:

def liftA2[HF, X <: HList, Y <: HList, Out <: HList](hf: HF)(x: X, y: Y)(implicit 
    lift: LiftA2[HF, X, Y, Out] 
) = lift(x, y) 

E questo è tutto-ora liftA2(tuple)(xs, ys) funziona.

scala> type Result = 
    | (Int, Double) :: (Int, String) :: 
    | (Symbol, Double) :: (Symbol, String) :: 
    | (Char, Double) :: (Char, String) :: HNil 
defined type alias Result 

scala> val res: Result = liftA2(tuple)(xs, ys) 
res: Result = (1,4.0) :: (1,e) :: ('b,4.0) :: ('b,e) :: (c,4.0) :: (c,e) :: HNil 

Proprio come volevamo.