CODEWITHSUNDEEP
haskellstack
user14609917
user14609917

Reputation:

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

I am self-learning Haskell. I have the following code that implements a stack using an list:

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

Now I want create a function that iterates over a list of integers and performs the following actions on a stack:

For example, say we have an input list of integers [0,2,6,7,3,4]. The flow of the function should be as follows:

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]

This is what I've got so far, which obviously doesn't iterate through the list and doesn't really work:

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

Help would be greatly appreciated. Thanks in advance!

Upvotes: 1

Views: 300

Answers (1)

castletheperson
castletheperson

Reputation: 33466

Using your code, it would be easiest to implement this using a foldl.

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

However, it should be noted that your implementation of a stack makes these pop and push functions much slower. Since Haskell lists are singly-linked lists, you must traverse the entire list in order to reach the value at the end. It would be much more efficient to only manipulate the value at the head of the list, and then reverse the list when the entire operation is complete. This will turn your O(n2) operation into O(n).

pop = tail
push = (:)

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

It should also be noted that this function is still not safe, because it's possible for the operation to produce an error if there are too many odd numbers. It would be better to use a Maybe in order to stop any errors.

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)

Upvotes: 1

Related Questions