遍历列表并在 Haskell 中的堆栈上执行操作

Question

我在自学Haskell。我有以下使用列表实现堆栈的代码：

push :: Int -> [Int] -> [Int]
push x [] = [x]
push x xs = xs ++ [x]

pop :: [Int] -> [Int]
pop [] = error "Cannot pop from an empty list!"
pop xs = init xs

peek :: [Int] -> Int
peek [] = error "Cannot peek from an empty list!"
peek xs = last xs

isEmpty :: [Int] -> Bool
isEmpty [] = True
isEmpty xs = False

现在我想创建一个迭代整数列表并在堆栈上执行以下操作的函数：

如果偶数，则入栈。
如果为奇数，则从堆栈弹出。

例如，假设我们有一个整数输入列表 [0,2,6,7,3,4]。函数的流程应该是这样的：

Current Int         Operation           Result
0 (First item)      push 0 []           [0]
2                   push 2 [0]          [0, 2]
6                   push 6 [0, 2]       [0, 2, 6]
7                   pop [0, 2, 6]       [0, 2]
3                   pop [0, 2]          [0]
4 (Last item)       push 4 [0]          [0, 4]

这是我到目前为止所得到的，显然没有遍历列表并且没有真正起作用：

operation :: [Int] -> [Int]
operation [] = []
operation (x:xs) | even x = push x stack
                 | odd x = pop stack
    where stack = []

将不胜感激。提前致谢！

Answer 1

使用您的代码，使用 foldl.

最容易实现

operation :: [Int] -> [Int]
operation = foldl step []
    where step xs x | odd x = pop xs
                    | otherwise = push x xs

但是，应该注意的是，您的堆栈实现使这些 pop 和 push 函数变慢了很多。由于 Haskell 列表是单链表，您必须遍历整个列表才能到达最后的值。如果只操作列表头部的值，然后在整个操作完成后反转列表，效率会高得多。这会将您的 O(n²) 操作变成 O(n).

pop = tail
push = (:)

operation :: [Int] -> [Int]
operation = reverse . foldl step []
    where step xs x | odd x = pop xs
                    | otherwise = push x xs

还需要注意的是，这个函数还是不安全的，因为如果odd个数太多，可能会导致运算出错。最好使用 Maybe 来阻止任何错误。

import Control.Monad (foldM)

pop :: [a] -> Maybe [a]
pop [] = Nothing
pop (_:xs) = Just xs

push :: a -> [a] -> [a]
push = (:)

operation :: [Int] -> Maybe [Int]
operation = fmap reverse . foldM step []
    where step xs x | odd x = pop xs
                    | otherwise = Just (push x xs)

遍历列表并在 Haskell 中的堆栈上执行操作

Iterating through a list and perform operations on a stack in Haskell

stack

haskell