"Distributive property"与无形

Question

不确定是否正确的术语是"分配性";但我记得我在学校里学过这个，所以这里有一个我正在尝试做的例子:

给定:

type MyHList = (A :+: B :+: C :+: CNil) :: (Foo :+: Bar :+: CNil) :: HNil

在Shapeless中是否有任何内置类型类来输出这个:

type Out = (A, Foo) :+: (A, Bar) :+: (B, Foo) :+: (B, Bar) :+: (C, Foo) :+: (C, Bar) :+: CNil

?

感谢

Answer 1

我会称这种变换为笛卡尔变换、张量变换或直积变换(即每一项与每一项的乘积，与内积/标量积/压缩相反)。虽然它确实与分配律有关。

我想从字面上看没有这样的标准类型类但是它可以通过标准类型来表达

import shapeless.{:+:, ::, CNil, Coproduct, HList, HNil, Poly1, poly}
import shapeless.ops.coproduct.{FlatMap, Mapper}
trait Cartesian[L <: HList] {
type Out <: Coproduct
}
object Cartesian {
type Aux[L <: HList, Out0 <: Coproduct] = Cartesian[L] { type Out = Out0 }
implicit def mkCartesian[C <: Coproduct, C1 <: Coproduct](implicit
flatMap: FlatMap[C, MapperPoly[C1]]
): Aux[C :: C1 :: HNil, flatMap.Out] = null
trait MapperPoly[C <: Coproduct] extends Poly1
object MapperPoly {
implicit def cse[C <: Coproduct, A](implicit
mapper: Mapper[TuplePoly[A], C]
): poly.Case1.Aux[MapperPoly[C], A, mapper.Out] = null
}
trait TuplePoly[A] extends Poly1
object TuplePoly {
implicit def cse[A, B]: poly.Case1.Aux[TuplePoly[A], B, (A, B)] = null
}
}
implicitly[Cartesian.Aux[MyHList, Out]] // compiles

