用辅助函数编写函数 [英] Writing A Function Using Helper Functions

问题描述

我试图在Scheme中编写一个函数，它将两个字符串作为输入并返回所有最佳字符串对的列表。为了做到这一点，我知道我需要使用我已经写过的以下函数。已经编写的函数显然需要用作我正在编写的函数的辅助函数。

1。 score-chars

该函数接受两个字符串，并根据评分标准对每个字符进行评分并累积结果。如果两个字符相等，则得分为2，如果两个字符不相等，则得分为-1，最后，如果一个字符是下划线，而另一个字符是其他字符，则得分为-2被获得。

以下是输入/输出示例：

 > （得分字符xx）
 2 
 
> （得分字符xy）
 -1 
 
> （得分字符x_）
 -2 
 
> （得分字符奶酪电脑）
 -3 
  

2 。 change-string-pairs

这个函数接受两个字符（a和b，比如说）和一串字符串作为输入，并返回一个修改

以下是输入/输出示例：

 > （（一，二）（三四）（五六）））
（（aone btw）（avereebfour）（afivebsix））
  

<强> 3。 get-best-pair

这个函数同时包含一个评分函数（在这种情况下评分函数将是score-chars，如上所述）和一个输入字符串对列表，然后返回修改后的字符串对列表。返回的列表将包含来自输​​入的所有最优字符串对，根据输入函数进行评分。

以下是输入/输出示例：

 > （奶酪蛋糕）（门墙）（兔子屋顶）（鼠标房子）（照片视频 ））
（（mousehouse））
  

拥有所有这些功能如上所述，我已经写过，我试图用这些函数编写的函数将具有以下内容：

输入/输出：

 > （（man_ypenny）
（ma_nypenny）
（m_any便士） ）
（_manypenny））
  

我可以大致了解如何做到这一点。另外，在我上面写的函数中，我使用了一些内置的Scheme函数，如map，filter，append和apply。

我也意识到，该算法效率极低，而且具有指数级的复杂性。这是我目前不关心的。

我知道第一步是编写一个函数来生成所有可能的序列匹配。一旦我有了这个功能，其余的将会很容易。因此，这是我真正陷入困境的部分。 对于可以使用谓词函数对列表进行排序的函数。

如果您的Scheme解释器不提供排序功能，您可以使用 Wikibooks 。您必须修改它以使用谓词函数而不是使用< = 作为默认谓词函数。

您的谓词函数可以是：

$ $ p $ （define（比较对齐lhs rhs）
（< =（alignment-score-tail lhs）（alignment-score-tail rhs）））


你可以请使用列表和谓词函数调用 merge-sort ：

 （合并排序第一比较对齐）
  

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.

解决方案

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)

这篇关于用辅助函数编写函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！