Удаление n числа элементов из списка

Question

Одним из моих модулей в этом году является программирование Haskell. У меня возникли проблемы с выражением сложности таким простым способом, особенно с других языков, таких как C#.

Часть процесса ознакомления включает в себя реализацию функции drop, которая удаляет из числа число n элементов.

Напишите функцию drop ':: Int -> [a] -> [a], где drop' n xs возвращает xs с удалением первых n элементов.

До сих пор это то, что я придумал.

drop' :: Int -> [a] -> [a] 
drop' x [] = [] 
drop' x (y : ys) = if x == 0 then ys else drop' (x-1) ys 

Я знаю, что нужно рекурсивно назвать падение»на хвосте списка, чтобы эффективно удалить элемент, но я не знаю, как вести подсчет, сколько элементов я снял, так что я могу гарантировать, что я удалите n элементов.

Я знаю, что выше не дает мне результат я ожидал, как он удаляет более 1, чем я ожидал, но интересно это работает:

drop' :: Int -> [a] -> [a] 
drop' x [] = [] 
drop' x (y : ys) = if x == 1 then ys else drop' (x-1) ys 

И я не могу вывести почему! Любая помощь с логикой этого будет очень признательна!

Answer 1

Вы не нужно следить за тем, сколько элементов у вас есть снято до сих пор, только у вас еще есть, и это значение параметра x. Итак, у вас уже есть эта часть.

Проблема с вашей первой версией функции заключается в том, что когда x равно 0, вы возвращаете ys, но это только хвост списка, так как вы уже удалили первый элемент с помощью сопоставления шаблонов в списке аргументов. Вам нужно будет использовать if x == 0 then (y:ys), чтобы вернуть весь список ввода.

В качестве альтернативы, вы можете использовать функцию tail в рекурсивном случае вместо сопоставления с образцом:

drop' x ys = if x == 0 then ys else drop' (x-1) (tail ys) 

И вы можете поставить нулевой случай на отдельной строке, вместо того, чтобы использовать if, поэтому в целом определение это:

drop' :: Int -> [a] -> [a] 
drop' _ [] = [] 
drop' 0 ys = ys 
drop' x ys = drop' (x-1) (tail ys) 

Answer 2

В коде здесь:

drop' x (y : ys) = If x == 0 then ys else drop' (x-1) ys 

Это источник вашей ошибки вне по одному: если x является 0, то вы хотите возвратить весь список изменений (y:ys), а не только хвост (ys). Эквивалентно, вы можете проверить 1 вместо 0, а затем вернуться ys.

Было бы более идиоматических использовать соответствия шаблону вместо if, и вы должны использовать переменную _ не-ухода за ценности, которые вы не используете:

drop' :: Int -> [a] -> [a] 
drop' _ [] = []   -- dropping any number of items from [] is still empty 
drop' 0 lst = lst   -- dropping nothing returns the list unchanged 
drop' n (_:xs) = drop' (n-1) xs -- otherwise remove head and recurse on the tail 

Answer 3

Следующий подход может оказаться поучительным, даже если рекурсия не используется.Рассмотрим это понимание,

drop' :: Int -> [a] -> [a] 
drop' n xs = [ v | (_,v) <- filter (\(x,_) -> x > n) $ zip [1..] xs ] 

Качества, представляющие интерес в этом примере,

• мы (лениво) список почтовый xs со значением индекса, начиная с 1 до числа элементов в xs;
• filter включает в себя лямбда-функцию, которая извлекает первый элемент в кортежей zipped и сравнивает значение с количеством элементов, которые нужно удалить;
• для каждого отфильтрованного кортежа, мы извлекаем второй элемент, значение из исходного списка.

Тогда, например

drop' 4 ['a'..'t'] 
"efghijklmnopqrst"