Rod Cutting in Functional Programming languages

Question

I tried implementing the rod cutting problem with memoization preferred in a functional programming language while trying to honor immutability, but I don't know how I can get around to doing so. The algorithm for the cutting rod problem is...

memoized-cut-rod(p, n)
let r[0..n] be a new array
for i = 0 to n
    r[i] = -infinity
return memoized-cut-rod-aux(p, n, r)

memoized-cut-rod-aux(p, n, r)
if r[n] >= 0
    return r[n]
if n == 0
    q = 0
else
    q = -infinity
    for i = 1 to n
        q = max(q, p[i] + memoized-cut-rod-aux(p, n - i, r))
    r[n] = q
return q

Can someone assist me in getting a purely functional approach to this algorithm?

Answer 1

I tried my best to make it purely functional. hope it satisfies

type P = Seq[Int]
type R = Seq[Option[Int]]
type M = (Int, R)
type N = (P, M)
type ~>[A, B] = PartialFunction[A, B]

val r: Int => R = Seq.fill(_)(None)

val exists: N ~> M = {
  case (_, (n, r)) => 
    r(n).fold(throw new MatchError)((_, r))
}

val zero: N ~> M = {
  case (_, (n, r)) if n == 0 =>
    (0, r.updated(n, Some(0)))
}

val other: (N => M, N) => M = {
  case (f, (p, (n, r))) =>
    ((0, r) /: (1 to n)) {
      case ((q, r), i) =>
        val (q1, r1) = f(p, (n - i, r))
        (math.max(q, q1), r1)
    }
}

val cut: N ~> M = exists orElse zero orElse {
  case n: N => other(cut, n)
}

Answer 2

The following is a translation of the top-down algorithm into Scala. The memoized values are local to memoizedCutRod so they have no impact on the environment, i.e., without side effects. I changed a couple of the names. The interior, recursive function uses p from the exterior function since it is not changing, and memo is share across all instances of the recursive function.

I also changed the use of - infinity to an Option[Int], so that we have a clear indicator that the value is not yet defined. I prefer that to the method of using an "impossible" number as a flag.

def memoizedCutRod(p: Array[Int], n: Int): Int = {
  val memo = new Array[Option[Int]](n+1)
  (0 to n).foreach(memo(_) = None)

  def memoizedCutRodAux(n: Int): Int = {
    if ( memo(n).isDefined ) memo(n).get
    else if ( n == 0 ) 0
    else {
      val q = (1 to n).map(i => p(i) + memoizedCutRodAux(n - i)).max
      memo(n) = Some(q)
      q
    }
  }

  memoizedCutRodAux(n)
}