CODEWITHSUNDEEP
haskell
Herokiller
Herokiller

Reputation: 2991

create stack as abstract data type in haskell

I need to create stack data type in haskell to be able to write like this:

let a = emptyStack

push 10 a
//[10]

pop a 
[]

I want push to look like

push :: a -> Stack a -> Stack a
push a b = a:b

but I have problems with syntax, exactly how to declare this new data type, so that

let a = emptyStack 
:t a

would show Stack

any hints on syntax

Upvotes: 1

Views: 8153

Answers (2)

josejuan
josejuan

Reputation: 9566

You can write

import Data.Maybe

data Stack a = Stack [a] deriving Show

empty :: Stack a
empty = Stack []

push :: a -> Stack a -> Stack a
push x (Stack xs)= Stack (x:xs)

pop :: Stack a -> (Maybe a, Stack a)
pop (Stack []) = (Nothing, Stack [])
pop (Stack (x:xs)) = (Just x, Stack xs)

example

*Main> push 4 $ push 3 empty
Stack [4,3]
*Main> pop $ push 4 $ push 3 empty
(Just 4,Stack [3])

this aproach is strict checking the type arguments (in contrast to @mhwombat solution). One or other aproach is valid (one will be better than other in some cases and vice versa).

Upvotes: 5

mhwombat
mhwombat

Reputation: 8136

Let's look at your implementation for push. It uses the operator :. You can find out the type of that operator like this:

ghci> :t (:)
(:) :: a -> [a] -> [a]

So this operator takes an a (which represents an arbitrary type), and a sequence of as, and returns the updated sequence. So your type Stack needs to be a sequence.

type Stack a = [a]

If you then define emptyStack like this:

emptyStack :: Stack a
emptyStack = []

You'll get the result you're looking for.

ghci> :t a
a :: Stack a

With that help, I think you'll be able to figure out how to write pop.

Upvotes: 4

Related Questions