[Haskell-beginners] Problem implementing a stack

Chaddaï Fouché chaddai.fouche at gmail.com
Sat Dec 12 06:03:05 EST 2009


On Wed, Dec 9, 2009 at 2:17 AM, Jacob Faren <shujinw at gmail.com> wrote:
> Hello. I'm implement data structures (a stack, here) to get familiar with
> Haskell. It's not going very well. I have the following code...
>
>     -- test.hs
>     data Stack a = Top (Stack a) | Layers [a] deriving (Show)
>
>     stack :: Stack a
>     stack = Top (Layers [])
>
>     push :: Stack a -> a -> Stack a
>     push (Top (Layers ls)) value = Top (Layers (value:ls))
>
> And I run the following in ghci...
>
>     Prelude> :l test
>     [1 of 1] Compiling Main             ( test.hs, interpreted )
>     Ok, modules loaded: Main.
>     *Main> push stack 4
>     Top (Layers [4])
>     *Main> let st = stack
>     *Main> push st 4
>     ^CInterrupted.
>
> The output of the last command never resolves. I have to kill it. Might
> anyone have an idea why the push function is failing with st, but not
> with stack?

It shouldn't, and it doesn't here, which version of GHC are you using ?

By the way, your Stack datatype seems broken to me, what would be the
meaning of (Top (Top (Top (Layers []))) ? I do believe that you do not
wish to allow anything besides a Layers inside a Top, and your push
function supports this interpretation. In this case, your Layers
constructor is unnecessary and your datatype declaration should be :

> data Stack a = Top [a] deriving (Show)

At which point you may realize that this type is isomorphic to the
list type (+ one bottom) and thus is better written :
- Either as a type synonym :
type Stack a = [a]

- Or if you wish to ensure some invariants on your type or add some
typeclass instances specific to stacks :
newtype Stack a = Top [a] deriving (Show)

-- 
Jedaï


More information about the Beginners mailing list