时间戳

首页 > 解决方案 > 检查 Array[T] 是否在没有本地 tailrec 的情况下排序？

scala - 检查 Array[T] 是否在没有本地 tailrec 的情况下排序？

问题描述

实现 isSorted，它检查 Array[A] 是否根据给定的比较函数排序：

def isSorted[A](as: Array[A], 有序: (A,A) => Boolean): Boolean

这是我的实现

@tailrec
def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean = {
  if(as.length==0 || as.length == 1 || as.isEmpty) true
  else if(!ordered(as(0),as(1))) false
  isSorted(as.tail,ordered)
}

我得到了这个例外：
java.lang.UnsupportedOperationException: empty.tail

我不太明白，它应该在as为空时返回true。

标签： scala

解决方案

在 Scala 中，在方法或块内计算的最后一个表达式成为该方法或块的值。

在您的情况下，在方法内部评估的最后一个表达式是：

isSorted(as.tail,ordered)

所以，这就是返回值。总是。

在此表达式之前，您的方法中还有另一个表达式：

if(as.length==0 || as.length == 1 || as.isEmpty) true
else if(!ordered(as(0),as(1))) false

但：

  • 这个表达式没有副作用
  • 此表达式的值未存储在任何地方
  • 不返回此表达式的值

因此，这个表达式本质上是一个空操作，而你的方法实际上就是这样的：

@tailrec
def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean = 
  isSorted(as.tail,ordered)

您的方法将简单地递归直到数组为空，然后抛出异常，因为您正尝试使用空数组的尾部再次递归。

最简单的解决方法是将最后一个表达式作为较大表达式的一部分，以便您的方法仅包含一个表达式：

@tailrec
def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean = {
  if(as.length==0 || as.length == 1 || as.isEmpty) true
  else if(!ordered(as(0),as(1))) false
  else isSorted(as.tail,ordered)
//↑↑↑↑ This is the only change needed.
}

现在，让我们进行一次小旅行：Scala 风格！

您的空格样式不一致。有时，运算符周围有空格，有时没有，不清楚何时选择一个或另一个，以及它的含义是什么。例如，这里：

if(as.length==0 || as.length == 1 || as.isEmpty) true
//          ↑↑ ↑↑↑↑         ↑↑↑↑ ↑↑↑↑

您使用什么标准来决定何时使用空格？你使用空格||和第二个==而不是第一个是什么意思？你想告诉我，你的代码的读者，这个决定有什么重要的信息？

就个人而言，我会这样写：

if(as.length == 0 || as.length == 1 || as.isEmpty) true
//          ↑↑↑↑ ↑↑↑↑         ↑↑↑↑ ↑↑↑↑

这也符合标准的 Scala 社区风格指南。

同样，您在参数列表中的逗号后使用空格，而在参数列表中不使用空格。标准 Scala 社区风格指南建议在逗号后使用空格以提高可读性：

else if(!ordered(as(0), as(1))) false
//                     ↑
else isSorted(as.tail, ordered)
//                    ↑

标准的 Scala 社区风格指南还建议在控制流关键字之后使用空格，例如iforwhile以清楚地将它们与方法调用区分开来：

if (as.length == 0 || as.length == 1 || as.isEmpty) true
//↑
else if (!ordered(as(0), as(1))) false
//     ↑

另外，请注意，检查零长度和空虚是多余的，它们是同一件事：

if (as.length == 1 || as.isEmpty) true

最后，既然我们的方法只包含一个表达式，我们就不再需要花括号了：

@tailrec
def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean = 
  if (as.length == 1 || as.isEmpty) true
  else if (!ordered(as(0), as(1))) false
  else isSorted(as.tail, ordered)

然而，实际上有一个更好的方法来解决这个问题：如果每对连续的元素都是有序的，则对数组进行排序：

def isSorted[A](as: Array[A], ordered: (A, A) => Boolean) = 
  as.sliding(2).forall { case Array(a, b) => ordered(a, b) }

您的方法的签名不方便。类型推断仅从一个参数列表流向下一个参数列表，但不在一个参数列表中，因此在您的情况下，编译器将不知道Ain 的内容ordered，即使它已经知道Ain 的内容as：

isSorted(Array(1, 5, 3, 4), (a, b) => a < b)
// error: missing parameter type
// isSorted(Array(1, 5, 3, 4), (a, b) => a < b)
//                              ^
// error: missing parameter type
// isSorted(Array(1, 5, 3, 4), (a, b) => a < b)
//                                 ^

您必须明确告诉编译器类型：

isSorted(Array(1, 5, 3, 4), (a: Int, b: Int) => a < b)
//=> res: Boolean = false

因此，最好将函数参数放在单独的参数列表中：

def isSorted[A](as: Array[A])(ordered: (A, A) => Boolean) = 
  as.sliding(2).forall { case Array(a, b) => ordered(a, b) }

现在，类型推断按预期工作：

isSorted(Array(1, 5, 3, 4))((a, b) => a < b)
//=> res: Boolean = false

您还可以使用占位符阻止函数的语法：

isSorted(Array(1, 5, 3, 4)) { _ < _ }
//=> res: Boolean = false

最后，签名实际上比必要的要严格得多：实际上没有什么需要as是 a Array，它可以与更通用的类型一样工作，例如Seq：

def isSorted[A](as: Seq[A])(ordered: (A, A) => Boolean) = 
  as.sliding(2).forall { case Seq(a, b) => ordered(a, b) }

现在，我们也可以传递一个List，例如，而不是只传递Arrays。事实上，只要稍微改写一下方法，就应该可以让它对所有 Iterable的 s 都有效。

推荐阅读