在Haskell中计算`[1,x ^ 1,x ^ 2,...,x ^ n]`

Question

如何powerList在Haskell中编写函数,如下所示？我希望它使用n乘法运算来构建这样的列表,其中每个元素是前一个元素的简单倍数,而不是n指数运算.

理想情况下,实现是干净的,惯用的Haskell,并且相当有效.

-- powerList x n -> [1, x, x^2, ..., x^n]
-- For example:
-- powerList 2 0 -> [1]
-- powerList 2 1 -> [1, 2]
-- powerList 2 2 -> [1, 2, 4]
-- powerList 2 3 -> [1, 2, 4, 8]
-- powerList 2 4 -> [1, 2, 4, 8, 16]
powerList :: forall a. Integral a => a -> a -> [a]
powerList _ 0 = [1]
powerList x n = [] -- ??? 

Answer 1

对于每个元素都是前一个元素的函数的列表,您可以使用iterate:

iterate :: (a -> a) -> a -> [a]

iterate f x返回的重复应用的无限名单f到x:

iterate f x == [x, f x, f (f x), ...]

Prelude> powerList x n = take (n + 1) $ iterate (* x) 1
Prelude> powerList 2 0
[1]
Prelude> powerList 2 4
[1,2,4,8,16]

如果你不想使用iterate或take练习,我首先要看看如何iterate实现:

iterate f i = i : iterate f (f i)

要做类似的事情,我们的递归函数将需要一个额外的参数i.在编写递归函数时,这是一种非常常见的技术.

-- powerList x n = [ 1, x, x^2, ..., x^n ]
powerList x n = powerList' n 1
  where
    -- powerList' n i = [ i, i*x, i*x^2, ..., i*x^n ]
    powerList' 0 i = [ i ]
    powerList' n i = i : powerList' (n - 1) (i * x)