在haskell中反转列表

Question

我试图扭转一个列表.

以下是我的代码:

reverseList :: [Int] -> [Int]
reverseList [] = []
reverseList (x:xs) =  x:reverseList xs

最终发生的事情是我最终以相同的顺序返回列表.我甚至有一个如何扭转列表的解决方案,但我想知道我在这里做错了什么？我对haskell很新,所以我认为我应该专注于理解更多,然后我可以轻松解决更多问题.我知道有很多解决方案可以解决这个问题,但我需要更多的帮助来理解我在这段代码中做错了什么.

Answer 1

在Haskell中有几种方法可以解决这个问题.天真的方法是使用连接函数++:

reverseList [] = []
reverseList (x:xs) = reverseList xs ++ [x]

但是,对于大型列表来说这将非常慢,因为Haskell列表实际上是单链表,因此为了附加元素,您必须遍历整个列表.另一种方法是跟上你在辅助函数中构建的列表:

reverseList = go []
    where
        go acc [] = acc
        go acc (x:xs) = go (x:acc) xs

但是,这只是fold模式:

reverseList = foldl (\acc x -> x : acc) []

但\acc x -> x : acc就是flip (:)这样,所以这可以写成

reverseList = foldl (flip (:)) []

但是,最简单的方法可能就是reverse在Prelude中使用该函数.

我想指出你的类型reverseList :: [Int] -> [Int]可以推广到:: [a] -> [a],你没有对列表的元素做任何特殊的事情,你只是用它们建立一个新的列表.

Answer 2

在 Haskell 中有几种方法可以解决这个问题。这是一个带有缺点和最后/初始化的解决方案：

reverseList  [] = []
reverseList  xs = last xs : reverseList (init xs)

或者使用 foldl：

reverseList xs = foldl (\x y -> y:x) [] xs 

Answer 3

您将列表分为头和尾，然后以相同顺序重新组装列表。以列表[1, 2, 3]为例：

在第一个通话中，x将是1和xs将是[2, 3]。然后，创建一个新列表，该列表由x前面的（so 1）组成，后跟reverseList [2, 3]。