Longest common subsequence (Haskell)

2
votes

I've been struggling with this for a while. I'm solving the longest common subsequence problem in Haskell as a learning exercise.

I have a function f1 that is passed two Ints i and j, and a function f2. f1 builds a two dimensional list so that the (i,j) location in the list is equal to f2 i j.

Now I'm trying to write a function called lcs that takes two Strings s1 and s2 and finds the longest common subsequence using f1 for memoization.

I'm not exactly sure how to set this up. Any ideas?

Code:

f1 :: Int -> Int -> (Int -> Int -> a) -> [[a]]

f2 :: Int -> Int -> a

lcs:: String -> String -> Int
1
haskell
I don't completely understand what f1 and f2 do. Is it possible to post the code? Here are the type signatures as I understand them: f1 :: Int -> Int -> a; f2 :: Int -> Int -> a. What's the difference? - Andres Riofrio
@AndresRiofrio: Maybe xcross means f1 :: (Int -> Int -> a) -> [[a]] s.t. f1 f2 !! i !! j == f2 i j. - rampion
@rampion: How about f1 :: Int -> Int -> (Int -> Int -> a) -> [[a]] and f2 :: Int -> Int -> a? So that f1 _ _ f2 !! i !! j == f2 i j. - Andres Riofrio
@AndresRiofrio added some code. Thanks guys. - user686605
Solve recursively first (as defined (not implemented) on wikipedia), don't worry about the exponential time. Then, after that is implemented correctly, go back and memoize (there are various techniques for this, but that's fodder for another SO question). - luqui

1 Answers

4
votes

I assume the Int parameters of f1 are some sort of bounds? Remember that using lists give you the benefit of not needing to specify bounds (because of laziness), but it costs you slow access times.

This function should do what you want f1 to do (memoize a given function): 

memo :: (Int -> Int -> a) -> (Int -> Int -> a)
memo f = index where
  index x y = (m !! x) !! y
  m         = [[f x y|y <- [0..]]|x <- [0..]]

-- memoized version of f2
f2' = memo f2