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

Question

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

это код:

 

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)
 

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

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

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

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

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

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

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

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