如何將遞歸轉換爲摺疊

根據Erik Meijer的說法，作爲函數式程序員，我們都知道代替遞歸，我們應該使用fold。你如何轉換以下使用摺疊？我可以看到返回的一種方式，但返回也應該在fp中避免。謝謝！如何將遞歸轉換爲摺疊

def tryOld(string: String, original: Exception, zomOldList: List[String => Double]): Double = { 
    zomOldList match { 
    case Nil => 
     throw original 
    case head :: tail => 
     try { 
     head(string) 
     } catch { 
     case ex: Exception => 
      tryOld(string, original, tail) 
     } 
    } 
}

來源

2014-05-18 ferk86

遞歸有什麼問題呢？遞歸非常適合解決遞歸問題。 –

遞歸可以工作，只需從另一個角度查看解決方案。我回答了一個帖子，下面有一個函數拋出異常可能是一個不好的做法。使用Try [Double]使用fold應該可以工作。 – ferk86

以下是foldLeft的解決方案。從我第一次寫一個通用函數開始，這段代碼被tryOldString調用

def tryOld[In, Error, Out](
    in: In, 
    original: Error, 
    zomOldList: List[In => Either[Error, Out]] 
): Either[Error, Out] = { 
    val seed: Either[Error, Out] = Left(original) 
    zomOldList.foldLeft(seed) { 
     case (prev, f) => 
     // stores first match without return 
     if (seed != prev) { 
      prev 
     } else { 
      f(in).fold(
      fa => 
       prev, 
      fb => 
       Right(fb) 
     ) 
     } 
    } 
    } 

    def tryOutString(string: String, original: Exception, zomOldList: List[String => Double]): Double = { 
    val zomFunctions: List[String => Either[Exception, Double]] = zomOldList.map { 
     f => 
     s: String => 
      try { 
      Right(f(s)) 
      } catch { 
      case e: Exception => 
       Left(e) 
      } 
    } 
    tryOld(string, original, zomFunctions).fold(
     bad => throw original, 
     good => good 
    ) 
    }

來源

2014-05-22 02:09:58 ferk86

你不能實現這個摺疊。摺疊循環遍及集合的每個元素，而tryOld有時會提前終止。你可以利用Stream的懶惰和在collectFirst和Try方面實現：

import scala.util.Try 

def tryOld(string: String, original: Exception, zomOldList: List[String => Double]): Double = 
    zomOldList.toStream.map(x => Try(x(string))) collectFirst { 
    case Success(x) => x 
    } getOrElse (throw original)

但你原來的遞歸實現更清晰和更高性能。

編輯：

如果斯卡拉曾與同懶惰屬性Haskell的foldr一個foldRight，那麼這可能是在來定義的foldRight：

implicit class GiveStreamAWorkingFoldRight[A](val s: Stream[A]) extends AnyVal { 
    def lazyFoldRight[B](z: => B)(f: (A,() => B) => B): B = 
    if (s.isEmpty) z else f(s.head,() => s.tail.lazyFoldRight(z)(f)) 
} 

def tryOld(string: String, original: Exception, zomOldList: List[String => Double]): Double = 
    zomOldList.toStream.lazyFoldRight(throw original) { (a, b:() => Double) => 
    try { 
     a(string) 
    } catch { 
     case ex: Exception => b() 
    } 
    }

然而，Scala的缺乏真正的尾巴優化意味着每次調用b都會引入一個新的堆棧幀，可能導致堆棧溢出。

來源

2014-05-18 03:47:45 wingedsubmariner

如果你正在使用Scalaz，那麼我認爲'lazyFoldRight'已經在'FoldableSyntax'中作爲'foldr'存在。 – Hugh

您可以foldRight利用的功能是價值的實現這個：

import util.control.NonFatal 
def tryOld(string: String, original: Exception, zomOldList: List[String ⇒ Double]): Double = { 
    val unhandled: String ⇒ Double = _ ⇒ throw original 
    zomOldList.foldRight(unhandled) { (f, z) ⇒ 
    x ⇒ try { f(x) } catch { case NonFatal(_) ⇒ z(x) } 
    }(string) 
}

注意，我們使用NonFatal這裏避免受涼，我們不應該捕捉異常。您可以通過不直接使用異常的方式以更優雅的方式編寫此代碼。

來源

2014-05-18 13:16:17 Hugh

這非常聰明，我根本沒有預料到這個解決方案。它比我的要乾淨得多。但是，Scala缺乏真正的tail-call優化意味着每次調用'z'都會引入一個新的堆棧幀，可能會導致堆棧溢出。我的答案遭受同樣的問題。 – wingedsubmariner

是的。當我明天上班時，我會看看更好的解決方案。具有函數拋出異常的 – Hugh

可能是一種不好的做法。使用Try [Double]使用fold應該可以工作。 – ferk86

如何將遞歸轉換爲摺疊

回答

相關問題