#list #haskell #recursion
#Список #haskell #рекурсия
Вопрос:
Я хотел бы знать, как поменять местами каждый второй элемент списка в Haskell.
Пример вывода должен выглядеть следующим образом:
swap [1,2,3,4,5]
[2,1,4,3,5]
Что у меня есть на данный момент, так это
swap :: [a] -> [a]
swap [] = []
swap (x:xs) = head xs : [x]
но при этом меняются местами только первые два элемента, и любая моя попытка сделать функцию рекурсивной вызывает ошибки при попытке загрузить файл, содержащий функцию. Как сделать это рекурсивным?
Комментарии:
1. Как насчет отображения ваших попыток и ошибок, которые это вызывает?
2. То, что я пытался сделать, это swap (x: xs) = head xs: [x] поменять местами xs . Ошибка при попытке загрузить файл: «haskell.hs:3:25: Функция
[x]' is applied to two arguments, but its type[a]’ не имеет none во втором аргументе(:)', namely[x] swap xs’ В выражении: head xs : [x] swap xs В уравнении для `swap’: swap (x: xs) = ошибка head xs: [x] swap xs, модули загружены: нет».
Ответ №1:
Вам нужно извлекать по 2 элемента одновременно:
swap [] = []
swap (x:y:rest) = y:x:(swap rest)
swap [x] = [x]
Последняя строка необходима для разрешения списков нечетной длины — она соответствует списку, имеющему длину ровно 1, поэтому она не перекрывает ни один из двух других случаев (длина 0 и длина 2 или более).
Комментарии:
1. Шаблоны empty и one-element могли бы быть более лаконично выражены как просто
swap other = otherпосле(x:y:rest)регистра.2. Спасибо за помощь. Я выяснил, как заставить ваш код работать со списками нечетного размера, добавив в swap [x] = [x]
3. @Chuck: Верно, но тогда вы должны поместить этот регистр последним, потому что он перекрывает другой регистр. Я чувствую себя более комфортно, когда регистры не пересекаются, поскольку тогда они могут располагаться в любом порядке (хотя, может быть, это плохой стиль?)
4. @j_random_hacker: К сожалению, моя шляпа арбитра стиля находится в уборщиках, но лично я ценю лаконичность больше, чем «возможность произвольно изменять порядок строк и заставить это работать». В коде Haskell очень нормально иметь общий список после ваших обычных случаев, поэтому я не думаю, что это кого-то сбило бы с толку.
Ответ №2:
В дополнение к другим довольно отличным ответам, вот решение, которое использует некоторые очень удобные библиотеки. Сначала установите split, который предоставляет множество очень приятных способов разделения списка. Наша стратегия для решения этой проблемы будет заключаться в том, чтобы сначала разделить ваш список на фрагменты второго размера, затем поменять местами каждый фрагмент, а затем объединить результат обратно в плоский список. Вот как работает ключевая функция:
Prelude Data.List.Split> chunk 2 [1..11]
[[1,2],[3,4],[5,6],[7,8],[9,10],[11]]
Чтобы поменять местами элементы каждого фрагмента, мы можем просто вызвать reverse . Таким образом, конечный результат таков:
Prelude Data.List.Split> let swap = concat . map reverse . chunk 2
Prelude Data.List.Split> swap [1..5]
[2,1,4,3,5]
Ответ №3:
Решение @j_random_hacker лучше, однако, если вы хотите довести свою реализацию до конца, вы могли бы попробовать это:
swap [] = []
swap (x:[]) = [x]
swap (x:xs) = head xs : x : (swap $ tail xs)
Обратите внимание, однако, что использование head и tail не является необходимым, и сопоставление с шаблоном может сделать здесь все намного чище.
Ответ №4:
import Data.Function(on)
swap = map snd . concatMap reverse . groupBy ((==) `on` fst) . zip (cycle "aabb")
Не воспринимайте мое решение слишком серьезно, я просто пытаюсь улучшить свой Haskell-Foo…