ハスケルで逆関数を書くには

Question

ハスケルのリストを逆にする関数が組み込まれていますが、ハスケルを練習するために自分の小さな関数を書こうとしています。私は悲しいかなか働いていない次のコードを考えました。あなたは私が間違っていたことを教えてもらえますか？

rev :: [Int] -> [Int] 
    rev [] = [] 
    rev [x] = last [x] : rev init [x] 

Answer 1

あなたはほとんどそれを持っていました。

rev :: [Int] -> [Int] 
rev [] = [] 
rev x = last x : rev (init x) 

説明：あなたはX

PSを直接操作したいのに対し、[X]は、Xを含むリストでした。ここにはdocumentation for Data.Listがあります。そしてimport Data.List

Answer 2

ウェルに覚えて、あなたはこのような何かを行うことができます：

rev :: [Int] -> [Int] 
rev [] = [] 
rev (x:l) = (rev l) ++ [x] 

3行目は、リストから最初の要素を取り、その後にのみ、その要素を含むリストを作成します。これは再帰呼び出しrev l呼び出しの結果に追加されます。

Answer 3

あなたが効率的にそれをしたい場合は、私はあなたがアキュムレータを使用することをお勧めしたい：

rev :: [a] -> [a] 
rev xs = go xs [] 
    where 
    go :: [a] -> [a] -> [a] 
    go []  ys = ys 
    go (x:xs) ys = go xs (x:ys) 

機能goは、各ステップで、最初のリストxsから一つの要素を削除し、第二に、それを付加しますリストysこれは、スタックからポップし、別のスタックにプッシュすることに似ています。これは、順序を逆転させます。

各再帰呼び出しで一定の時間しか使用しないため、O（n）の複雑さが得られます（nはリストの長さです）。

代わりに、それぞれの再帰呼び出しでlastを使用するか、... ++ [x]を追加すると、各呼び出しにO（n）、したがって全体としてO（n^2）が支払われます。