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

Question

Я все еще новичок в Хаскеле. Я пытаюсь сделать сопоставление с образцом. Я хочу повторить каждый элемент списка n раз. N определяется индексом каждого элемента в списке. Например ['1', '2', '3'] должен дать мне: ['1', '2', '2', '3', '3', '3'], Это упражнение, и я не должен использовать prebuild-list-functions.

Я попробовал что-то подобное:

test [] = []
test (first:[]) = [first] 
test (first:second:rest) = first : second : test (second:rest)

Но он просто удваивал каждый элемент после первого. Я думал об elemIndex и его репликации, но я не должен использовать эти функции. Моя идея состояла в том, чтобы использовать elemIndex и использовать его в качестве my "n" и использовать репликацию или что-то подобное после этого с "n" и рекурсией. Мне нужно что-то подобное в сопоставлении с шаблоном. Но я думаю, что я думаю слишком сложно. Есть ли у кого-нибудь идея?

Answer 1

Большая часть 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

Answer 2

Список понятий для спасения:

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

Если конечно вы не считаете zip среди "prebuilt-list-functions", что вы вполне могли бы.

Answer 3

В этом случае мы обычно используем аккумулятор. Аккумулятор - это дополнительный параметр, который мы передаем (и обновляем) для достижения нашей цели. Таким образом, мы можем реализовать функцию 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"

Answer 4

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

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

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

Answer 5

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

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

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