haskell - Haskell リバース関数

Question

Haskell は初めてで、独自の逆関数を作成しようとしています。これをここに書きましたが、常に空のリスト [] を返します:

reverse' :: [a] -> [a]
reverse' xs = [xs !! k | k <- [((length xs) - 1)..0]]

誰かが私が間違っていることを説明できますか?

ありがとう

Answer 1

多くの場合、いくつかの不変条件を発明し、それに対するいくつかの保存法則を書き留めておくと役立ちます。ここで、

reverse xs     = reverse xs ++ []
reverse (x:xs) = (reverse xs ++ [x]) ++ []
               = reverse xs ++ ([x] ++ [])
               = reverse xs ++ (x:[])
reverse (x:(y:xs)) =
               = reverse (y:xs) ++ (x:[])
               = reverse xs ++ (y:x:[])
......
reverse (x:(y:...:(z:[])...)) =
               = reverse [] ++ (z:...:y:x:[])

したがって、定義すると

reverse xs = rev xs []  where
  rev (x:xs) acc = rev xs (x:acc)
  rev []     acc = acc

私たちは設定されています。:) つまり、呼び出しrev a bの場合、 reversed の連結は、aからhead要素を取得し、それを先頭に追加するbという変換の下で保持されます。これは、英語の説明に従って高階関数を使用して表現することもできます。ab abuntil

{-# LANGUAGE TupleSections #-}
reverse = snd . until (null.fst) (\(a,b)-> (tail a,head a:b)) . (, []) 

また、関数などを定義することもできますrevappend。まったく同じ内部関数を使用して、呼び出し方を少し調整します。

revappend xs ys = rev xs ys  where
  rev (x:xs) acc = rev xs (x:acc)
  rev []     acc = acc