在haskell中，有没有一种方法可以防止变量在递归内部发生变化？

Question

我正在尝试定义 isInfixOf 函数，并且我找到了一个解决方案（希望它能正常工作:-)），
但由于 haskell 的递归性质，我编写了另一个（帮助）函数
几乎重复函数 isInfixOf 的代码。

这是代码：

 myIsInfixOf :: (Eq a) =>; [一]-> [一]->布尔
myIsInfixOf [] [] = True
myIsInfixOf [] 列表 = True
myIsInfixOf 列表 [] = False
myIsInfixOf 列表A 列表B | myIsInfixOf helpFunction listA listB == True = True
                        |否则 = myIsInfixOf listA (tail listB)

 helpFunction :: (Eq a) => [一]-> [一]->布尔
帮助函数 [] [] = True
helpFunction [] 列表 = True
帮助函数列表 [] = False
帮助函数 (x:xs)(y:ys) | x == y = helpFunction xs ys
                          |否则=假

我执行了帮助功能，因为我需要 myIsInfixOf 函数的第一个元素，不可触及。
如果我不创建这个 helpFunction，函数 myIsInfixOf 的第一个元素总是减少一个元素，这不好，因为我需要迭代函数 myIsInfixOf 的整个第二个元素，并检查与第一个元素是否相等它的元素。
在 helpFunction 的帮助下，列表中的第一个元素是不可触及的，只有第二个元素正在减少每次递归（这很好）。

那么，我可以将 myIsInfixOf 的第一个元素保存在某个地方，而不需要重新编码几乎所有内容吗？

谢谢。 :-)

Answer 1

如果你仔细观察的话，这两个函数其实并不那么相似。前三个“琐碎”案例是相同的，但最后一个案例在两个函数中执行不同的操作。您还可以在这两个函数中省略前两种情况，因为它们在相同的列表上检查相同的内容。所以 myIsInfixOf 也可以这样工作：

myIsInfixOf :: (Eq a) => [a] -> [a] -> Bool
myIsInfixOf (a:as) [] = False
myIsInfixOf listA listB | helpFunction listA listB = True
                        | otherwise =  myIsInfixOf listA (tail listB)

这确实与 helpFunction 不同，并且不重复任何重要的代码。

另外，您确实希望第二个函数独立于第一个函数工作，因为您希望检查 listB 中的每个位置，如果 listA 的每个字符都与 listB 中的字符匹配。要在命令式程序中执行此操作，您需要嵌套循环，这里您需要一个嵌套递归，最好像您一样使用辅助函数来完成。问题不在于如果没有 helpFunction，listA 会以某种方式丢失，问题在于该算法需要 helpFunction 独立于 myIsInfixOf 运行列表>。

如果您想通过使用标准库中的更多函数来避免手动实现 myIsInfixOf 的递归，您可以使用 any 和 tails。对于 helpFunction 可能显式递归是可行的方法，但您可以将最后一种情况简化为：

helpFunction (x:xs) (y:ys) = (x == y) && helpFunction xs ys

Answer 2

请注意，1）在这两种情况下都不需要第一个子句，因为 [] list 也匹配 [] [] 并且返回相同的结果； 2) helpFunction listA listB == True 与 helpFunction listA listB 相同。

myIsInfixOf :: (Eq a) => [a] -> [a] -> Bool
myIsInfixOf [] list = True
myIsInfixOf list [] = False
myIsInfixOf listA listB | helpFunction listA listB = True
                        | otherwise =  myIsInfixOf listA (tail listB)

helpFunction :: (Eq a) => [a] -> [a] -> Bool
helpFunction [] list    = True
helpFunction list []    = False
helpFunction (x:xs)(y:ys) | x == y = helpFunction xs ys
                          | otherwise = False

你在评论中说

帮助函数检查第一个元素是否在第二个元素内。

事实上，事实并非如此。它检查第二个参数是否以第一个参数开始。这就是为什么你需要一个不同的函数。因此 helpFunction 的更好名称是 myPrefixOf。这应该可以帮助您从 myIsInfixOf 的定义中消除另一个子句。

Answer 3

根据 Alexey Romanov 等人提出的一些建议，这将是我重写它的初步看法：

import Data.List

myIsInfixOf xs ys = any (myIsPrefixOf xs) (tails ys)

myIsPrefixOf [] _ = True
myIsPrefixOf (x:_) [] = False
myIsPrefixOf (x:xs) (y:ys) = x == y && myIsPrefixOf xs ys

为了更直接地回答您的实际问题，请注意有关此版本的两件事：

• 您可以“保存”使用部分应用程序的第一个参数
• 您可以通过使用内置递归函数消除大量冗余代码

Answer 4

我认为您在问题中混淆了“元素”和“论证”，至少在某些地方是这样。另外，你所说的“不可触碰”是什么意思？

回到你的问题：你可以使用所谓的 at-patterns 进行模式匹配并保留原始参数：

myIsInfixOf listA@(x:xs) listB@(y:ys) = ...

这使你可以将整个第一个参数称为 listA，将 listA 的第一个元素称为 x 和尾部作为 xs （与第二个参数相同）。这就是你的意思吗？