下面是来自 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 版本有什么想法吗?
最佳答案
在这种情况下(将递归调用转换为尾调用可能很复杂),您可以使用 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的实现在这里,因为 the standard library's目前缺少一些部分(尽管 will change soon )。
现在你可以写例如以下内容:
mergeAndCount((1 to 20000).toStream, (2 to 20001).toStream).run
如果我们不限制尾部调用,这几乎肯定会破坏堆栈。
关于algorithm - 将 Haskell 反转计数器移植到 Scala,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18980612/