在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]`

回答

相關問題