Haskell reverse function

Question

Очень новый для Haskell и пытается создать мою собственную функцию обратного хода. Написал это здесь, но он всегда возвращает пустой список []:

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

Может ли кто-нибудь объяснить, что я делаю неправильно?

Благодаря

Answer 1

Как groovy упоминалось, диапазоны Haskell в основном инкрементальный - то есть, она не имеет ни малейшего представления, как построить убывающую список, если не дать ему какой-то намек. Посмотрите на GHCI сессии ниже:

Prelude> [5..0] 
[] 
Prelude> [5,4..0] 
[5,4,3,2,1,0] 

Таким образом, вы можете построить что-то вроде этого:

foo xs = [(length xs-1), (length xs -2)..0] 
rev xs = [xs !! k| k <- foo xs] 

, который проверяет в GHCI так:

Prelude> rev [1..5] 
[5,4,3,2,1] 

взглянуть на Unexpected result while reversing a list и How can I write reverse by foldr efficiently in Haskell? для других идей по перестановке списка.

Answer 2

часто помогает изобретать некоторый инвариант и записывать для него некоторые законы сохранения. Здесь обратите внимание, что

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, конкатенаций реверсивного a и b сохраняются при преобразовании с головным элементом из a и не предваряя его b, доa пусты, а затем это просто b. Это может даже быть выражено с использованием higher-order function until после описания английского как

{-# 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 

Answer 3

Это моя форма, чтобы создать свою собственную функцию реверса с рекурсией. эта функция очень удобна для определения вспомогательных функций.

list = [] reverse [x] = list ++ [x] reverse = list ++ [last l] ++ reverse (init l)