14

在我的一个项目中，一个常见的用例不断出现。在某些时候，我有某种排序的集合（List、Seq 等...无关紧要）和这个集合的一个元素。我想要做的是将给定元素与其后一个元素（如果该元素存在）或有时与前一个元素交换。

我很清楚使用过程编程技术实现这一目标的方法。我的问题是通过函数式编程（在 Scala 中）解决问题的好方法是什么？

谢谢大家的答案。我接受了我自己最了解的那个。由于我（还）不是函数式程序员，所以我很难决定哪个答案是真正最好的。在我看来，它们都非常好。

4

5 回答 5

10

以下是与列表中的下一个元素进行交换的功能版本，您只需构建一个交换元素的新列表。

def swapWithNext[T](l: List[T], e : T) : List[T] = l match {
  case Nil => Nil
  case `e`::next::tl => next::e::tl
  case hd::tl => hd::swapWithNext(tl, e)
}
于 2010-07-26T14:22:55.500 回答
8

zipper是一种纯函数式数据结构，带有指向该结构的指针。换句话说，它是在某种结构中具有上下文的元素。

例如，Scalaz库提供了一个Zipper类，该类使用列表中的特定元素对列表进行建模。

您可以获得列表的拉链，专注于第一个元素。

import scalaz._
import Scalaz._

val z: Option[Zipper[Int]] = List(1,2,3,4).toZipper

您可以使用 on 方法移动拉链的焦点Zipper，例如，您可以从当前焦点移动到下一个偏移量。

val z2: Option[Zipper[Int]] = z >>= (_.next)

这就像List.tail它记得它曾经在哪里。

然后，一旦您选择的元素成为焦点，您就可以修改焦点周围的元素。

val swappedWithNext: Option[Zipper[Int]] =
  for (x <- z2;
       y <- x.delete)
    yield y.insertLeft(x.focus)

注意：这是最新的 Scalaz 主干头，其中 Zipper 的尾递归find和move方法的错误已得到修复。

你想要的方法就是：

def swapWithNext[T](l: List[T], p: T => Boolean) : List[T] = (for {
  z <- l.toZipper
  y <- z.findZ(p)
  x <- y.delete
} yield x.insertLeft(y.focus).toStream.toList) getOrElse l

这匹配基于谓词的元素p。但是您可以更进一步，也可以考虑所有附近的元素。例如，实现插入排序。

于 2010-07-27T12:12:22.800 回答
5

Landei 的通用版本：

import scala.collection.generic.CanBuildFrom
import scala.collection.SeqLike
def swapWithNext[A,CC](cc: CC, e: A)(implicit w1: CC => SeqLike[A,CC],
                                        w2: CanBuildFrom[CC,A,CC]): CC = {
    val seq: SeqLike[A,CC] = cc
    val (h,t) = seq.span(_ != e)
    val (m,l) = (t.head,t.tail)
    if(l.isEmpty) cc
    else (h :+ l.head :+ m) ++ l.tail
}

一些用法：

scala> swapWithNext(List(1,2,3,4),3)
res0: List[Int] = List(1, 2, 4, 3)

scala> swapWithNext("abcdef",'d')
res2: java.lang.String = abcedf

scala> swapWithNext(Array(1,2,3,4,5),2)
res3: Array[Int] = Array(1, 3, 2, 4, 5)

scala> swapWithNext(Seq(1,2,3,4),3)
res4: Seq[Int] = List(1, 2, 4, 3)

scala>
于 2010-07-26T15:37:48.963 回答
1

venechka 方法的另一种实现：

def swapWithNext[T](l: List[T], e: T): List[T] = {
  val (h,t) = l.span(_ != e)
  h ::: t.tail.head :: e :: t.tail.tail
}

请注意，如果 e 是最后一个元素，则此操作将失败并出现错误。

如果你知道这两个元素，并且每个元素只出现一次，它会变得更加优雅：

def swap[T](l: List[T], a:T, b:T) : List[T] = l.map(_ match {
  case `a` => b
  case `b` => a
  case e => e }
)
于 2010-07-26T14:55:40.083 回答
0

怎么样 ：

  val identifierPosition = 3;
  val l = "this is a identifierhere here";
  val sl = l.split(" ").toList;

  val elementAtPos = sl(identifierPosition)
  val swapped = elementAtPos :: dropIndex(sl , identifierPosition)

  println(swapped)

  def dropIndex[T](xs: List[T], n: Int) : List[T] = {
    val (l1, l2) = xs splitAt n
    l1 ::: (l2 drop 1)
  }

感谢http://www.scala-lang.org/old/node/5286的dropIndex函数

于 2015-08-10T22:20:22.487 回答