Определить подмножество с помощью рекурсии

Question

Я пытаюсь написать функцию subset, которая берет два списка и определяет, появляются ли элементы первого во втором.

Код компилируется в GHCi, но не запускается (то есть застревает) при вводе функции, подобной следующей:

subset [1,2] [1,2]

Это мой код:

subset :: (Eq a) => [a] -> [a] -> Bool
subset [] ys = True
subset (x:xs) ys
 | elem x ys = subset (x:xs) ys
 | otherwise =  False

Спасибо!

Answer 1

Давайте внимательно посмотрим на фрагмент вашего кода:

subset (x:xs) ys
 | elem x ys = subset (x:xs) ys

В случае выполнения elem x ys, что вполне вероятно, у вас есть

subset (x:xs) ys = subset (x:xs) ys

, который не приводит к уменьшениюлюбой из его аргументов и просто повторяет один и тот же вызов заново.

Следовательно, бесконечный цикл.

При работе с булевыми значениями принято использовать логические связки, что часто приводит к более лаконичными четкие определения:

subset (x:xs) ys = elem x ys && subset ..... .....

- это все, что вам нужно, потому что таблица истинности (&&) равна

    True  && x  =  x
    False && _  =  False

, т.е. когда первый аргумент равен false, значение второго аргумента равнодаже не осмотрен.

Answer 2

явная рекурсия не требуется;вы можете использовать all, чтобы убедиться, что (`elem` ys) истинно для каждого значения в xs:

subset xs ys = all (`elem` ys) xs

Answer 3

subset (x:xs) ys
 | elem x ys = subset (x:xs) ys
                   -- ^^^^^^ --

Обратите внимание, что приведенный выше рекурсивный вызов не меняет аргументы!Это приведет к бесконечной рекурсии.Вы хотите удалить x перед выполнением рекурсивного вызова.