类型类Cartesian现在只作用于类型级别。在值级别上，它的定义可能会有点棘手(poly.Case1.Aux[P, ...为P <: MapperPoly[C],poly.Case1.Aux[P, ...为P <: TuplePoly[A]，而不是poly.Case1.Aux[MapperPoly[C], ...,poly.Case1.Aux[TuplePoly[A], ...，并使用Unpack1，参见使用超类型筛选HList)。更新:或者不是:)

还可以选择递归地定义自定义类型类，而不是尝试将所有内容推断为标准类型类。

---

这是Coproducts(不一定是两个)的多个HLists的递归类型级实现

// transforms an hlist of coproducts into a coproduct of tuples
trait Cartesian[L <: HList] {
type Out <: Coproduct
}
object Cartesian {
type Aux[L <: HList, Out0 <: Coproduct] = Cartesian[L] { type Out = Out0 }
implicit def mkCartesian[L <: HList, C <: Coproduct](implicit
cartesian: CartesianHelper.Aux[L, C],
mapper: coproduct.Mapper[tuplerPoly.type, C]
): Aux[L, mapper.Out] = null
object tuplerPoly extends Poly1 {
implicit def cse[L <: HList](implicit
tupler: hlist.Tupler[L]
): Case.Aux[L, tupler.Out] = null
}
}
// transforms an hlist of coproducts into a coproduct of hlists
trait CartesianHelper[L <: HList] {
type Out <: Coproduct
}
trait LowPriorityHelper1 {
type Aux[L <: HList, Out0 <: Coproduct] = CartesianHelper[L] { type Out = Out0 }
// (a + (a1+...)) * (b1+...) * (c1+...) * ... 
//  = a * ((b1+...) * (c1+...) * ...) 
//  + ((a1+...) * (b1+...) * (c1+...) * ...)
implicit def recurse[H, T <: Coproduct, T1 <: HList,
C <: Coproduct, C1 <: Coproduct, C2 <: Coproduct](implicit
ev: T1 <:< (_ :: _),
cartesian: Aux[T1, C],
mapper: coproduct.Mapper.Aux[PrependPoly[H], C, C1],
cartesian1: Aux[T :: T1, C2],
extendBy: coproduct.ExtendBy[C1, C2]
): Aux[(H :+: T) :: T1, extendBy.Out] = null
trait PrependPoly[H] extends Poly1
object PrependPoly {
implicit def cse[H, L <: HList]: poly.Case1.Aux[PrependPoly[H], L, H :: L] = null
}
}
trait LowPriorityHelper extends LowPriorityHelper1 {
implicit def one[C <: Coproduct](implicit 
mapper: coproduct.Mapper[prependPoly.type, C]
): Aux[C :: HNil, mapper.Out] = null
object prependPoly extends Poly1 {
implicit def cse[A]: Case.Aux[A, A :: HNil] = null
}
}
object CartesianHelper extends LowPriorityHelper {
implicit def hnil: Aux[HNil, CNil] = null
implicit def cnil[T <: HList]: Aux[CNil :: T, CNil] = null
}
type MyHList1 = (A :+: B :+: C :+: CNil) :: (Foo :+: Bar :+: CNil) :: (X :+: Y :+: CNil) :: HNil
type Out1 = (A, Foo, X) :+: (A, Foo, Y) :+: (A, Bar, X) :+: (A, Bar, Y) :+: (B, Foo, X) :+: (B, Foo, Y) :+:
(B, Bar, X) :+: (B, Bar, Y) :+: (C, Foo, X) :+: (C, Foo, Y) :+:  (C, Bar, X) :+: (C, Bar, Y) :+: CNil
implicitly[Cartesian.Aux[MyHList1, Out1]] // compiles

---

添加值级别:

def cartesian[L <: HList](l: L)(implicit cart: Cartesian[L]): cart.Out = cart(l)
trait Cartesian[L <: HList] extends DepFn1[L] {
type Out <: Coproduct
}
object Cartesian {
type Aux[L <: HList, Out0 <: Coproduct] = Cartesian[L] { type Out = Out0 }
def instance[L <: HList, Out0 <: Coproduct](f: L => Out0): Aux[L, Out0] =
new Cartesian[L] {
override type Out = Out0
override def apply(l: L): Out0 = f(l)
}
implicit def mkCartesian[L <: HList, C <: Coproduct](implicit
cartesian: CartesianHelper.Aux[L, C],
mapper: coproduct.Mapper[tuplerPoly.type, C]
): Aux[L, mapper.Out] = instance(l => mapper(cartesian(l)))
object tuplerPoly extends Poly1 {
implicit def cse[L <: HList](implicit
tupler: hlist.Tupler[L]
): Case.Aux[L, tupler.Out] = at(tupler(_))
}
}
trait CartesianHelper[L <: HList] extends DepFn1[L] {
type Out <: Coproduct
}
trait LowPriorityHelper1 {
type Aux[L <: HList, Out0 <: Coproduct] = CartesianHelper[L] { type Out = Out0 }
def instance[L <: HList, Out0 <: Coproduct](f: L => Out0): Aux[L, Out0] =
new CartesianHelper[L] {
override type Out = Out0
override def apply(l: L): Out0 = f(l)
}
implicit def recurse[H, T <: Coproduct, T1 <: HList,
C <: Coproduct, C1 <: Coproduct, C2 <: Coproduct](implicit
ev: T1 <:< (_ :: _),
cartesian: Aux[T1, C],
prepend: Prepend.Aux[H, C, C1],
cartesian1: Aux[T :: T1, C2],
extendBy: coproduct.ExtendBy[C1, C2]
): Aux[(H :+: T) :: T1, extendBy.Out] =
instance(l => {
val t1 = l.tail
val c = cartesian(t1)
l.head.eliminate(h => {
val c1 = prepend(h, c)
extendBy.right(c1)
}, t => {
val c2 = cartesian1(t :: t1)
extendBy.left(c2)
})
})
// custom type class instead of mapping with a generic Poly
trait Prepend[H, C <: Coproduct] extends DepFn2[H, C] {
type Out <: Coproduct
}
object Prepend {
type Aux[H, C <: Coproduct, Out0 <: Coproduct] = Prepend[H, C] { type Out = Out0 }
def instance[H, C <: Coproduct, Out0 <: Coproduct](f: (H, C) => Out0): Aux[H, C, Out0] =
new Prepend[H, C] {
override type Out = Out0
override def apply(h: H, c: C): Out0 = f(h, c)
}
implicit def cnil[H]: Aux[H, CNil, CNil] = instance((_, _) => unexpected)
implicit def ccons[H, L <: HList, C <: Coproduct](implicit
prepend: Prepend[H, C]
): Aux[H, L :+: C, (H :: L) :+: prepend.Out] =
instance((h, c) =>
c.eliminate(
l => Inl(h :: l),
c => Inr(prepend(h, c))
)
)
}
}
trait LowPriorityHelper extends LowPriorityHelper1 {
implicit def one[C <: Coproduct](implicit
mapper: coproduct.Mapper[prependPoly.type, C]
): Aux[C :: HNil, mapper.Out] = instance(l => mapper(l.head))
object prependPoly extends Poly1 {
implicit def cse[A]: Case.Aux[A, A :: HNil] = at(_ :: HNil)
}
}
object CartesianHelper extends LowPriorityHelper {
implicit def hnil: Aux[HNil, CNil] = instance(_ => unexpected)
implicit def cnil[T <: HList]: Aux[CNil :: T, CNil] = instance(_ => unexpected)
}
val c: C = new C {}
val bar: Bar = new Bar {}
val myHList: MyHList = Inr(Inr(Inl(c))) :: Inr(Inl(bar)) :: HNil
val res = cartesian(myHList)
res: Out // compiles
res == Inr(Inr(Inr(Inr(Inr(Inl((c, bar))))))) // true

我用自定义类型类Prepend[H, C <: Coproduct]替换了与PrependPoly[H]的协积映射，因为通用的Poly是棘手的，并不是所有的事情都可以在值级别上用它们完成。

问题#198:向调用方法之外定义的Poly注入值是尴尬的

issue #154:改进对poly的部分应用的支持

向多态函数传递额外的参数?

选择HList of Lists的第n个元素，并返回该值作为HList of values

动态参数化Poly1函数

shapelless -dev: How to parameterize"保利函数?

HList折叠函数，需要HList

参数化list of Lists中元素的过滤

---

参见:

取Seq[_]的HList，用值的笛卡尔积生成Seq[HList]

异构表的笛卡尔积(Haskell)