在 Scala 中将循环的命令式重写为声明式样式

Question

如何使用内置的高阶函数或尾递归将以下循环（模式）重写到 Scala 中？

这是迭代模式的示例，您可以在其中对两个列表元素进行计算（例如比较），但前提是原始输入中第二个元素出现在第一个元素之后。注意这里用的是+1步骤，一般情况下可以是+n.

public List<U> mapNext(List<T> list) {
    List<U> results = new ArrayList();

    for (i = 0; i < list.size - 1; i++) {
        for (j = i + 1; j < list.size; j++) {
            results.add(doSomething(list[i], list[j]))
        }
    }

    return results;
}

到目前为止，我在 Scala 中想到了这个：

def mapNext[T, U](list: List[T])(f: (T, T) => U): List[U] = {
  @scala.annotation.tailrec
  def loop(ix: List[T], jx: List[T], res: List[U]): List[U] = (ix, jx) match {
    case (_ :: _ :: is, Nil) => loop(ix, ix.tail, res)
    case (i :: _ :: is, j :: Nil) => loop(ix.tail, Nil, f(i, j) :: res)
    case (i :: _ :: is, j :: js) => loop(ix, js, f(i, j) :: res)
    case _ => res
  }

  loop(list, Nil, Nil).reverse
}

编辑：对于所有贡献者，我只希望我能接受每个答案作为解决方案:)

Answer 1

list       // [a, b, c, d, ...]
  .indices // [0, 1, 2, 3, ...]
  .flatMap { i =>
    elem = list(i) // Don't redo access every iteration of the below map.
    list.drop(i + 1) // Take only the inputs that come after the one we're working on
      .map(doSomething(elem, _))
  }
// Or with a monad-comprehension
for {
  index <- list.indices
  thisElem = list(index)
  thatElem <- list.drop(index + 1)
} yield doSomething(thisElem, thatElem)

您不是从列表开始，而是从它的 indices 开始。然后，您使用 flatMap，因为每个索引都指向一个元素列表。使用 drop 仅获取我们正在处理的元素之后的元素，并将该列表映射到实际运行计算。请注意，这具有可怕的时间复杂度，因为此处的大多数操作 indices/length、flatMap、map 的列表大小为 O(n)，并且 drop 和 apply 是参数中的 O(n)。

如果您 a) 停止使用链表（List 适用于后进先出、顺序访问，但 Vector 在一般情况下更好），并且 b)让这个更丑一点

val len = vector.length
(0 until len)
  .flatMap { thisIdx =>
    val thisElem = vector(thisIdx)
    ((thisIdx + 1) until len)
      .map { thatIdx =>
        doSomething(thisElem, vector(thatIdx))
      }
  }
// Or
val len = vector.length
for {
  thisIdx <- 0 until len
  thisElem = vector(thisIdx)
  thatIdx <- (thisIdx + 1) until len
  thatElem = vector(thatIdx)
} yield doSomething(thisElem, thatElem)

如果您真的需要，您可以通过使用一些 implicit CanBuildFrom 参数将此代码的任一版本推广到所有 IndexedSeqs，但我不会介绍它.

Answer 2

复出尝试：

在删除了我第一次给出答案的尝试后，我对它进行了更多思考并提出了另一个至少更短的解决方案。

def mapNext[T, U](list: List[T])(f: (T, T) => U): List[U] = {
  @tailrec
  def loop(in: List[T], out: List[U]): List[U] = in match {
    case Nil          => out
    case head :: tail => loop(tail, out ::: tail.map { f(head, _) } )
  }

  loop(list, Nil)
}

我还想推荐 enrich my library 模式，用于将 mapNext 函数添加到列表 api（或对任何其他集合进行一些调整）。

object collection {
  object Implicits {
    implicit class RichList[A](private val underlying: List[A]) extends AnyVal {
      def mapNext[U](f: (A, A) => U): List[U] = {
        @tailrec
        def loop(in: List[A], out: List[U]): List[U] = in match {
          case Nil          => out
          case head :: tail => loop(tail, out ::: tail.map { f(head, _) } )
        }

        loop(underlying, Nil)
      }
    }
  }
}

然后你可以使用如下函数：

list.mapNext(doSomething)

同样，也有一个缺点，因为连接列表的成本相对较高。然而，理解中的变量赋值也可能非常低效（正如这个针对 dotty Scala Wart: Convoluted de-sugaring of for-comprehensions 的改进任务所暗示的那样）。

更新

既然入了这个圈子，就放不下了:(

关于'Note that the +1 step is used here, but in general, it could be +n.'

我用一些参数扩展了我的提案以涵盖更多情况：

object collection {
  object Implicits {
    implicit class RichList[A](private val underlying: List[A]) extends AnyVal {
      def mapNext[U](f: (A, A) => U): List[U] = {
        @tailrec
        def loop(in: List[A], out: List[U]): List[U] = in match {
          case Nil          => out
          case head :: tail => loop(tail, out ::: tail.map { f(head, _) } )
        }

        loop(underlying, Nil)
      }

      def mapEvery[U](step: Int)(f: A => U) = {
        @tailrec
        def loop(in: List[A], out: List[U]): List[U] = {
          in match {
            case Nil => out.reverse
            case head :: tail => loop(tail.drop(step), f(head) :: out)
          }
        }

        loop(underlying, Nil)
      }
      def mapDrop[U](drop1: Int, drop2: Int, step: Int)(f: (A, A) => U): List[U] = {
        @tailrec
        def loop(in: List[A], out: List[U]): List[U] = in match {
          case Nil          => out
          case head :: tail =>
            loop(tail.drop(drop1), out ::: tail.drop(drop2).mapEvery(step) { f(head, _) } )
        }

        loop(underlying, Nil)
      }
    }
  }
}

Answer 3

这是我的刺。我认为它非常可读。直觉是：对于列表的每个头部，将函数应用于头部和尾部的每个其他成员。然后在列表的尾部递归。

def mapNext[U, T](list: List[U], fun: (U, U) => T): List[T] = list match {
  case Nil => Nil
  case (first :: Nil) => Nil
  case (first :: rest) => rest.map(fun(first, _: U)) ++ mapNext(rest, fun)
}

这是一个示例运行

scala> mapNext(List(1, 2, 3, 4), (x: Int, y: Int) => x + y)
res6: List[Int] = List(3, 4, 5, 5, 6, 7)

这个不是明确的尾递归，但可以很容易地添加一个累加器来实现它。

Answer 4

递归当然是一个选项，但标准库提供了一些可以实现相同迭代模式的替代方案。

这是一个非常简单的演示设置。

val lst = List("a","b","c","d")
def doSomething(a:String, b:String) = a+b

这是实现我们所追求目标的一种方法。

val resA = lst.tails.toList.init.flatMap(tl=>tl.tail.map(doSomething(tl.head,_)))
// resA: List[String] = List(ab, ac, ad, bc, bd, cd)

这行得通，但是 flatMap() 中有一个 map() 的事实表明 for 理解可以用来美化它。

val resB = for {
  tl <- lst.tails
  if tl.nonEmpty
  h = tl.head
  x <- tl.tail
} yield doSomething(h, x)  // resB: Iterator[String] = non-empty iterator

resB.toList  // List(ab, ac, ad, bc, bd, cd)

在这两种情况下，toList 转换都用于让我们返回到原始集合类型，这实际上可能不是必需的，具体取决于需要对集合进行哪些进一步处理。

在 Scala 中将循环的命令式重写为声明式样式

Rewriting imperative for loop to declarative style in Scala

scala

loops

functional-programming

tail-recursion

declarative