为什么Scala使用一会而不是使用`find`进行递归

快速实验（使用Scala 2.13.2）。三种候选实现是：

• while循环
• 尾递归，但保持与while版本相同的逻辑
• 具有模式匹配的尾递归

我在适当的地方修改了逻辑，以减少对编译器优化的依赖（nonEmpty相对于!isEmpty显式保存，these.head因此不会被调用两次）。

  import scala.annotation.tailrec
  
  object ListFindComparison {
    def whileFind[A](lst: List[A])(p: A => Boolean): Option[A] = { 
      var these: List[A] = lst 
      while (these.nonEmpty) {
        val h = these.head

        if (p(h)) return Some(h)
        else these = these.tail
      }   
      None
    }
  
    def tailrecFind[A](lst: List[A])(p: A => Boolean): Option[A] = { 
      @tailrec
      def iter(these: List[A]): Option[A] =
        if (these.nonEmpty) {
          val h = these.head
          if (p(h)) Some(h)
          else iter(these.tail)
        } else None
  
      iter(lst)
    }
  
    def tailRecPM[A](lst: List[A])(p: A => Boolean): Option[A] = { 
      @tailrec
      def iter(these: List[A]): Option[A] =
        these match {
          case Nil => None
          case head :: tail if p(head) => Some(head)
          case _ => iter(these.tail)
        }   
  
      iter(lst)
    }
  }

在检查字节码（使用:javap ListFindComparison$）时，我们看到

对于whileFind，发出的代码很简单

Code:
   0: aload_1
   1: astore_3
   2: aload_3
   3: invokevirtual #25                 // Method scala/collection/immutable/List.nonEmpty:()Z
   6: ifeq          50
   9: aload_3
  10: invokevirtual #29                 // Method scala/collection/immutable/List.head:()Ljava/lang/Object;
  13: astore        4
  15: aload_2
  16: aload         4
  18: invokeinterface #35,  2           // InterfaceMethod scala/Function1.apply:(Ljava/lang/Object;)Ljava/lang/Object;
  23: invokestatic  #41                 // Method scala/runtime/BoxesRunTime.unboxToBoolean:(Ljava/lang/Object;)Z
  26: ifeq          39
  29: new           #43                 // class scala/Some
  32: dup
  33: aload         4
  35: invokespecial #46                 // Method scala/Some."<init>":(Ljava/lang/Object;)V
  38: areturn
  39: aload_3
  40: invokevirtual #49                 // Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
  43: checkcast     #21                 // class scala/collection/immutable/List
  46: astore_3
  47: goto          2
  50: getstatic     #54                 // Field scala/None$.MODULE$:Lscala/None$;
  53: areturn

尾递归发现基本相同：

aload_0
aload_1
aload_2
invokespecial   // call the appropriate (private) iter methods
areturn

该iter中tailrecFind是

Code:
   0: aload_1
   1: invokevirtual #25                 // Method scala/collection/immutable/List.nonEmpty:()Z
   4: ifeq          53
   7: aload_1
   8: invokevirtual #29                 // Method scala/collection/immutable/List.head:()Ljava/lang/Object;
  11: astore        4
  13: aload_2
  14: aload         4
  16: invokeinterface #35,  2           // InterfaceMethod scala/Function1.apply:(Ljava/lang/Object;)Ljava/lang/Object;
  21: invokestatic  #41                 // Method scala/runtime/BoxesRunTime.unboxToBoolean:(Ljava/lang/Object;)Z
  24: ifeq          39
  27: new           #43                 // class scala/Some
  30: dup
  31: aload         4
  33: invokespecial #46                 // Method scala/Some."<init>":(Ljava/lang/Object;)V
  36: goto          50
  39: aload_1
  40: invokevirtual #49                 // Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
  43: checkcast     #21                 // class scala/collection/immutable/List
  46: astore_1
  47: goto          0
  50: goto          56
  53: getstatic     #54                 // Field scala/None$.MODULE$:Lscala/None$;
  56: areturn

whileand的核心之间并没有太大的区别iter：在足够的调用之后，JIT很可能会将它们带到相同的机器代码中。tailrecFind与进入循环iter相比whileFind，进入的恒定开销要大一些。这里不可能存在有意义的性能差异（事实上，由于while将语言定义保留while为一点点，因此只要有谓词通过，尾部递归调用一个块的库函数就可以了）。

在iter与模式匹配有很大的不同：

Code:
   0: aload_1
   1: astore        5
   3: getstatic     #77                 // Field scala/collection/immutable/Nil$.MODULE$:Lscala/collection/immutable/Nil$;
   6: aload         5
   8: invokevirtual #80                 // Method java/lang/Object.equals:(Ljava/lang/Object;)Z
  11: ifeq          22
  14: getstatic     #54                 // Field scala/None$.MODULE$:Lscala/None$;
  17: astore        4
  19: goto          92
  22: goto          25
  25: aload         5
  27: instanceof    #82                 // class scala/collection/immutable/$colon$colon
  30: ifeq          78
  33: aload         5
  35: checkcast     #82                 // class scala/collection/immutable/$colon$colon
  38: astore        6
  40: aload         6
  42: invokevirtual #83                 // Method scala/collection/immutable/$colon$colon.head:()Ljava/lang/Object;
  45: astore        7
  47: aload_2
  48: aload         7
  50: invokeinterface #35,  2           // InterfaceMethod scala/Function1.apply:(Ljava/lang/Object;)Ljava/lang/Object;
  55: invokestatic  #41                 // Method scala/runtime/BoxesRunTime.unboxToBoolean:(Ljava/lang/Object;)Z
  58: ifeq          75
  61: new           #43                 // class scala/Some
  64: dup
  65: aload         7
  67: invokespecial #46                 // Method scala/Some."<init>":(Ljava/lang/Object;)V
  70: astore        4
  72: goto          92
  75: goto          81
  78: goto          81
  81: aload_1
  82: invokevirtual #49                 // Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
  85: checkcast     #21                 // class scala/collection/immutable/List
  88: astore_1
  89: goto          0
  92: aload         4
  94: areturn

这几乎不可能与没有模式匹配的版本相提并论（尽管公平地说，对于预测器而言，分支实际上将非常容易：未采用（not- Nil），未采用（::），未- （谓词失败），但最后一次运行除外。

对我来说有点有趣，我们equals在检查时会打电话给Nil它：它可能仍然比isEmpty/更快nonEmpty，但是如果没有模式匹配并且带有显式eq/ne反对，它甚至会更快Nil。

我还注意到，针对的模式匹配this是有点反模式的IMO：在这一点上，使用虚拟方法分派几乎可以肯定更好，因为您基本上是在实现慢速的vtable（它确实有可能预先如果您将普通情况放在首位，就可以这样做）。

如果您真的很在意性能，我会尽量避免模式匹配。

PS：我还没有分析简单的foldLeft解决方案：

lst.foldLeft(None) { (acc, v) =>
  acc.orElse {
    if (p(v)) Some(v)
    else None
  }
}

但是，由于这不会短路，因此我怀疑它不会一直击败任何一个候选者，即使在最后一个元素之前没有匹配的情况下，它甚至也可能没有匹配模式匹配的版本。