Haskellで `[1、x^1、x^2、...、x^n]`を計算する

Question

HaskellでpowerList関数を以下のように書くことができますか？ 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 xfxへの繰り返しのアプリケーションの無限のリストを返します。

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) 

Answer 2

あなたが探しているのは、おそらくクリスの答えです。

iterateを使用せずに実行したい場合は、次のコードを使用できます。

編集：リニア時間を要するリストの末尾に追加することを避けるために、補助機能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) 

Answer 3

リスト内包表記は、しばしばジェネレータの略語です。ジェネレータは、多くの目的で他の関数で使用されます。リスト内包表記は、しばしば関数内でインラインに含めるのに十分なほど簡潔です。以下は、あなたのpowerList関数のリスト理解版です。それは単にpという名前です。私は怠け者。 結果の2つの値はそれぞれのデカルト積である。最初のパラメーターでもある定数は、1回だけ必要です。 Go figure。

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] 

LOL目立たない事実では、iまたはkは定数であり、パラメータはすぐに使用できます。私はHaskellのについて最も顕著見つける何

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

は、上記のような機能は仕様ではなくディレクティブであるということです。多くのHaskell関数は、コンピュータに、何をするのかを決める代わりに何が求められているのかを伝えます。つまり、言語で最も必要とされるものが大きく宣言的です。