如何确保(在编译时)集合未重新排序？

Question

假设我有一个索引集合(List或Map在这里不重要):

val zipped = List(1 -> "A", 3 -> "C", 8 -> "D")

很难处理这样的操作(因为每个操作，如map，必须处理index)，所以我想传递给业务处理程序的是:

case class Indexed[T](seq: Seq[T], i: Seq[Int])
val unzipped = Indexed(List("A", "C", "D"), List(1,3,8))
handler(unzipped.seq)

但是我需要用户被限制，只做map, filter, collect, contains, forall, scanLeft等。但不是flatMap(除了filter类)，sort, ++等等。所以任何双射/射，但不是类注射。在必要时，用户可以没有filter/flatMap，所以有Functor，但没有Monad对我来说可能很好-无论如何，从我最初的需求中可以接受的List[Option[T]] => List[T]不是完整的Monad (M[M[T]] => M[T], T => M[T])。

toList, toSet是可以接受的，但我也想确保(从业务处理程序)返回的集合是基于原始集合的。我可以通过将路径依赖的Tag(路径依赖类型)添加到原始集合的类型签名中来实现这一点，并要求相同标记的集合作为返回类型(只能使用asInstanceOf欺骗)。我的第一个要求可以通过实现我自己的Traversable来满足。

所以我自己的"轮子"来解决这个问题只是一个包装器(只允许操作的子集+标签，以确保集合是相同的):

 trait NonReorderedListT {
     trait Tag
 }
 trait NonReorderedList[Tg <: NonReorderedListT#Tag, T] {
   type Tag = Tg 
   def map[U](f: T => U): NonReorderedList[Tag, U] //same tag
   //... other permitted operations should be here        
 }

 object NonReorderedList {
   class NonReorderedListImpl[Tg <: NonReorderedListT#Tag, T] private[NonReorderedList] (l: List[T]) extends NonReorderedList[Tg, T] { 
      def map[U](f: T => U) = new NonReorderedListImpl[Tag, U](l.map(f))
      //... other permitted operations should be here  
   }     

   def apply[T](l: List[T]) = {
     val tagC = new NonReorderedListT {} //container
     new NonReorderedListImpl[tagC.Tag, T](l)
   }
 }

下面是Scala REPL的结果:

defined trait NonReorderedListT
defined trait NonReorderedList
defined class NonReorderedListImpl
defined object NonReorderedList
scala>  val l = NonReorderedList(List(1,2,3))
warning: there was one feature warning; re-run with -feature for details
l: NonReorderedListImpl[tagC.Tag,Int] forSome { val tagC: NonReorderedListT } = NonReorderedListImpl@3620eab
scala> val res: NonReorderedList[l.Tag, Int] = l.map(_ + 1)
res: NonReorderedList[l.Tag,Int] = NonReorderedListImpl@34bddf43
scala>  val m = NonReorderedList(List(1,2,3))
warning: there was one feature warning; re-run with -feature for details
m: NonReorderedListImpl[tagC.Tag,Int] forSome { val tagC: NonReorderedListT } = NonReorderedListImpl@2d8c729f
scala> val res: NonReorderedList[l.Tag, Int] = m.map(_ + 1)
<console>:31: error: type mismatch;
 found   : NonReorderedListImpl[m.Tag,Int]
    (which expands to)  NonReorderedListImpl[tagC.Tag,Int]
 required: NonReorderedList[l.Tag,Int]
    (which expands to)  NonReorderedList[tagC.Tag,Int]
       val res: NonReorderedList[l.Tag, Int] = m.map(_ + 1)
                                                    ^

然而，它不应该是如此罕见的情况下，当你需要这样的收集，所以也许Scalaz已经有一些实现，像NonEmptylist，但NonReorderedList。

我这样做是因为我有一个已经排序的集合(1 ->"A"，2 -"B"，3 ->"C"，4 ->"D"，5 ->"E")作为输入，它分成(1 ->"A"，3 ->"C"，4 ->"D")和(2 ->"B"，5 ->"E")，它们分别处理，然后合并回来(原始顺序应该保留)。使用复杂谓词排序需要一些时间(因为它调用外部服务)，所以我不能用它对集合重新排序两次——第二次重新排序应该基于简单索引。

注:我不是在寻找更少的类型安全的替代品，因为我已经在我的项目中有了:)。我的目标是改进现有的(在我的项目中)代码。

Answer 1

也许这可以通过使用Nat和HList从shapeless接近?其思想是显式地为元素的索引建模。(我问了一个相关的问题，用Shapeless实现编译安全索引。)例如

import shapeless._
import Nat._
case class Entry[+N<:Nat](value: String, index: N)
val send: Entry[ _1] :: Entry[ _3] :: Entry[ _4] :: HNil= Entry("A", _1):: Entry("C", _3) :: Entry("D", _4) :: HNil
val keep= Entry("B", _2) :: Entry("E", _5)  :: HNil

这将提供一些类型安全(尽管我不确定对性能的影响)