Haskell

Question

我仍然是 Haskell 的初学者。我尝试做一些模式匹配。我想重复 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 和 replicate，但我不应该使用这些函数。我的想法是使用 elemIndex 并将其用作 my "n" 并在 "n" 和递归之后使用复制或类似的东西。我在模式匹配中需要类似的东西。但我认为，我想得太复杂了。有没有人有想法？

Answer 1

Haskell 的很大一部分是将事情分解成更小的问题。因此，让我们分解您的问题。

您需要能够做的一件事是重复一个元素。正如您已经发现的那样，此功能以 replicate 函数的形式存在于 Haskell 中。但是您可以自己轻松实现它。

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

如果我们重复某件事零次，return 空列表。否则，将元素放在最前面并递归。

现在我们可以重复了。让我们编写一个函数来跟踪我们的列表位置。它看起来像这样。

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

它将取一个整数（当前位置）和列表的尾部，return 给定列表的特定部分的结果。和以前一样，我们将遇到两种情况：一种是列表为空，另一种不是。第一种情况很简单；如果列表为空，return 为空列表。如果列表不为空，则重复第一个元素，然后递归。

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

++ 是一个连接两个列表的内置函数。如果您真的愿意，也可以自己实施。现在，首先，我们将第一个元素视为元素 1，因为我们想重复它一次，所以我们将通过将 1 传递给 testImpl.[=19= 来开始递归]

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'：一个列表l和一个索引i，我们定义它如下：

如果列表为空，我们return一个空列表；和
如果列表不为空，我们产生列表的头部 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 3

救援列表理解：

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

当然，除非您将 zip 算在 "prebuilt-list-functions" 中，您很可能会这样。

Answer 4

不用任何数字也可以做到这一点。让我们一起努力吧。我们将使用累加器方法，但不是在累加器中保留 number，而是保留一个 function 重复其参数次数。

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

这确实不是解决问题的高效方法，但它是一种相当简约的方法。

Answer 5

枚举可以生成给定基数的序数。索引是序数。这意味着列表 a 中的数字是枚举中的结束数字。每个索引集（基数集从ordinals）是[0..index]第一个，实际上零是[0..1]。如果我们想要我们的序数，它将是 [1..1]，然后是 [1..2] 和 [1..3] 但是该函数出于习惯使用零索引并且必须减少基数。

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

枚举参数很好玩。枚举可以用作任何类型的其他列表的索引参数。枚举可以为其他函数和其他枚举提供参数。

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

Haskell - repeat elements of a list according to their list-index

list

replicate