Повторяющиеся элементы списка на четном индексе

Question

В Haskell, как мне реализовать функцию dup, которая дублирует все элементы, которые находятся на четных позициях (0,2,4 ...) в списке

dup :: [a] -> [a]
dup [] = []
dup (x:xs) =  x : x : dup xs
//but only on even index ??

Пример вызова:

dup [1,5,2,8,4] = [1,1,5,2,2,8,4,4]

Answer 1

Ну, мы можем определить две функции, которые выполняют взаимную рекурсию : dupeven :: [a] -> [a] и dupodd :: [a] -> [a].dupeven, таким образом, будет дублировать первый элемент, и проход рекурсивно к dupodd.dupodd, с другой стороны, делает только одну копию головы, а затем выполняет рекурсию на dupeven.Как:

dupeven :: [a] -> [a]
dupeven [] = []
dupeven (x:xs) = x : x : <b>dupodd xs</b>

dupodd :: [a] -> [a]
dupodd [] = []
dupodd (x:xs) = x : <b>dupeven xs</b>

Приятно то, что мы получаем два дублированных варианта.Кроме того, обе функции довольно просты: они работают только с двумя различными шаблонами: пустым списком [] и "cons" (:).

Таким образом, это работает, как и ожидалось, и, кроме того, у нас в основном есть дополнительная функция в(скорее) низкая стоимость реализации:

Prelude> dupeven [1,5,2,8,4]
[1,1,5,2,2,8,4,4]
Prelude> dupodd [1,5,2,8,4]
[1,5,5,2,8,8,4]

Answer 2

Как объясняют другие ответы, вы можете написать эту функцию рекурсивно из первых принципов, но я всегда думаю, что проблемы, подобные этим, являются интересными загадками: как вы можете составить такую ​​функцию из существующей базовой библиотеки?

Во-первых, всякий раз, когда вы хотите проиндексировать список, вы можете zip создать его с лениво вычисленным бесконечным списком:

Prelude> zip [0..] [1,5,2,8,4]
[(0,1),(1,5),(2,2),(3,8),(4,4)]

В этом случае вам не нужно знатьфактические значения индекса (0, 1, 2, 3, 4 и т. д.).Вместо этого вам просто нужно знать, сколько повторений каждого числа вам нужно.Вы можете получить это знание путем бесконечного циклического переключения между 2 и 1:

Prelude> take 10 $ cycle [2,1]
[2,1,2,1,2,1,2,1,2,1]

(В приведенном выше примере для остановки списка используется take 10, который, в противном случае, продолжается вечно.)

Вы можете zip (cycle [2,1]) с любым списком ввода, чтобы получить список кортежей:

Prelude> zip (cycle [2,1]) [1,5,2,8,4]
[(2,1),(1,5),(2,2),(1,8),(2,4)]

Первый элемент кортежа - это количество повторений второго элемента.

Вы можете использовать replicate для повторения любого значения несколько раз, но вам придется uncurry, чтобы принять один кортеж в качестве ввода:

Prelude> uncurry replicate (2,1)
[1,1]
Prelude> uncurry replicate (1,5)
[5]

Обратите внимание, что эта функция всегда возвращаетсписок, так что если вы сделаете это над списком кортежей, у вас будет список списков.Чтобы немедленно сгладить такой список, вы можете использовать монадное связывание для сглаживания проекции:

Prelude> zip (cycle [2,1]) [1,5,2,8,4] >>= uncurry replicate
[1,1,5,2,2,8,4,4]

Вы можете, если хотите, сделать из него функцию:

dup xs = zip (cycle [2,1]) xs >>= uncurry replicate

Эта функция оказывается параметрически полиморфной, поэтому, хотя вы можете использовать ее со списками целых чисел, вы также можете использовать ее со списками символов:

Prelude> dup [1,5,2,8,4]
[1,1,5,2,2,8,4,4]
Prelude> dup "acen"
"aaceen"

Answer 3

Возможно, вы захотите создать взаимно рекурсивный набор функций

duplicate, duplicate' :: [a] -> [a]
duplicate [] = []
duplicate (x:xs) =  x : x : duplicate' xs
duplicate' [] = []
duplicate' (x:xs) = x : duplicate xs

или добавить простой ADT для определения следующего действия

data N = O | T
duplicate = duplicate' T
duplicate' _ [] = []
duplicate' T (x:xs) = x : x : duplicate' O xs
duplicate' O (x:xs) = x : duplicate' T xs

Но, честно говоря, лучший способэто то, что предложил @Simon_Shine,

duplicate [] = []
duplicate (x:y:xs) = x : x : y : duplicate xs
duplicate (x:xs) = x : x : xs -- Here x is an even index and xs is an empty list