Есть ли способ сохранить переменную внутри рекурсии, в haskell?

Question

Я пытаюсь определить функцию isInfixOf, и я пришел к решению (надеюсь, что оно работает хорошо: -)),
но из-за рекурсивной природы haskell я написал другую (справочную) функцию, которая
почти продублируйте код функции isInfixOf.

это код:

</p>

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

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

я сделал функцию справки, потому что мне нужен первый элемент функции 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. Чтобы сделать это в императивной программе, вам понадобятся вложенные циклы, здесь вам нужна вложенная рекурсия, лучше всего выполненная с помощью вспомогательной функции, как вы сделали. Проблема не в том, что listA каким-то образом будет потеряна без помощи helpFunction, проблема в том, что алгоритм требует, чтобы helpFunction выполнял список независимо от myIsInfixOf.

Если вы хотите избежать ручной реализации рекурсии myIsInfixOf, используя больше функций из стандартной библиотеки, вы можете использовать any и tails. Для helpFunction вероятно, реальная рекурсия - путь, но вы могли бы упростить весь последний случай до:

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

Answer 2

В соответствии с некоторыми предложениями Алексея Романова и других, это будет мой первоначальный вариант переписывания:

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 3

Обратите внимание, что 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 4

Я думаю, что вы путаете «элемент» и «аргумент» в своем вопросе, по крайней мере, в некоторых местах. Кроме того, что вы подразумеваете под «неприкасаемый»?

Возвращаясь к вашему вопросу: вы можете выполнить сопоставление с образцом и сохранить исходный аргумент, используя так называемые at-pattern:

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

Это позволяет вам ссылаться на весь первый аргумент как listA, первый элемент listA как x и хвост как xs (и то же самое для второго аргумента). Это то, что вы имели в виду?