2

这是来自 Haskell 实现的相关代码，该例程计算列表中的反转

mergeAndCount :: Ord a => [a] -> [a] -> (Int,[a])
mergeAndCount l@(x:xs) r@(y:ys) | x < y = let (inv, s) = mergeAndCount xs r in (inv, x:s)
                                | otherwise = let (inv, s) = mergeAndCount l ys in (inv + rest, y:s)
                                                where rest = length l
mergeAndCount l [] = (0, l)
mergeAndCount [] r = (0, r)

我曾尝试在 Scala 中编写类似的例程，但它会因堆栈溢出而崩溃（不过，惰性排序有效）。这是非工作版本：

  def mergeAndCount(l: Stream[Int], r: Stream[Int]) : (Long, Stream[Int]) = {
    (l, r) match {
      case (x#::xs, Empty) => (0, l)
      case (Empty, y#::ys) => (0, r)
      case (x#::xs, y#::ys) => if(x < y) {
        lazy val (i, s) = mergeAndCount(xs, r)
        (i, x#::s)
      } else {
        lazy val (i, s) = mergeAndCount(l, ys)
        (i + l.length, y#::s)
      }
    }
  }

关于如何使 Scala 版本表现得像 Haskell 的任何想法？

4

2 回答 2

3

在这种情况下（将递归调用转换为尾调用可能很复杂），您可以使用trampolines将堆换成堆栈：

import Stream.Empty
import scalaz.std.tuple._
import scalaz.syntax.bifunctor._
import scalaz.Free.Trampoline, scalaz.Trampoline._

def mergeAndCount(
  l: Stream[Int],
  r: Stream[Int]
): Trampoline[(Long, Stream[Int])] = (l, r) match {
  case (_ #:: _, Empty) => done((0, l))
  case (Empty, _ #:: _) => done((0, r))
  case (x #:: xs, y #:: _) if x < y => suspend(
    mergeAndCount(xs, r).map(_.rightMap(x #:: _))
  )
  case (_, y #:: ys) => suspend(
    mergeAndCount(l, ys).map(_.bimap(_ + l.length, y #:: _))
  )
}

请注意，我在这里使用Scalaz的实现，因为标准库目前缺少一些部分（尽管很快就会改变）。

现在您可以编写例如以下内容：

mergeAndCount((1 to 20000).toStream, (2 to 20001).toStream).run

如果我们不蹦蹦跳跳尾跟注，这几乎肯定会破坏堆栈。

于 2013-09-24T12:34:27.700 回答
1

我会将此作为评论留下，但不幸的是我还没有这样做的声誉......

无论如何，如果您在函数的最后一次调用之前进行递归，您可能会遇到堆栈溢出错误 - 在 Scala 中，只有尾递归被优化为不使用堆栈。如果您可以将递归调用移动到每个案例的最后一行（这意味着放弃懒惰），那么您可能会得到更好的结果。

于 2013-09-24T12:32:55.110 回答