This module implements the DP problem solver. Its input is an instance of the type DPProblem. This type holds two funcions:

• isTrivial that is true when an instance can be trivially solved.
• subproblems that decompose the instance in smaller subproblems.

It also holds initial, the initial instance of the problem, the one that you want to solve.

An example is the problem of finding the longest common subsequence of two lists (ie, the LCS of xs and ys is a list all whose elements appear both in xs and ys in the same order):

• If both xs and ys are empty, the problem is trivial.
• If not, check the heads of xs and ys. If they are equal, take it and find the lcs of the tails. If they are different, don't take the element and consider one list and the tail of the other.

In code:

import HyloDP

lcsDPProblem :: Eq a => [a] -> [a] -> DPProblem ([a], [a]) Int (Maybe a)
lcsDPProblem xs ys = DPProblem (xs, ys) isTrivial subproblems
  where isTrivial (xs, ys) = null xs || null ys
        subproblems (l@(x:xs), r@(y:ys))
          | x == y = [(1, Just x, (xs, ys))]
          | otherwise = [ (0, Nothing, (xs, r))
                        , (0, Nothing, (l, ys))
                        ]

We use Nothing to signal that the element is dropped and 'Just x' to signal that it is taken. Also, when we take an element, the score for that decision is one, while dropping the element scores zero.

Now, you can find the number of chars in common between "train" and "raising" like this:

print (dpSolve $ lcsDPProblem "train" "raising" :: TMax Int)

But you are probably more interesting in the best solution, so you can do

print (dpSolve $ lcsDPProblem "train" "raising" :: BestSolution Char (TMax Int))

As you can see, by choosing the appropriate semiring you decide what result you get.