通过分割和折叠重写序列 [英] Rewriting a sequence by partitioning and collapsing

问题描述

什么是最优雅和简单的算法来映射顺序集合，使得满足一些谓词的连续元素被折叠到另一个元素中，并且不满足谓词的那些元素被映射到另一个元素？

这里是一个例子：

 是这种类型
 sealed trait B //说输出元素是这种类型
 case类C（i：Int）extends A //这些是满足谓词的输入元素
 case类D（s：C *）扩展B //它们应该被折叠成这个
 case类E（i：Int）extends A with B //这些是留下的输入elems 
  
 
 
 
给定此输入序列：
  val input = Seq（C（1），C（2），C（3），E（4），E（5），C（6） 9））
  
预期输出为：
  val output = Seq（D（C（1），C（2），C（3）），E（4） ），E（7），D（C（8），C（9）））
 // ---------------  -   -   -   -  ----- --- 
 //破折号表示如何重新分组序列（折叠）
  
是这样做的一种方式，但我不确定这是特别优雅：
  def split（xs：Seq [A ]：Seq [B] = split1（Seq.empty [B]，true，xs）
 @ annotation.tailrec def split1（done：Seq [B]，test：Boolean， ：Seq [B] = {
 val（pre，post）= rem.span {case _：C =>测试; case _ => ！test} 
 val add = if（test）{
 D（pre.collect（{case x：C => x}）：_ *）:: Nil 
} else { 
 pre.collect（{case x：E => x}）
} 
 val done2 = done ++ add 
 if（post.isEmpty）done2 else split1 ，！test，post）
} 
  
验证：
  val output2 = split（input）
 output2 == output // ok 
  
 
 
解决方案
我会为D添加一个方便的方法，所以你可以添加另一个C，并得到一个新的D。那么很容易使用一个简单的foldLeft等来构建一个新的Seq。
 
what is the most elegant and simple algorithm to map a sequential collection such that contiguous elements that satisfy some predicate are collapsed into another element, and those that do not satisfy the predicate are mapped 1:1 into another element?

here is an example:
sealed trait A  // say the input elements are of this type
sealed trait B  // say the output elements are of this type
case class C(i: Int) extends A // these are the input elements satisfying the predicate
case class D(s: C*) extends B // they should be collapsed into this
case class E(i: Int) extends A with B // these are input elems that are left as such
given this input sequence:
val input  = Seq(C(1), C(2), C(3), E(4), E(5), C(6), E(7), C(8), C(9))
the expected output is:
val output = Seq(D(C(1), C(2), C(3)), E(4), E(5), D(C(6)), E(7), D(C(8), C(9)))
//                ---------------       -    -      -       -      --------
// the dashes indicate how the sequence is regrouped (collapsed)
here is one way of doing it, but i'm not sure this is particularly elegant:
def split(xs: Seq[A]): Seq[B] = split1(Seq.empty[B], true, xs)
@annotation.tailrec def split1(done: Seq[B], test: Boolean, rem: Seq[A]) : Seq[B] = {
    val (pre, post) = rem.span { case _: C => test; case _ => !test }
    val add = if(test) {
        D(pre.collect({ case x: C => x }): _*) :: Nil
    } else {
        pre.collect({ case x: E => x })
    }
    val done2 = done ++ add
    if(post.isEmpty) done2 else split1(done2, !test, post)
}
verify:
val output2 = split(input)
output2 == output  // ok

解决方案
I would add a convenience method to D so you can "add" another C and get a new D back. Then it would be easy to use a simple foldLeft or so to build a new Seq.

                        
这篇关于通过分割和折叠重写序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！