尾递归问题

Question

我们正在Scala中尝试并行收集,并想检查结果是否已订购.为此,我在REPL上编写了一个小函数来检查我们生成的非常大的List:

def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => x>y & isOrdered(tail) 
  }
}

它失败了stackOverflow(这里的问题是多么合适!).我期待它是尾部优化的.怎么了？

Answer 1

isOrdered不是代码中的最后一个调用,&运算符是.试试这个:

@scala.annotation.tailrec def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => if (x>y) isOrdered(tail) else false
  }
}

Answer 2

您的算法不正确.即使有了@Kim的改进,isOrdered(List(4,3,5,4))也要回归true.

试试这个:

def isOrdered(l:List[Int]): Boolean = l match {
  case Nil => true
  case x :: Nil => true
  case x :: y :: t => if (x <= y) isOrdered(l.tail) else false
}

(也更新,以便标志正确)

编辑:我的perferred布局是这样的:

def isOrdered(list: List[Int]): Boolean = list match {
  case Nil      => true
  case x :: Nil => true
  case x :: xs  => if (x > xs.head) false
                   else isOrdered(xs)
}

如果性能不是问题的快速方法

def isOrdered(l: List[Int]) = l == l.sorted