Re: [Haskell-cafe] Stack data structure

8 Dec 2018

      Hi Daniel,

Could you say what it was that you are looking for that you did not find in
existing libraries?

A cursory glance of your code did not reveal anything striking.

Also the traditional way of discussing code on this list is to paste it in
the email, literate style if you wish, and not as file attachments. Github
gists and lpaste have also seen use but there is nothing like the immediacy
of code in email.

To that end, I have pasted your code below for the benefit of all.

Best, Kim-Ee

module Data.Stack ( Stack
                  , empty
                  , size
                  , push, push'
                  , peek
                  , pop, pop_, _pop
                  , turn
                  , null
                  , fromList, toList
                  , over, under
                  ) where

import qualified Data.Sequence as S
import qualified Data.Foldable as F
import           Prelude                hiding (null)

data Stack a = Stack (S.Seq a) deriving (Eq, Read, Show)

-- | returns the empty stack
-- | O(1)
empty :: Stack a
empty = Stack S.empty

-- | returns the stack size
-- | O(1)
size :: Stack a -> Int
size (Stack items) = S.length items

-- | push an element on the stack
-- | O(1)
push :: Stack a -> a -> Stack a
push (Stack items) item = Stack (item S.<| items)

-- | push with its arguments flipped
-- | O(1)
push' :: a -> Stack a -> Stack a
push' = flip push

-- | returns the topmost element
-- | O(1)
peek :: Stack a -> Maybe a
peek (Stack items) = items S.!? 0

-- | returns the topmost element or nothing and the new stack
-- | O(1)
pop :: Stack a -> (Stack a, Maybe a)
pop (Stack items) = (Stack $ S.drop 1 items, items S.!? 0)

-- | return the stack without the topmost element
-- | O(1)
pop_ :: Stack a -> (Stack a)
pop_ stack = fst $ pop stack

-- | returns the topmost element or nothing
-- | O(1)
_pop :: Stack a -> Maybe a
_pop stack = snd $ pop stack

-- | turns the stack upside down
-- | O(n)
turn :: Stack a -> Stack a
turn (Stack items) = Stack (S.reverse items)

-- | returns true if it is the empty stack
-- | O(1)
null :: Stack a -> Bool
null (Stack items) = S.null items

-- | creates a stack from a list
-- | O(n)
fromList :: [a] -> Stack a
fromList list = Stack $ S.fromList list

-- | returns a list from the stack
-- | O(n)
toList :: Stack a -> [a]
toList (Stack items) = F.toList items

-- | puts the first stack onto the second stack
-- | O(log(min(a,b)))
over :: Stack a -> Stack a -> Stack a
(Stack a) `over` (Stack b) = Stack (a S.>< b)

-- | puts the first stack under the second stack
-- | O(log(min(a,b)))
under :: Stack a -> Stack a -> Stack a
(Stack a) `under` (Stack b) = Stack (b S.>< a)

On Saturday, December 8, 2018, daniel huebleitner <
daniel.huebleitner@student.tuwien.ac.at> wrote:
...
I am a graduate student in theoretical computer science playing around
with haskell for the past year or so. I wrote a Stack Data structure today
and would like to get some feedback from more experienced haskellers if
possible. I know its a really simple thing to write. But the implementation
I found on hackage wasn't what I was looking for. I haven't wrote unit
tests yet, but it should behave as expected.
Thanks in advance.
Kind regards.
Daniel
-- 
-- Kim-Ee

Re: [Haskell-cafe] Stack data structure

Kim-Ee Yeoh