在Haskell中反转一个列表

Question

在Haskell中反转一个列表

23

我想要将一个列表反转。

以下是我的代码：

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

最终发生的是，我得到的列表顺序与原来相同。我甚至有一个解决方案来反转这个列表，但我想知道我在这里做错了什么？我对Haskell非常陌生，所以认为我应该更关注理解，然后才能更容易地解决问题。我知道有很多解决方案可以解决这个问题，但我需要更多的帮助来理解我在这段代码中做错了什么。

- user1010101

1

从这里可以学到的一课是，你可以做 1:[2,3,4] 但是你不能做 [2,3,4]:1。在这个数组构造指令中，最左边的项要求该项为元素而不是数组。这是Haskell在这种情况下的方式，也是新手像我非常重要的核心概念，需要内化并适应。 - daparic

7个回答

8

您正在将列表分成头和尾，但是在相同的顺序中重新组装列表。以列表[1, 2, 3]为例：

在第一次调用中，x将是1，xs将是[2, 3]。然后您创建一个新列表，由位于前面的x（即1）和后跟reverseList [2, 3]组成。

- Michael Kohl

我的错，抱歉。已经更正。 - Michael Kohl

我不是在做同样的事情吗？因为当我取出头部时，我会像x:reverseList xs一样先插入头部。 - user1010101

7

在Haskell中，有几种解决这个问题的方法。这里提供一个使用cons和last/init的解决方案：

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

或者使用foldl：

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

- Twistleton

2

你将这两种方法作为两个选择，但只有一种是高效的解决方案！你可能需要解释一下为什么。 - dfeuer

我点赞这个帖子，因为作为Haskell的新手，我使用last和init得到了相同的解决方案。它可能不是最有效的，但它加强了我对Haskell的理解。 - daparic

第二种选择实际上比第一种选择没有更高的效率。函数 foldl 在列表参数上是严格的，并对其进行递归。这意味着为了将其结果评估为弱头部正常形式，必须首先遍历整个列表。这很好，但是这种遍历会导致生成一个Thunk，其大小与列表的大小成比例，其评估可能导致堆栈溢出。这是因为 foldl 不在累加值上强制要求执行。可以使用 foldl' 强制Thunk为 WHNF，该值在累加值上是有结构的。 - justinpc

1

@justinpc，你有两个错误。你的主要错误是认为第二个和第一个一样糟糕。实际上，第二个需要线性时间，而第一个需要平方时间。如果你不相信我，请尝试使用一百万个元素进行测试，并使用reverse的每个实现打印last . rev $ [1..10^6]。如果你不明白为什么，我可以尝试解释一下。第二件事是，如果启用了优化，则GHC绝对不会为foldl实现构建任何多余的thunks。 - dfeuer

2

基本上，天真的算法使用附加。最初的回答。

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

由于添加操作是一个O(n)的操作，其中n是++运算符的第一个（左）参数的长度，因此效率低下。因此，上面的revList函数最终变成了O(n(n-1)/2) ~ O(n^2)。

因此，在这样的追加任务中，有差异列表数据类型。

差异列表只是一个表示为函数的列表。我的意思是，当用DList类型表示类似于[1,2,3]的列表时，它将是\xs -> [1,2,3] ++ xs或简写为([1,2,3] ++)。

Original Answer翻译成"最初的回答"

type DList a = [a] -> [a]

toDList :: [a] -> DList a
toDList xs  = (xs ++ )

fromDList :: DList a -> [a]
fromDList f = f []

这很酷，因为DLists是函数，我们可以通过组合（.）运算符附加它们并获得一个新的DList。换句话说，toDList (xs ++ ys) == (toDList xs) . (toDList ys)。

那么这有什么用呢？通过使用嵌套函数组合，我们可以以类似于revList函数的方式反转列表，但成本要少得多。只有O(n)，因为每个函数组合都是O(1)。

最初的回答：DLists是函数，可以通过组合运算符将它们附加到一起，形成新的DList。这种方法可以用于反转列表，并且成本较低，只需O(n)。

revList' :: [a] -> DList a
revList' []     = toDList []
revList' (x:xs) = revList' xs . toDList [x]

现在我们已经有了反转的[a]，在DList a类型中，我们只需要应用fromDList即可。"Original Answer"翻译成"最初的答案"。

fastReverse :: [a] -> [a]
fastReverse = fromDList . revList'

差异列表数据类型并不像我上面展示的那样简单。它可以有Monoid，Functor和MonadT实例。关于这个有用的数据类型的更多信息，请查看Data.DList。最初的回答。

- Redu

虽然不完全正确，但每个函数组合确实是O(1)，但我们对组合函数执行工作所需的时间有什么保证呢？完整答案在这里。 :) - Will Ness

2

简单。使用内置的reverse函数：

print (reverse [1,2,3,4,5]) -- [5,4,3,2,1]

- Sapphire_Brick

0

在 Haskell 中，reverse 函数是使用列表推导式定义的。

rev1::  [a] -> [a]
rev1 xs = [xs !! (length xs - a)  | (a,b) <- zip [1..] xs]

- ibrahim uğur Yılmaz

0

这个反转函数使用一个累加器和foldl。

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

这个使用递归。

reverse :: [a] -> [a]
reverse (x:xs) = reverse xs ++ [x]

- Gabe Itch

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bheklilr · Accepted Answer

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

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

然而，对于大型列表来说，这种方法将非常缓慢，因为Haskell列表实际上是单向链表，所以为了追加一个元素，你必须遍历整个列表。另一种替代方法是在辅助函数中跟踪正在构建的列表：

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

然而，这只是折叠模式：

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

但是 \acc x -> x : acc 只不过是 flip (:)，所以可以写成

reverseList = foldl (flip (:)) []

然而，最简单的方法可能只是使用Prelude中的reverse函数。

我想指出，你的reverseList :: [Int] -> [Int]类型可以推广为:: [a] -> [a]，因为你没有对列表的元素进行任何特殊处理，只是用它们构建了一个新的列表。