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

如何在Haskell中编写powerList函数？我希望用n乘法运算构建这样一个列表，其中每个元素是前一个元素的简单倍数，而不是指数操作的n。在Haskell中计算`[1，x^1，x^2，...，x^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 = [] -- ???

来源

2016-09-17 clay

对于一个列表，其中每个元素是以前的元件的功能，你可以使用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)

来源

2016-09-17 03:55:58

太棒了！谢谢！将在计时器允许时接受。 – clay

Haskell奇妙地允许无限形式[0,1 ..]所以你可以（\ kx-> map（k ^）$ take（x + 1）[0,1 ..]）2 4 它产生[1 ，2,4,8,16] 此外，我不明白为什么要求4值应该产生5.（X + 1）应该是X和结果[1,2,4,8] – fpmora

但是，而不是使用take来限制无限生成器，直接使用n .... （\ kn - > map（k ^）[0..n]）2 4但是这会产生5个值[1,2,4,8， 16] – fpmora

克里斯的回答很可能是你要找的。

如果您希望在不使用迭代的情况下执行此操作，则可以使用以下代码。

编辑：为了避免附加到列表尾部（需要线性时间），可以使用辅助函数powerList'首先反向计算列表，然后反转该函数的输出以纠正顺序。

powerList' :: Integral a => a -> a -> [a] 
powerList' _ 0 = [1] 
powerList' x n = do { let l = go x (n - 1) 
        ; [x * (head l)] ++ l 
        } 
powerList :: Integral a => a -> a -> [a] 
powerList x n = reverse (powerList' x n)

来源

2016-09-17 04:08:15

这里的运行时间在'n'中是二次的;追加到列表的末尾是线性的，所以通常应该避免。 –

好的一点，这只是我的第一个关于实现没有迭代的想法。我猜想另一种选择是创建头部最大元素的列表，并在完成时将其逆转。 –

你也不需要反转 - 请参阅我的编辑:) –

列表解析通常是生成器的简写。发电机用于其他功能用于多种目的。列表理解通常简洁到足以包含函数中的内联。以下是你的powerList函数的列表理解版本。它简单地命名为p。我很懒。结果中的两个值分别是每个值的笛卡尔乘积。常量也是第一个参数只需要一次。去搞清楚。

Prelude> p i j = [(k^n) | k <- [i], n <- [0..j]] 
Prelude> p 2 16 
[1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536]

大声笑一个显而易见的事实，i或k是一个常数和一个参数，随时可以使用。

p i j = [(i^n) | n <- [0..j] ]

我觉得Haskell最引人注目的是像上面这些函数是规范而不是指令。许多Haskell函数告诉计算机什么是想要的，而不是做什么来获得它，也就是说，这是非常明确的，这是一种语言最想要的。

来源

2018-02-01 16:47:03 fpmora

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

回答

相关问题