haskell - Haskell 反向函数

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 reverseing a list和How can I write reverse by foldr Effective 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

我们准备好了。:) 即，对于 call rev a b， reversed 的串联a并b保留在从 head 元素中获取a并将其添加到的转换下b，直到 a为空，然后为b。这甚至可以用英文描述之后的高阶函数来表达，如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)