Haskell - повторять элементы списка в соответствии с их индексом списка

Большая часть Haskell разбивает вещи на более мелкие задачи. Итак, давайте разберем вашу проблему.

Одна из вещей, которую вам нужно уметь делать, это повторять элемент. Как вы уже поняли, эта функциональность существует в Haskell в виде функции replicate. Но вы можете реализовать это самостоятельно так же легко.

repeatNTimes :: Int -> a -> [a]
repeatNTimes 0 _ = []
repeatNTimes n x = x : repeatNTimes (n - 1) x

Если мы повторяем что-то ноль раз, возвращаем пустой список. В противном случае поместите элемент впереди и рекурсивно.

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

testImpl :: Int -> [a] -> [a]

Он возьмет целое число (текущую позицию) и конец списка и вернет результат с учетом этой конкретной части списка. Как и раньше, у нас будет два случая: один, когда список пуст, и другой, когда его нет. Первый случай прост; если список пуст, вернуть пустой список. Если список непуст, повторите первый элемент, а затем рекурсивно.

testImpl :: Int -> [a] -> [a]
testImpl _ [] = []
testImpl n (x:xs) = repeatNTimes n x ++ testImpl (n + 1) xs

++ — это встроенная функция, которая объединяет два списка. Вы также можете реализовать это самостоятельно, если действительно хотите. Теперь, для начала, мы считаем первый элемент элементом 1, так как мы хотим повторить его один раз, поэтому мы начнем рекурсию, передав 1 в testImpl.

test :: [a] -> [a]
test = testImpl 1

Полный пример:

repeatNTimes :: Int -> a -> [a]
repeatNTimes 0 _ = []
repeatNTimes n x = x : repeatNTimes (n - 1) x

testImpl :: Int -> [a] -> [a]
testImpl _ [] = []
testImpl n (x:xs) = repeatNTimes n x ++ testImpl (n + 1) xs

test :: [a] -> [a]
test = testImpl 1

Список понятий на помощь:

test xs = [x | (i,x) <- zip [1..] xs, _ <- [1..i]]

Если, конечно, вы не считаете zip среди "предустановленных функций-списков", что вполне возможно.

В этом случае мы обычно используем аккумулятор. Аккумулятор — это дополнительный параметр, который мы передаем (и обновляем) для достижения нашей цели. Таким образом, мы можем реализовать функцию test' с двумя параметрами: списком l и индексом i, и мы определяем ее следующим образом:

1. если список пуст, мы возвращаем пустой список; и
2. в случае, если список не пуст, мы возвращаем начало списка i раз и рекурсивно используем конец списка и увеличенное i.

Мы можем реализовать это так:

test' :: Int -> [a] -> [a]
test' _ [] = []
test' i (x:xs) = rep i
    where rep j | j > 0 = x : rep (j-1)
                | otherwise = test' (i+1) xs

Итак, теперь нам нужно только определить test с точки зрения test', здесь мы можем сказать, что test со списком l совпадает с test' с этим списком, а 1 в качестве начального индекса:

test :: [a] -> [a]
test = test' 1
    where test' _ [] = []
          test' i (x:xs) = rep i
              where rep j | j > 0 = x : rep (j-1)
                          | otherwise = test' (i+1) xs

Затем мы получаем результаты теста, такие как:

Prelude> test ['1'..'3']
"122333"
Prelude> test [1..3]
[1,2,2,3,3,3]
Prelude> test [1, 4, 2, 5]
[1,4,4,2,2,2,5,5,5,5]
Prelude> test "ia2b"
"iaa222bbbb"

Вы можете сделать это без каких-либо номеров. Давайте работать наш путь к нему. Мы будем использовать накопительный подход, но вместо того, чтобы хранить число в аккумуляторе, мы сохраним функцию, которая повторяет свой аргумент определенное количество раз.

test0 :: [a] -> [a]
test0 xs = go rep1 xs
  where
    rep1 :: a -> [a]
    rep1 a = [a]

    go :: (a -> [a]) -> [a] -> [a]
    go _rep [] = []
    go rep (a : as) = rep a ++ go (oneMore rep) as

    oneMore :: (a -> [a]) -> (a -> [a])
    oneMore rep a = a : rep a

Мы начинаем с вызова go с rep1, очень простой функции, которая превращает свой аргумент в одноэлементный список. Затем при каждом рекурсивном вызове мы модифицируем функцию повторителя, заставляя ее повторять свой аргумент еще раз.

test0 прекрасно работает, но использует функцию ++, и вы не должны использовать какие-либо предопределенные функции. Использование ++ здесь также означает, что вам нужно создавать небольшие списки и соединять их вместе, неэффективность, которую мы можем довольно легко устранить.

Обратите внимание, что каждый раз, когда go вызывает rep, он немедленно добавляет к результату что-то еще. Это предлагает решение: вместо того, чтобы rep брать элемент и создавать список, давайте возьмем элемент и список и создадим список, состоящий из элемента, повторяющегося определенное количество раз, за ​​которым следует заданный список! Так что у нас будет

rep1 "a" ["b", "c"] = ["a", "b", "c"]
rep2 "a" ["b", "c"] = ["a", "a", "b", "c"]

где rep1 и rep2 — первые две функции rep. Требуется всего несколько корректировок.

test :: [a] -> [a]
test = go rep1
  where
    rep1 :: a -> [a] -> [a]
    rep1 a as = a : as  -- Note: rep1 can be written as just (:)

    go :: (a -> [a] -> [a]) -> [a] -> [a]
    go _ [] = []
    go rep (a : as) = rep a (go (oneMore rep) as)

    oneMore :: (a -> [a] -> [a])
            -> a -> [a] -> [a]
    oneMore f a as = a : f a as

На самом деле это не эффективный способ решения проблемы, но это скорее минималистский подход.

Перечисления могут производить порядковые числа по заданному кардинальному числу. Индексы - это порядковые числа. Это означает, что цифра в списке a является конечным числом в перечислении. Каждый набор индексов (набор количественных чисел из порядковых) равен [0..index] первому, фактически ноль равен [0..1]. Если бы мы хотели использовать порядковые номера, это было бы [1..1], затем [1..2] и [1..3]. Но функция использует нулевой индекс по привычке, и кардинальное число должно быть декриментировано.

[b|b<-[1,2,3], a<-[0..b-1]]

Параметры перечисления очень забавны. Перечисления можно использовать в качестве индексных параметров для других списков любого типа. Перечисления могут предоставлять параметры другим функциям и другим перечислениям.