Haskell再帰関数はリストの末尾に追加します

Question

私は数nをとり、1からnまでの2乗の長さのリストを生成する再帰的Haskell関数を持っています。

コードは動作しますが、n = 3のリストの代わりに[9,4,1]です。[1,4,9]にしたいと思います。

私はswappig the：を試しましたが、++ではforパターンマッチングは機能しません。私はちょうど今ハスケルを開始したので、明白かもしれません。

Answer 1

sqNListを実装するのが最も良い方法は、1からnまで数えられるヘルパー関数です。そうすれば、リストを正しい順序で生成することができます。

sqNList :: Int -> [Int] 
sqNList n = sqNListHelper 1 n 

sqNListHelper :: Int -> Int -> [Int] 
sqNListHelper current end = ... 

は、より洗練されたアプローチの多種多様ありますが、これはまた、あなたがすべてのものを自分で行う方法を考え出すている対話的にデバッグ/テストに最も簡単な方法です。

より洗練されたアプローチには、リストの補完またはmapやenumFromToのような作成関数を使用して、より単純なロジックを構築することができます。

Answer 2

おそらく最小メモリ量を消費する最も簡単な方法は、アキュムレータ（すべての再帰呼び出しで渡したパラメータ）を使用することです。

今あなたがアキュムレータとしてNを使用して、我々はアキュムレータを使用することを決定することができますが、デクリメント、私は代わり1から始まり、をインクリメントを保持します：

今

helper :: Int -> Int -> [Int] 
helper i n | i > n = [] 
      | otherwise = i*i : helper (i+1) n

私たちは当然それをi = 1と呼ぶ必要がありますが、これは理想的ではありませんが、helperをsqNListに入れてwhereという句を使用することができます：

sqNList :: Int -> [Int] 
sqNList n = helper 1 n 
    where helper :: Int -> Int -> [Int] 
      helper i n | i > n = [] 
        | otherwise = i*i : helper (i+1) n

これを少し改善することができます。 instancのために、それは変化しないため、helperコールを介しnに合格する必要がない、そしてトップレベルで定義されています

sqNList :: Int -> [Int] 
sqNList n = helper 1 
    where helper :: Int -> [Int] 
      helper i | i > n = [] 
        | otherwise = i*i : helper (i+1)

のみInt秒で動作する必要がさらにありません：我々は使用することができますいずれのタイプNum aとOrd aためa：

sqNList :: (Num a, Ord a) => a -> [a] 
sqNList n = helper 1 
    where helper i | i > n = [] 
        | otherwise = i*i : helper (i+1)

Answer 3

は、これは、より高度な技術であるので、あなただけの今後の研究のためにこれを保存することもできます。

---

ほとんどの再帰関数は再帰の同じ一般的な形式のいずれかを使用する傾向があるので、使用する高次の機能を知ることは、あなたに（おそらく間違って）再帰を再実装の手間を節約し、あなたがに焦点を当てることができますあなたの問題に固有の仕事。

Data.Listで定義されているunfoldr関数によって捕捉されます。これにより、ジェネレータ関数と初期シード値を使用して（おそらく無限の）リストを生成できます。

実際の定義は、効率のために少し複雑ですが、その定義は

unfoldr f x = case f x of 
        Nothing -> [] 
        Just (new, next) = new : unfoldr f next 

ような単純なことができます。

基本的には、シード値xで発電機fを呼び出すだけです。結果がNothingの場合は、空のリストを返します。それ以外の場合は、結果と新しいシード値を持つ再帰呼び出しによって生成されたリストを含むリストを作成します。

これを問題に適用すると、入力がまだ十分小さい限り、次の整数が生成されます。コールgenerator 1

1. とバックJust (1, 2)を得る;：

   import Data.List (unfoldr) 
   sqNList n = unfoldr generator 1 
         where generator x = if x > n then Nothing else Just (x*x, x+1) 
   

   は、次のようにsqNList 3のような単純な例のために、それが進行しますアキュムレータは現在[1]です。

2. generator 2に電話してJust (4, 3)に電話してください。アキュムレータは現在 [1,4]です。
3. generator 3に電話してJust (9, 4)に電話してください。アキュムレータは今や[1,4,9]です。
4. generator 4に電話してNothingに電話してください。結果としてアキュムレータ[1,4,9]を返します。あなたはすべての正方形単に決してNothingを返さないことでの無限のリストを生成

---

注：あなたがそれらを必要と

allSquares = unfoldr (\x -> Just (x*x, x+1)) 1 

Haskellは、怠けている、唯一、リスト内の要素を生成し、無限リストの最初のn項目のみを取ってsqNListと定義することもできます。

sqNList n = take n (unfoldr (\x -> Just (x*x, x+1)) 1)