2014-09-02 216 views
0

我有一些遞歸代碼我想重構使用從Enumerator尾遞歸,我可以簡化遞歸看起來像這樣,請忽略此功能要實現的功能。可以函數尾遞歸

@tailrec 
def doStuff: List[Int] => Int = { 
     case Nil => 0 
     case x :: xs => doStuff(xs) 
    } 

如果我擺脫tailrec註釋,它做工精細,結構看起來像這樣doStuff(doStuff(doStuff(..)))。它會有stackoverflow異常。

所以,我怎樣才能使尾遞歸如果是

回答

5

匿名函數不能進行尾遞歸。讓我們先對代碼進行一次非常簡單的重寫,以引入一個val來保存結果函數。

@tailrec 
def doStuff: List[Int] => Int = { 
    val result: List[Int] => Int = { 
    case Nil => 0 
    case x :: xs => doStuff(xs) 
    } 
    result 
} 

應該清楚,從那裏,那是doStuff(xs)調用匿名函數本身。它調用方法doStuff,其中返回您要調用的函數。更糟的是,由於它是def,它實際上在每次呼叫時都會返回一個不同的功能。因此匿名函數絕對不會調用本身

這個問題概括爲這個簡單的事實:匿名函數是匿名的。所以他們無法直接調用自己:他們總是調用一些可能自行返回的defval,但編譯器不知道。

由於這個原因,只有合適的def像@dhg提出的那樣才真正是尾遞歸的。

現在,如果您確實想要返回一個函數值,那恰好是使用尾遞歸的情況來實現的,那麼您可以簡單地使用theMethod _將函數轉換爲函數。因此,解決您最初的問題是以下幾點:

val doStuff = { 
    @tailrec 
    def rec(list: List[Int]): Int = list match { 
    case Nil => 0 
    case x :: xs => rec(xs) 
    } 
    rec _ 
} 

請注意,我們聲明一個適當的尾遞歸方法rec),我們則變成一個函數值與rec _

1

也許你的意思是這樣的功能?

@tailrec 
def doStuff(list: List[Int]): Int = list match { 
    case Nil => 0 
    case x :: xs => doStuff(xs) 
} 
+0

不是真的,這是Int的返回類型,我仍然想返回類型爲一個函數。如果你看一下這個http://blog.higher-order.com/blog/2010/10/14/scalaz-tutorial-enumeration-based-io-with-iteratees/中enumerateFile的實現。幾乎所有的遞歸函數都不是尾遞歸的。這是我想改變的。 – 2014-09-02 04:19:28

+0

@Cloudtech [你可以用'doStuff _'調用把它變成函數值](http://scalafiddle.net/console/7bd66825e9a97424ffe5645549270832) – 2014-09-02 13:24:58

0

所以,我怎樣才能使尾遞歸如果它是一個功能

你不能。我的意思是,當然你可以在Scala中編寫一個尾遞歸函數,但它不會幫助你,因爲它不會被優化。

Scala只優化直接尾遞歸方法調用。