score:0
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)
}
score:0
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)
}
Source: stackoverflow.com
Related Query
- Rod Cutting in Functional Programming languages
- Simple sum of two numbers file i/o in F#, Haskell, Scala, and Visual Basic or other functional programming languages
- Functional programming - is immutability expensive?
- Difference between reduce and foldLeft/fold in functional programming (particularly Scala and Scala APIs)?
- Functional Programming - Lots of emphasis on recursion, why?
- Which programming languages can be used to develop in Android?
- Which programming languages can I use on Android Dalvik?
- Functional Reactive Programming in Scala
- Is Scala functional programming slower than traditional coding?
- Object-oriented programming in a purely functional programming context?
- Mixing object-oriented and functional programming
- Functional languages targeting the LLVM
- Real World Functional Programming in Scala
- Functional languages (Erlang, F#, Haskell, Scala)
- What does the "world" mean in functional programming world?
- Dynamic programming in the functional paradigm
- Is Scala a Functional Programming Language?
- Js Deferred/Promise/Future compared to functional languages like Scala
- Other programming languages that support implicits "a la Scala"
- Are there any LL Parser Generators for Functional Languages such as Haskell or Scala?
- Functional Programming + Domain-Driven Design
- Which JVM functional languages are well IDE-supported? (IDE: IDEA, Netbeans, Eclipse or similar)
- Is Reactive Programming bounded to Functional programming?
- How will Dotty change pure functional programming in Scala?
- Function Overhead in Functional Languages like Haskell or in Hybrids like Scala
- Generate a DAG from a poset using stricly functional programming
- Type systems of functional object-oriented languages
- What is the added value of the kestrel functional programming Design Pattern? (Scala)
- Functional programming applied
- Batch processing and functional programming
More Query from same tag
- play compile error Cannot access term libs in value <root>.api. The current classpath may be missing a definition for <root>.api.libs,
- Rogue query orderAsc with variable field according to its name
- Is it (really that) bad to use case-classes for mutable state?
- finding least subset in an rdd in spark
- There is a HTTP server starts when Launching Spark jar on a machine, what's that?
- How to pass Java List to Scala, filter it in Scala and get back to Java?
- Play with jquery autocomplete proper usage
- Scala RegexParser calculator example right-associativity
- scala pattern matching on scala.collection.script.Message
- Scala Play no application started when grabbing data sources from application.conf
- How can I use the new Slick 2.0 HList to overcome 22 column limit?
- Build a Scala package dependency graph
- Scala shapeless KList with extra constraint
- Dynamic Akka streams sink
- Connecting to wildcard ip 0.0.0.0 works in a container, but not on the host
- Spark Scala GroupBy
- how to recognise specific text with selenium?
- Private Chat Application using Play 2.3 Websocket
- Does anyone knows how to create a DenseVector[Double] using Breeze library in scala
- compareTo type error
- How to traverse column of dataset in spark?
- Java Wildcard Generic Type Interop From Scala
- building query/filter in scala eclipse plugin for elastic search
- Play server refuses to start with google-cloud dependency
- Remove field from array.struct in Spark
- Scala's state of type inference regarding Scalaz
- Sharepoint Online Authentication with Play Framework web application (Scala)
- Scala: "val" as identifier possible? Linking to java library needs it
- Slick MultiDB Configuration
- Calculate hash for java.sql.ResultSet