«Распределительная собственность» с Shapeless

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теперь действует только на уровне типа. Возможно, на уровне значений его определение будет немного сложнее (с for P <: MapperPoly[C], poly.Case1.Aux[P, ...для P <: TuplePoly[A]скорее, чем poly.Case1.Aux[MapperPoly[C], ..., poly.Case1.Aux[TuplePoly[A], ...и используя Unpack1, см. Фильтрация HList с помощью супертипа ).Обновление: А может и нет :)

Также всегда есть возможность рекурсивно определить пользовательский класс типов, а не пытаться вывести все в стандартные классы типов.

---

Вот рекурсивная реализация на уровне типов для несколькихHListс изCoproductс (не обязательно два)

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

Я заменил отображение побочного продукта наPrependPoly[H]по классу пользовательского типаPrepend[H, C <: Coproduct]потому что общийPolyсложны, и не все можно сделать с ними на ценностном уровне.

проблема № 198: неудобно вводить значения в Poly, определенный вне вызывающего метода

issue #154: Улучшена поддержка частичного применения Polys

Передача дополнительного аргумента в полиморфную функцию?

Выберите N-й элемент HList of Lists и верните это значение как HList значений

Динамически параметризовать функцию Poly1 в бесформенном

shapeless-dev: Как «параметризовать» полифункцию?

Функция складывания HList, для которой требуется HList

Параметризировать фильтрацию элемента в бесформенном списке списков

---

Смотрите также:

Берем HList из Seq[_] и генерируем Seq[HList] с декартовым произведением значений

Декартово произведение разнородных списков (Haskell)