如何确保(在编译时)该集合没有重新排序? [英] How to make sure (in compile-time) that collection wasn't reordered?

问题描述

假设我已经索引了集合(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))处理程序(解压缩.seq)

但我需要限制用户，只做map、filter、collect、contains、forall、scanLeft 等等.但不是 flatMap(除了 filter-like)、sort、++ 等等.所以任何双射/surjection，但不是注入式.在紧要关头，用户可以在没有 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 NonReorderedList[Tg <: NonReorderedListT#Tag, T] {类型标签 = Tgdef map[U](f: T => U): NonReorderedList[Tag, U]//相同的标签//... 其他允许的操作应该在这里}对象 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))//... 其他允许的操作应该在这里}def apply[T](l: List[T]) = {val tagC = new NonReorderedListT {}//容器new NonReorderedListImpl[tagC.Tag, T](l)}}

这是 Scala REPL 的结果:

定义的特征 NonReorderedListT定义的特征 NonReorderedList定义类 NonReorderedListImpl已定义对象 NonReorderedList标度>val l = NonReorderedList(List(1,2,3))警告:有一个功能警告；使用 -feature 重新运行以获取详细信息l: NonReorderedListImpl[tagC.Tag,Int] forSome { val tagC: NonReorderedListT } = NonReorderedListImpl@3620eab标度>val res: NonReorderedList[l.Tag, Int] = l.map(_ + 1)res: NonReorderedList[l.Tag,Int] = NonReorderedListImpl@34bddf43标度>val m = NonReorderedList(List(1,2,3))警告:有一个功能警告；使用 -feature 重新运行以获取详细信息m: NonReorderedListImpl[tagC.Tag,Int] forSome { val tagC: NonReorderedListT } = NonReorderedListImpl@2d8c729f标度>val res: NonReorderedList[l.Tag, Int] = m.map(_ + 1)<console>:31: 错误:类型不匹配；发现:NonReorderedListImpl[m.Tag,Int](扩展为) NonReorderedListImpl[tagC.Tag,Int]需要:NonReorderedList[l.Tag,Int](扩展为) 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")，它们是单独处理然后合并回来(应保留原始顺序).使用复杂谓词排序需要一些时间(因为它调用外部服务)，所以我不能只用它对集合重新排序两次 - 第二次重新排序应该基于简单索引.

附言我不是在寻找类型安全性较低的替代品，因为我的项目中已经有这样的替代品:).我的目标是改进现有(在我的项目中)代码.

解决方案

也许可以通过使用来自 shapeless 的 Nat 和 HList 来解决这个问题?这个想法是显式地对元素的索引进行建模.(我问了一个相关的问题使用 Shapeless 实现编译安全索引.)例如，

import shapeless._导入 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) :: HNilval keep= Entry("B", _2) :: Entry("E", _5) :: HNil

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

Let's say I have indexed collection (List or Map doesn't matter here):

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

It's hard to work with such (as every operation, like map, has to deal with index), so what I want to pass into business handler is:

case class Indexed[T](seq: Seq[T], i: Seq[Int])

val unzipped = Indexed(List("A", "C", "D"), List(1,3,8))

handler(unzipped.seq)

But I need user to be restricted, to do only map, filter, collect, contains, forall, scanLeft and so on. But not flatMap (except filter-like), sort, ++ and so forth. So any bijection/surjection, but not injection-like. In a pinch, user can live without filter/flatMap, so having Functor, but not Monad could be fine for me - anyway acceptable List[Option[T]] => List[T] from my original requirements isn't complete Monad (M[M[T]] => M[T], T => M[T]).

toList, toSet are acceptable, but I also want to be sure that returning (from business handler) collection is based on original one. I can do this by adding path-dependent Tag (path-dependent type) to the type signature of original collection and require same-tagged collection as a return type (which can be cheated only with asInstanceOf). My first requirements can be satisfied by implementing my own Traversable.

So my own "wheel" to solve this is just a wrapper (with only subset of operations permitted + tags for making sure that collection is same):

 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)
   }
 }

Here is the results from 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)
                                                    ^

However, it shouldn't be so rare situation when you need such collection, so maybe Scalaz already has some implementation, something like NonEmptylist, but NonReorderedList.

I'm doing all this because I have one already ordered collection (1 -> "A", 2 - "B", 3 -> "C", 4 -> "D", 5 -> "E") as an input, which splits into (1 -> "A", 3 -> "C", 4 -> "D") and (2 -> "B", 5 -> "E"), they're processed separately and then merged back (original order should be preserved). Ordering with complex predicate takes some time (as it calls to the external service), so I can't just reorder collection twice with it - second reordering should be based on simple index.

P.S. I'm not looking for less type-safe alternatives as I already have such in my project :). My goal is to improve existing (in my project) code.

解决方案

Maybe this could be approached by using Nat and HList from shapeless? The idea is to model an element's index explicitly. (I asked a related question Achieving compile safe indexing with Shapeless.) For example,

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

This would provide some type safety (although I'm not sure about the performance implications.)

这篇关于如何确保(在编译时)该集合没有重新排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！