Stack data structure

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Stack data structure

daniel huebleitner
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




_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

Stack.hs (2K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Stack data structure

Kim-Ee Yeoh
Administrator
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 <[hidden email]> 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

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Stack data structure

Francesco Ariis
In reply to this post by daniel huebleitner
Hello Daniel,

On Sat, Dec 08, 2018 at 01:38:52AM +0100, daniel huebleitner 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.

The (small) tings I noticed:

- For haddock purposes, comments should start with |, but only the first
  line. I.e.:

      -- | returns the empty stack
      -- O(1)

- `data Stack a` could well become `newtype Stack a` since there is
  only one constructor/field in it.

- hlint picks up a redundant pair of brackets on line 51.

I personally don't mind attached code but maybe the `text/x-haskell`
directive isn't handled gracefully by all clients.

I played around with it on ghci and everything seemed fine!

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Stack data structure

Serguey Zefirov
In reply to this post by daniel huebleitner
The list as usually constructed (head and tail) is a stack.

сб, 8 дек. 2018 г. в 03:43, daniel huebleitner <[hidden email]>:
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



_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Stack data structure

Ian Denhardt
Quoting Serguey Zefirov (2018-12-08 09:33:35)
> The list as usually constructed (head and tail) is a stack.

This was my reaction as well; except for the over and under operations,
everything in the file would have as-good or better asymptotic
complexity as a simple list, and probably better constant factors too.
The docs for Data.Sequence even say:

> Note that sequences are typically slower than lists when using only
> operations for which they have the same big-(O) complexity: sequences
> make rather mediocre stacks!

It would also likely be more readable to use a list, in that every
Haskeller knows the list APIs, whereas Data.Sequence is less likely to
be familiar.

TBH, most cases where I would want a stack I wouldn't even bother with
the extra layer of abstraction over lists -- I'd probably use the
directly.

You mention being unsatisfied with the existing libraries -- what was
your use case?
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Stack data structure

Serguey Zefirov
I once improved Seq-based code by changing them to lists. The improvement was about 10x in both memory and speed and all can be attributed to just constant factors.

When I saw the same error again above I can't help myself.


сб, 8 дек. 2018 г. в 22:48, Ian Denhardt <[hidden email]>:
Quoting Serguey Zefirov (2018-12-08 09:33:35)
> The list as usually constructed (head and tail) is a stack.

This was my reaction as well; except for the over and under operations,
everything in the file would have as-good or better asymptotic
complexity as a simple list, and probably better constant factors too.
The docs for Data.Sequence even say:

> Note that sequences are typically slower than lists when using only
> operations for which they have the same big-(O) complexity: sequences
> make rather mediocre stacks!

It would also likely be more readable to use a list, in that every
Haskeller knows the list APIs, whereas Data.Sequence is less likely to
be familiar.

TBH, most cases where I would want a stack I wouldn't even bother with
the extra layer of abstraction over lists -- I'd probably use the
directly.

You mention being unsatisfied with the existing libraries -- what was
your use case?

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.