斯卡拉列表遞歸性能

Question

這個問題是關於斯卡拉做模式匹配和遞歸列表和其性能的方式。

如果我有一個遞歸在列表的功能，我在利弊相匹配，例如像做：

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

在Haskell：

myFunction [] = [] 
myFunction (x:xs) = «something» : myFunction xs 

我使用例如Haskell，我會用同樣的語義。我不認爲會有關於Haskell實現的任何問題，因爲這是簡單的，你對付列表的方式。對於一個長長的清單，哈斯克爾不會閃爍（我將與幾千個節點列表上操作）（我想雖然，我從來沒有嘗試過）。

但是，從我與斯卡拉了解，本場比賽的語句將調用不應用抽提法拆分列表周圍的利弊，並在例如延伸到無助於列表中的功能：

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

在Haskell中：

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

它會調用應用提取器方法將它重新組合起來。對於一長串名單，我想這將是非常昂貴的。

爲了說明這一點，在我的特定情況下，我想在遞歸字符列表和積累各種事情，其中​​輸入字符串是什麼，高達幾十千字節。

請問我真的叫構造函數和提取的遞歸的每一步，如果我想在遞歸一個長長的清單？還是有優化？或更好的方法來做到這一點？在這種情況下，我需要幾個累加器變量，很明顯，我不會只是被遞歸地在一個列表無所事事...

（請原諒我的哈斯克爾，我沒有寫過一行兩年。）

（是的，我要去尾遞歸。）

Answer 1

首先，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。如果爲true，則返回後者。否則，它會在對象上調用instanceOf[::]。如果爲true，則將該對象轉換爲該對象，並調用其上的方法tl。如果沒有這些，加載協調員null並返回它。

所以，你看，​​沒有調用任何提取器。

至於積累，還有就是你可能要考慮另一種模式：

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) 
    }) 

的默認參數和複製方法是斯卡拉2.8功能，我只是用來讓這個例子更簡單，但問題是使用當你想要在列表上累積東西時使用方法foldLeft。