Scala列表递归表现

发布时间：2020-12-16 09:20:17 所属栏目：安全来源：网络整理

导读：这个问题是关于 Scala与列表及其性能进行模式匹配和递归的方法. 如果我有一个在一个列表上递归的函数,并且通过匹配匹配来实现,例如： def myFunction(xs) = xs match { case Nil = Nil case x :: xs = ?something? myFunction(xs)} 在哈斯克尔 myFunction []

这个问题是关于 Scala与列表及其性能进行模式匹配和递归的方法.

如果我有一个在一个列表上递归的函数,并且通过匹配匹配来实现,例如：

def myFunction(xs) = xs match { 
  case Nil => Nil
  case x :: xs => ?something? myFunction(xs)
}

在哈斯克尔

myFunction [] = []
myFunction (x:xs) = ?something? : myFunction xs

我正在使用与我所做的相同的语义,例如Haskell.我认为没有任何关于Haskell实现的问题,因为这只是处理列表的方式.对于一个长列表(我将在具有几千个节点的列表中运行),Haskell不会闪烁(我想象,我从来没有尝试过).

但是根据我对Scala的理解,匹配语句将调用unapply extractor方法来将列表围绕cons进行拆分,并将示例扩展到对列表不起作用的函数：

def myFunction(xs) = xs match { 
  case Nil => Nil
  case x :: xs => x :: myFunction(xs)
}

在哈斯克尔

myFunction [] = []
myFunction (x:xs) = x : myFunction xs

它将调用应用提取方法将其反馈到一起.对于长列表,我想象这将是非常昂贵的.

为了说明,在我的具体情况下,我想递归一个字符列表,并积累各种各样的东西,输入字符串最多可达几十千字节.

如果我想在长列表中递归,我真的会在递归的每个步骤中调用构造函数和提取器吗？还是有优化？还是更好的方法呢？在这种情况下,我将需要几个累加器变量,显然我不会只是通过列表执行递归运算…

(请原谅我的Haskell,我没有写了两年.)

(是的,我要进行尾递归.)

解决方法

首先,Haskell是非严格的,所以尾部的这些函数调用根本就不会被评估.另一方面,Scala将在返回之前计算所有列表.对Haskell发生的事情将会更加紧密地实现：

def myFunction[T](l: List[T]): Stream[T] = l match {   
  case Nil => Stream.empty  
  case x :: xs => x #:: myFunction(xs)
}

它接收到一个List,这是一个严格的,并返回一个非严格的Stream.

现在,如果你想避免模式匹配和提取器(虽然在这种特殊情况下没有调用 – 请参见下文),你可能只是这样做：

def myFunction[T](xs: List[T]): Stream[T] =
  if (xs.isEmpty) Stream.empty else xs.head #:: myFunction(xs.tail)

我只是意识到你打算去尾巴递归.你写的不是尾递归的,因为你将x加上递归的结果.处理列表时,如果您向后计算结果然后反转,您将得到尾递归：

def myFunction[T](xs: List[T]): List[T] = {
  def recursion(input: List[T],output: List[T]): List[T] = input match {
    case x :: xs => recursion(xs,x :: output)
    case Nil => output
  }
  recursion(xs,Nil).reverse
}

最后,我们来反编译一个例子,看看它是如何工作的：

class ListExample {
  def test(o: Any): Any = o match {
    case Nil => Nil
    case x :: xs => xs
    case _ => null
  }
}

产生：

public class ListExample extends java.lang.Object implements scala.ScalaObject{
public ListExample();
  Code:
   0:   aload_0
   1:   invokespecial   #10; //Method java/lang/Object."<init>":()V
   4:   return

public java.lang.Object test(java.lang.Object);
  Code:
   0:   aload_1
   1:   astore_2
   2:   getstatic       #18; //Field scala/Nil$.MODULE$:Lscala/Nil$;
   5:   aload_2
   6:   invokestatic    #24; //Method scala/runtime/BoxesRunTime.equals:(Ljava/lang/Object;Ljava/lang/Object;)Z
   9:   ifeq    18
   12:  getstatic       #18; //Field scala/Nil$.MODULE$:Lscala/Nil$;
   15:  goto    38
   18:  aload_2
   19:  instanceof      #26; //class scala/$colon$colon
   22:  ifeq    35
   25:  aload_2
   26:  checkcast       #26; //class scala/$colon$colon
   29:  invokevirtual   #30; //Method scala/$colon$colon.tl$1:()Lscala/List;
   32:  goto    38
   35:  aconst_null
   36:  pop
   37:  aconst_null
   38:  areturn

public int $tag()   throws java.rmi.RemoteException;
  Code:
   0:   aload_0
   1:   invokestatic    #42; //Method scala/ScalaObject$class.$tag:(Lscala/ScalaObject;)I
   4:   ireturn

}

解码,它首先调用方法equals对传递的参数和对象Nil.如果为真则返回后者.否则,它调用对象上的instanceOf [::].如果为true,则将该对象转换为该对象,并调用该方法.失败所有这些,加载cosntant null并返回它.

所以,你看,x :: xs没有调用任何提取器.

对于积累,还有另一种模式,你可能想考虑：

val list = List.fill(100)(scala.util.Random.nextInt)
case class Accumulator(negative: Int = 0,zero: Int = 0,positive: Int = 0)
val accumulator = list.foldLeft(Accumulator())( (acc,n) => 
  n match {
    case neg if neg < 0 => acc.copy(negative = acc.negative + 1)
    case zero if zero == 0 => acc.copy(zero = acc.zero + 1)
    case pos if pos > 0 => acc.copy(positive = acc.positive + 1)
  })

默认参数和复制方法是Scala 2.8功能,我只是为了使示例更简单,但是当您想要通过列表累积事物时,使用foldLeft方法.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!