Haskell - 根据列表索引重复列表元素

Question

我是一名Haskell初学者，尝试进行一些模式匹配。我想将列表中的每个元素重复n次。n由列表中每个元素的索引位置决定。

例如['1'，'2'，'3']应该给我：['1'，'2'，'2'，'3'，'3'，'3']。这是一个练习题，我不应该使用预先构建的列表函数。

我尝试了以下代码：

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

但是它只是将第一个元素之后的每个元素加倍。我考虑过elemIndex和replicate，但我不应该使用这些函数。我的想法是使用elemIndex，并将其作为我的“n”，然后再使用replicate或类似的函数，并结合“n”和递归来实现。我需要像模式匹配一样的东西。但我认为，我想得太复杂了。有没有人有思路？

- Pal

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

- Silvio Mayolo

Answer 2

列表推导式来拯救:

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

除非您将zip视为“预构建列表函数”之一，否则您可能不会计算它。

- Will Ness

---

你也可以实现 zip。 - 4castle

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"

- Willem Van Onsem

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

我们从使用rep1这个非常简单的函数开始调用go，它将其参数转换为一个单例列表。然后在每次递归调用中，我们通过使重复器函数重复其参数一次来修改重复器函数。 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

这真的不是解决问题的一种高效方式，但它是一种相当极简主义的方法。

- dfeuer

---

@WillNess，这里的表述让我有点困难。如果您认为您可以做得更好，请随意编辑。此外，对于自己，我会使用 RankNTypes 更好地解释发生了什么，但是原帖的作者可能会感到非常迷茫。 - dfeuer

@WillNess，我不确定那真的有帮助；我个人觉得它很混乱和难懂。经过更多思考，我认为开始的方法是使用oneMore0和++的test版本，然后展示如何消除后者。除非你先完成了它，否则我会尝试稍后解决它。 - dfeuer

顺便提一下，将数据结构进行轻松追踪作为起点是 Sterling 和 Shapiro 的旧版 Prolog 书籍中的一种技术。他们称之为“程序骨架”。 - Will Ness

@WillNess，我撤销了你的更改，因为我无法弄清楚如何将其集成到我决定想要的结构中。但是，如果您能更好地激发您的技巧，我认为您应该编写自己的答案。感谢您促使我改进我的解释。 - dfeuer

当然，这是一种非常不同的方法。关于导出，这是一个好的起点！还可以说 rep a ++ go (oneMore rep) as = ((++).rep) a (go ...) 这实际上迫使我们给出融合的 rep1' = (++).rep1 定义，以及相应更改的 oneMore' rep1' a as = ...，它必须与 rep1' 相同的类型，这又实际上是自己编写的。只是说 "需要一些调整" 并没有解释得很清楚。这只是一个想法。 - Will Ness

Answer 5

枚举可以根据基数产生序数。索引是序数。这意味着列表a中的数字是枚举的结束数字。每个索引集（从序数得到基数）是[0...索引]，实际上零是[0...1]。如果我们想使用序数，它将是[1..1]，然后是[1..2]和[1..3]，但函数习惯性地使用零索引，基数必须减少。

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

枚举参数非常有趣。枚举可用作其他任何类型的列表的索引参数。枚举可以为其他函数和其他枚举提供参数。

- fp_mora