通过从模式列表中添加整数来生成 Haskell 中的整数列表

Question

我在玩 Haskell，主要是想学习一些解决问题的新技术。在没有任何实际应用的情况下，我想到了一件有趣的事情，但我找不到令人满意的解决方案。也许有人有更好的主意？

问题：

假设我们要使用起始值和整数列表生成一个整数列表，表示要按指定顺序添加的数字模式。所以第一个值给出，那么第二个值应该是起始值加上列表中的第一个值，第三个 that 值加上模式的第二个值，依此类推。当模式结束时，它应该重新开始。

例如：假设我们有一个起始值 v 和一个模式 [x,y]，我们想要列表 [v,v+x,v+x+y,v+2x+y,v+2x+2y, ...]。换句话说，对于双值模式，下一个值是通过将 x 和 y 交替添加到上次计算的数字来创建的。

如果模式足够短（2-3 个值？），可以生成单独的列表：

[v,v,v,...]
[0,x,x,2x,2x,3x, ...]
[0,0,y,y,2y,2y,...]

然后通过加法将它们压缩在一起。然而，一旦模式变长，这就会变得非常乏味。我最好的解决方案尝试是这样的：

generateLstByPattern :: Int -> [Int] -> [Int]
generateLstByPattern v pattern = v : (recGen v pattern)
  where
  recGen :: Int -> [Int] -> [Int]
  recGen lastN (x:[]) = (lastN + x) : (recGen (lastN + x) pattern)
  recGen lastN (x:xs) = (lastN + x) : (recGen (lastN + x) xs)

它按预期工作 - 但我感觉在某处有更优雅的 Haskell 解决方案（几乎总是如此！）。你怎么看？也许是一个很酷的列表理解？我忘记的高阶函数？

Answer 1

分离关注点。首先看一个只处理一次的列表。让它工作，测试它。提示：“用一些累加器遍历列表元素”通常很适合折叠。

然后剩下的就是重复输入列表并将其输入一次传递函数。方便的是，有 a standard function 用于此目的。只需确保您的一次处理器足够懒惰以处理无限列表输入。

Answer 2

单独实现列表可能更好，例如 x 的列表可以用：

实现

xseq :: (Enum a, Num a) => a -> [a]
xseq x = 0 : ([x, x+x ..] >>= replicate 2)

而 y 的序列可以实现为：

yseq :: (Enum a, Num a) => a -> [a]
yseq y = [0,y ..] >>= replicate 2

然后你可以用zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]把两个列表加在一起，加上v:

mylist :: (Enum a, Num a) => a -> a -> a -> [a]
mylist v x y = zipWith ((+) . (v +)) (xseq x) (yseq y)

因此对于 v = 1、x = 2 和 y = 3，我们得到：

Prelude> take 10 (mylist 1 2 3)
[1,3,6,8,11,13,16,18,21,23]

另一种方法是将我们每次先添加 x 然后添加 y 作为模式。因此，我们可以创建一个无限列表 [(x+), (y+)]，并使用 scanl :: (b -> a -> b) -> b -> [a] -> [b] 每次应用其中一个函数并产生中间结果：

mylist :: Num a => a -> a -> a -> [a]
mylist v x y = scanl (<b>flip ($)</b>) v (cycle [(x+), (y+)])

这会产生相同的结果：

Prelude> take 10 $ mylist 1 2 3
[1,3,6,8,11,13,16,18,21,23]

现在唯一要做的就是将其概括为列表。因此，例如，如果给出了添加列表，那么您可以将其实现为：

mylist :: Num a => [a] -> [a]
mylist v <b>xs</b> = scanl (<b>flip ($)</b>) v (cycle (<b>map (+) xs</b>))

或函数列表：

mylist :: Num a => [a -> a] -> [a]
mylist v <b>xs</b> = scanl (<b>flip ($)</b>) v (cycle (<b>xs</b>))

Answer 3

关于生成系列，我的第一个方法是 iterate or unfoldr。 iterate 用于简单系列，unfoldr 用于那些携带某种状态但不使用任何 State monad 的人。

在这种特殊情况下，我认为 unfoldr 是理想的。

series :: Int -> [Int] -> [Int]
series s [x,y] = unfoldr (\(f,s) -> Just (f*x + s*y, (s+1,f))) (s,0)

λ> take 10 $ series 1 [1,1]
[1,2,3,4,5,6,7,8,9,10]

λ> take 10 $ series 3 [1,1]
[3,4,5,6,7,8,9,10,11,12]

λ> take 10 $ series 0 [1,2]
[0,1,3,4,6,7,9,10,12,13]

Answer 4

你描述的是

foo :: Num a => a -> [a] -> [a]
foo v pattern = scanl (+) v (cycle pattern)

通常会写成

foo :: Num a => a -> [a] -> [a]
foo v = scanl (+) v . cycle

scanl (+) v xs 是计算 (v:xs) 的 部分和 的标准方法，而 cycle 是重复给定的标准方法循环列出。这是你所描述的。

这适用于任何正长度的模式列表，如您所愿。

您生成它的方法很有创意，但它几乎太聪明了（即看起来过于复杂）。它可以用一些列表理解来表达，如

foo v pat =
   let   -- the lists, as you describe them:
       lists = repeat v :
               [ replicate i 0 ++
                 [ y | x <- [p, p+p ..]
                     , y <- map (const x) pat ]
                 | (p,i) <- zip pat [1..] ]
   in
     -- OK, so what do we do with that? How do we zipWith
     --   over an arbitrary amount of lists?
     --   with a fold!
     foldr (zipWith (+)) (repeat 0) lists

map (const x) pat是"clever"的一种写法replicate (length pat) x。根据定义，它可以进一步缩短为 x <$ pat，因为 (<$) x xs == map (const x) xs。它可能看起来很模糊，直到您习惯了它，然后它才显得清晰明了。 :)

Answer 5

奇怪的是居然还没有人提到这种愚蠢的方式。

mylist x xs = x : zipWith (+) (mylist x xs) (cycle xs)

（如果你眯着眼睛，你可以看到与 scanl 答案的联系）。

通过从模式列表中添加整数来生成 Haskell 中的整数列表

Generate list of Ints in Haskell by adding Ints from a pattern list

haskell

sum

list

cycle

infinite