CODEWITHSUNDEEP
scalarecursion
ferk86
ferk86

Reputation: 2345

How to convert recursion to fold

According to Erik Meijer, as functional programmers, we all know that instead of recursion, we should use fold. How do you convert the following to use fold? I can see one way with return, but return should also be avoided in fp. Thanks!

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

Upvotes: 0

Views: 632

Answers (3)

ferk86
ferk86

Reputation: 2345

Here's a solution with foldLeft. It is lengthy since I first wrote a generic function which is called by 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
    )
  }

Upvotes: 0

wingedsubmariner
wingedsubmariner

Reputation: 13667

You cannot implement this with a fold. A fold loops over every element of a collection, whereas tryOld will sometimes terminate early. You could take advantage of Stream's laziness and implement it in terms of collectFirst and 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)

but your original recursive implementation is clearer and more performant.

EDIT:

If Scala had a foldRight with the same laziness properties as Haskell's foldr, then this could be defined in terms of 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()
    }
  }

However, Scala's lack of true tail-call optimization means that each call to b will introduce a new stack frame, potentially leading to a stack overflow.

Upvotes: 2

Hugh
Hugh

Reputation: 8932

You can implement this with foldRight taking advantage of functions being values:

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

Note we use NonFatal here to avoid catching exceptions that we shouldn't be catching. You can write this in a more elegant way by not using exceptions directly.

Upvotes: 3

Related Questions