Writing A Function Using Helper Functions

Question

I'm trying to write a function in Scheme that takes two strings as input and returns a list of all optimal pairs of strings. In order to do this, I know that I need to make use of the following functions that I have already written. The functions already written will obviously need to be used as helper functions for the function that I'm trying to write.

1. score-chars

This function takes two strings, and scores each character according to a scoring criteria and accumulates the result. If two characters are equal, a score of 2 is obtained, if two characters are not equal, a score of -1 is obtained, and finally, if one character is an underscore, and the other character something else, a score of -2 is obtained.

Here is example input/output:

> (score-chars "x" "x")
2

> (score-chars "x" "y")
-1

> (score-chars "x" "_")
-2

> (score-chars "Cheese" "Computer")
-3  

2. change-string-pairs

This function takes two chars (a and b, say) and a list of pairs of strings as input, and returns a modified list of pairs of strings: for each string pair in the list.

Here is example input/output:

> (change-string-pairs "a" "b" '(("one" "two")("three" "four")("five" "six")))
(("aone" "btwo") ("athree" "bfour") ("afive" "bsix"))

3. get-best-pairs

This function takes both a scoring function (scoring function in this case will be score-chars, which is described above) and a list of pairs of strings as input and then returns a modified list of pairs of strings. The returned list will contain all the optimal string pairs from the input, scored according to the input function.

Here is example input/output:

> (get-best-pairs score-chars '(("cheese" "cake")("door" "wall")("bunny" "roof")("mouse" "house")("photo" "video")))
(("mouse" "house"))

Having all these functions described above that I have already written, the function that I'm trying to write using those functions will have the following:

Input/output:

> (get-all-best-pairs "many" "penny")
(("man_y" "penny") 
 ("ma_ny" "penny") 
 ("m_any" "penny") 
 ("_many" "penny")) 

Would be really great, if I can get a rough idea of how this can be done. Also, in my functions that I have written above, I have made use of some built in Scheme functions like map, filter, append and apply.

I also am aware, that the algorithm is extremely inefficient, and is of exponential complexity. That is not of a concern to me at this time.

I know that the first step is to write a function that will generate all possible sequence matches. Once I have this function, the rest will be easy. Hence, this is the part where I am really stuck.

Answer 1

I think you have almost everything you need except for a function that can sort a list using a predicate function.

If your Scheme interpreter does not provide a sorting function, you can use one found at Wikibooks . You'll have to adapt it to take a predicate function instead of using <= as the default predicate function.

Your predicate function can be:

(define (compare-by-alignment lhs rhs)
   (<= (alignment-score-tail lhs) (alignment-score-tail rhs)))

You can call merge-sort using your list and predicate function as:

(merge-sort lst compare-by-alignment)