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" и использовать replicate или что-то подобное после этого с "n" и рекурсией. Мне нужно что-то подобное в сопоставлении с образцом. Но я думаю, что я думаю слишком сложно. Есть ли у кого-нибудь идея?

Answer 1

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

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

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

Answer 2

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

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 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

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

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

Если, конечно, вы не считаете zip "готовыми списочными функциями", что вы вполне могли бы сделать.

Answer 5

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