Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save AndreasKostler/00a71363a1607f103c4f1826c4e5a3a1 to your computer and use it in GitHub Desktop.
Save AndreasKostler/00a71363a1607f103c4f1826c4e5a3a1 to your computer and use it in GitHub Desktop.
object Def {
import shapeless.{ =:!=, HNil, HList, Nat, Poly1, Succ, Witness }
import shapeless.nat.{ _0 => D0, _1 => D1, _2 => D2, _3 => D3 }
import shapeless.ops.nat.{ Diff, GT, LTEq, ToInt }
import shapeless.ops.hlist.{ Mapper, ToTraversable, ZipConst }
trait Value {
def toShortString = ???
}
object Value {
// TODO: Is defining implicit conversions like this good or bad form?
// KOSTLEAN: I personally don't see an issue here. Implicit conversions were all the
// hype not long ago, now they're frowned upon. I guess the question is: What are the alternatives?
// I think having a bunch of implicit conversions in a class' companion object is fine. Others might disagree.
implicit def stringToValue(value: String): Value = StringValue(value)
implicit def doubleToValue(value: Double): Value = DoubleValue(value)
implicit def longToValue(value: Long): Value = LongValue(value)
implicit def intToValue(value: Int): Value = LongValue(value)
val Ordering: Ordering[Value] = new Ordering[Value] {
def compare(x: Value, y: Value): Int = ???
}
}
case class StringValue(value: String) extends Value
case class DoubleValue(value: Double) extends Value
case class LongValue(value: Long) extends Value
trait Content
trait Result[A, T[X] <: Result[X, T]] {
def map[B](f: (A) => B): T[B]
def flatMap[B](f: (A) => Option[B]): T[B]
def toTraversableOnce: TraversableOnce[A]
}
case class Single[A](result: Option[A]) extends Result[A, Single] {
def map[B](f: (A) => B): Single[B] = Single(result.map(f(_)))
def flatMap[B](f: (A) => Option[B]): Single[B] = Single(result.flatMap(f(_)))
def toTraversableOnce: TraversableOnce[A] = result
}
object Single {
def apply[A](): Single[A] = Single[A](None)
def apply[A](result: A): Single[A] = Single[A](Some(result))
}
case class Multiple[A](result: TraversableOnce[A]) extends Result[A, Multiple] {
def map[B](f: (A) => B): Multiple[B] = Multiple(result.map(f(_)))
def flatMap[B](f: (A) => Option[B]): Multiple[B] = Multiple(result.flatMap(f(_)))
def toTraversableOnce: TraversableOnce[A] = result
}
// TODO: Is it worthwhile to create an `ExpandablePosition` or is what's here the "best"
// representation of a position?
// KOSTLEAN: You might want to restrict expanding beyond a certain dimension??
sealed trait Position[P <: Nat] {
val coordinates: List[Value]
// TODO: Is the type parameter needed, or can it be done using `def apply(dim: Nat)(implicit ...`? It looks like
// most of the pain will be in `Slice`.
// KOSTLEAN: You can but then you need to thread the evidence for ToInt and LTEq through Slice and Over. I got it to
// work but it's ugly. Not worth the effort.
def apply[D <: Nat : ToInt](dim: D)(implicit ev: LTEq[D, P]): Value = coordinates(toIndex(dim))
def update[D <: Nat : ToInt](dim: D, value: Value)(implicit ev: LTEq[D, P]): Position[P] = {
PositionImpl(coordinates.updated(toIndex(dim), value))
}
def prepend(value: Value): Position[Succ[P]] = PositionImpl(value +: coordinates)
def insert[D <: Nat : ToInt](dim: D, value: Value)(implicit ev: LTEq[D, P]): Position[Succ[P]] = {
val (h, t) = coordinates.splitAt(toIndex(dim))
PositionImpl(h ++ (value +: t))
}
def append(value: Value): Position[Succ[P]] = PositionImpl(coordinates :+ value)
def toShortString(separator: String): String = coordinates.map(_.toShortString).mkString(separator)
override def toString = "Position(" + coordinates.map(_.toString).mkString(",") + ")"
def toOption(): Option[Position[P]] = Option(this)
def compare(that: Position[_]): Int = {
if (coordinates.length == that.coordinates.length) {
coordinates
.zip(that.coordinates)
.map { case (m, t) => Value.Ordering.compare(m, t) }
.maxBy(math.abs(_))
} else
coordinates.length.compare(that.coordinates.length)
}
def toIndex[D <: Nat : ToInt](dim: D)(implicit ev: LTEq[D, P]): Int = {
val index = Nat.toInt[D]
if (index == 0) coordinates.length - 1 else index - 1
}
}
object Position {
implicit def pos1ToCom(pos: Position[D1]): CompactablePosition[D1] = pos
implicit def posToCom[P <: Nat](pos: Position[P])(implicit ev: GT[P, D1]): CompactablePosition[P] = pos
implicit def posToPer[P <: Nat](pos: Position[P])(implicit ev: GT[P, D1]): PermutablePosition[P] = pos
/* TODO: is this needed?
KOSTLEAN: Of course not ;)
trait Foo[N <: Nat]
implicit def foo[N <: Nat](f: Foo[N])(implicit diff: Diff[N, D1]) = 0
*/
implicit def posToRed[
P <: Nat,
L <: Nat
](
pos: Position[P]
)(implicit
ev1: Diff.Aux[P, D1, L]
): ReduciblePosition[L, P] = ReduciblePositionImpl[L, P](pos.coordinates)
def apply(first: Value): Position[D1] = PositionImpl[D1](List(first))
def apply(first: Value, second: Value): Position[D2] = PositionImpl[D2](List(first, second))
def apply(first: Value, second: Value, third: Value): Position[D3] = PositionImpl[D3](List(first, second, third))
def toString[
P <: Nat
](
descriptive: Boolean = false,
separator: String = "|"
): (Position[P]) => TraversableOnce[String] = (t: Position[P]) => {
List(if (descriptive) t.toString else t.toShortString(separator))
}
}
// TODO: Compactable, Permutable and Reducible are all traits with private case class implementations. A user
// gets access through implicit conversions. Is that a "good" pattern, or are there more idiomatic ways?\
// KOSTLEAN: Not quite sure I understand.
trait CompactablePosition[P <: Nat] extends Position[P] {
type C[_]
def toMapValue[R <: Nat](rem: Position[R], con: Content): C[Position[R]]
}
private object ToIndex extends Poly1 {
implicit def defaultCase[N <: Nat : ToInt, P[X <: Nat] <: Position[X], M <: Nat](implicit ev: LTEq[N, M]) = {
at[(N, P[M])] { case (n, pos) => pos.coordinates(pos.toIndex(n)) }
}
}
trait PermutablePosition[P <: Nat] extends Position[P] {
/* TODO: is this needed?
KOSTLEAN: No- see above ToIndex
object ToIndexPoly extends Poly1 {
implicit def default[N <: Nat : ToInt](implicit ev: LTEq[N, P]) = at[N] ((n: N) => coordinates(toIndex(n)))
}
*/
def permute[
H <: HList,
ZL <: HList,
ML <: HList
](
l: H
)(implicit
constZipper: ZipConst.Aux[PermutablePosition[P], H, ZL],
mapper: Mapper.Aux[ToIndex.type, ZL, ML],
toTraversableAux: ToTraversable.Aux[ML, List, Value]
): Position[P] = {
val zipped = l zipConst this
PositionImpl((zipped map ToIndex).toList[Value])
}
}
trait ReduciblePosition[L <: Nat, P <: Nat] extends Position[P] {
def remove[D <: Nat : ToInt](dim: D)(implicit ev: LTEq[D, P]): Position[L] = {
val (h, t) = coordinates.splitAt(toIndex(dim))
PositionImpl(h ++ t.tail)
}
def melt[
D <: Nat : ToInt,
E <: Nat : ToInt,
// KOSTLEAN: Should this be a context bound??
V <% Value
](
dim: D,
into: E,
merge: (Value, Value) => V
)(implicit
ev1: D =:!= E,
ev2: LTEq[D, P],
ev3: LTEq[E, P]
): Position[L] = {
val iidx = toIndex(into)
val didx = toIndex(dim)
val value: Value = merge(coordinates(iidx), coordinates(didx))
PositionImpl(coordinates.updated(iidx, value).zipWithIndex.collect { case (c, i) if (i != didx) => c })
}
}
// KOSTLEAN: Are those needed??
private case class CompactableD1(coordinates: List[Value]) extends CompactablePosition[D1] {
type C[R] = Content
def toMapValue[R <: Nat](rem: Position[R], con: Content): C[Position[R]] = con
}
private case class CompactableDX[P <: Nat](coordinates: List[Value]) extends CompactablePosition[P] {
type C[R] = Map[R, Content]
def toMapValue[R <: Nat](rem: Position[R], con: Content): C[Position[R]] = Map(rem -> con)
}
private case class PositionImpl[P <: Nat](coordinates: List[Value]) extends Position[P]
private case class ReduciblePositionImpl[
L <: Nat,
P <: Nat
](
coordinates: List[Value]
) extends ReduciblePosition[L, P]
sealed trait Slice[L <: Nat, P <: Nat, D <: Nat] {
type S <: Nat
type R <: Nat
val dimension: D
def selected(pos: ReduciblePosition[L, P]): Position[S]
def remainder(pos: ReduciblePosition[L, P]): Position[R]
protected def remove(pos: ReduciblePosition[L, P])(implicit ev1: ToInt[D], ev2: LTEq[D, P]): Position[L] = {
pos.remove(dimension)
}
protected def single(pos: Position[P])(implicit ev1: ToInt[D], ev2: LTEq[D, P]): Position[D1] = {
Position(pos(dimension))
}
}
sealed trait Over[
L <: Nat,
P <: Nat,
D <: Nat
] extends Slice[L, P, D] {
type S = D1
type R = L
}
object Over {
def apply[
L <: Nat,
P <: Nat
](
d: Nat
)(implicit
ev1: Diff.Aux[P, L, D1],
ev2: LTEq[d.N, P],
ev3: Witness.Aux[d.N],
ev4: ToInt[d.N]
): Over[L, P, d.N] = OverImpl[L, P, d.N](ev3.value)
}
private case class OverImpl[
L <: Nat,
P <: Nat,
D <: Nat : ToInt
](
dimension: D
)(implicit
ev1: Diff.Aux[P, L, D1],
ev2: LTEq[D, P]
) extends Over[L, P, D] {
def selected(pos: ReduciblePosition[L, P]): Position[S] = single(pos)
def remainder(pos: ReduciblePosition[L, P]): Position[R] = remove(pos)
}
trait Aggregator {
type Q[S <: Nat] <: Nat
type O[A] <: Result[A, O]
def present[S <: Nat](pos: Position[S]): O[Position[Q[S]]]
}
trait Legal[A <: Aggregator, S <: Nat] extends Serializable { }
object Aggregator {
type Aux[A <: Aggregator, S <: Nat] = Legal[A, S]
implicit def sWithSingle[
A <: Aggregator,
S <: Nat
](implicit
ev: A <:< Aggregator { type Q[N <: Nat] = N; type O[B] = Single[B] }
): Aux[A, S] = new Legal[A, S] { }
implicit def notS[A <: Aggregator, S <: Nat](implicit ev: A#Q[S] =:!= S): Aux[A, S] = new Legal[A, S] { }
}
case class AsIsS() extends Aggregator {
type Q[S <: Nat] = S
type O[A] = Single[A]
def present[S <: Nat](pos: Position[S]): O[Position[Q[S]]] = Single(pos)
}
case class AsIsM() extends Aggregator {
type Q[S <: Nat] = S
type O[A] = Multiple[A]
def present[S <: Nat](pos: Position[S]): O[Position[Q[S]]] = Multiple(List(pos))
}
case class AppendTwo() extends Aggregator {
type Q[S <: Nat] = Succ[Succ[S]]
type O[A] = Multiple[A]
def present[S <: Nat](pos: Position[S]): O[Position[Q[S]]] = Multiple(List(pos.append("bar").append(42)))
}
def summarise[
L <: Nat,
P <: Nat,
D <: Nat,
A <: Aggregator
](
slice: Slice[L, P, D],
pos: Position[P],
aggregator: A
)(implicit
ev1: Diff.Aux[P, D1, L],
ev2: Aggregator.Aux[A, slice.S]
): TraversableOnce[Position[aggregator.Q[slice.S]]] = aggregator.present(slice.selected(pos)).toTraversableOnce
// TODO: The current Matrix.permute API looks similar to this. How can we make that work? The simplest way is
// to make Position.permute take a list of Int (representing the new ordering of the coordinates). And
// then define Matrix.permute something like:
//
// def permute[D <: Nat : ToInt, E <: Nat : ToInt](first: D, second: E) = {
// data.map(_.permute(List(Nat.toInt[D], Nat.toInt[E]))) // Assuming data: TypedPipe[Position[D2]]
// }
//
// The downside, obviously, is that Position.permute looses all type safety.
//def permute[D <: Nat, E <: Nat](pos: Position[D2], first: D, second: E): Position[D2] = pos.permute(D :: E :: HNil)
// ==================================
val p1: Position[D1] = Position("foo")
val p2: Position[D2] = p1.append("bar")
val p3: Position[D1] = p2.remove(D1)
val p4: Position[D0] = p3.remove(D1)
//p4.remove(D1) // Correctly does not compile.
val o1 = Over[D0, D1](D1)
//val o2 = Over[D0, D1](D2) // Correctly does not compile.
val o3 = Over[D1, D2](D1)
val o4 = Over[D1, D2](D2)
//val o5 = Over[D0, D2](D1) // Correctly does not compile
val px = Position("foo", 3.14)
val py = o3.selected(px)
val p = Position("foo")
val q = summarise(Over(D1), p, AsIsS()).map(_.remove(D1))
val r = summarise(Over(D1), p, AppendTwo()).map(_.remove(D1))
//val s = summarise(Over(D1), p, AsIsM()).map(_.remove(D1)) // Correctly does not compile
Position("foo", 3.14).permute(D2 :: D1 :: HNil)
//Position("foo").permute(D1 :: HNil) // Correctly does not compile
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment