On Feb 4, 2010, at 6:27 PM, michael rice wrote:

I haven't done much with modules so I'm guessing what you've provided is the guts of StackImpl, to hide the implementation?

Right. In order to make the Stack type abstract, you can hide the Stack data (that is, newtype) constructor and only export the Stack type constructor and the operations. You can use the following module header (I should have provided it in the first place): module Data.Stack (Stack, emptyStack, isEmptyStack, push, pop, top) where Making the Stack type abstract has the advantage that you can later change the implementation without affecting users of your Stack library which can only depend on its interface. Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

data Stack a = EmptyStk | Stk a (Stack a)

I find it amusing that the book defined a type that is exactly isomorphic to the standard list (EmptyStk === [] and Stk === (:)). I guess it's just for clarity? On Thu, Feb 4, 2010 at 12:29 PM, Casey Hawthorne wrote:

On Thu, 4 Feb 2010 09:07:28 -0800 (PST), you wrote:

...

Can't find a Stack datatype on Hoogle? Where should I look?

Michael

From "Algorithms: a functional programming approach" Second edition Fethi Rabhi Guy Lapalme

data Stack a = EmptyStk | Stk a (Stack a)

push x s = Stk x s

pop EmptyStk = error "pop from an empty stack" pop (Stk _ s) = s

top EmptyStk = error "top from an empty stack" top (Stk x _) = x

emptyStack = EmptyStk

stackEmpty EmptyStk = True stackEmpty _ = False

newtype Stack a = Stk [a]

push x (Stk xs) = Stk (x:xs)

pop (Stk []) = error "pop from an empty stack" pop (Stk (_:xs)) = Stk xs

top (Stk []) = error "top from an empty stack" top (Stk (x:_)) = x

emptyStack = Stk []

stackEmpty (Stk []) = True stackEmpty (Stk _ ) = False

-- Regards, Casey _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Not using Stack for anything, just trying to understand how things can be done in Haskell. To that end... What's going on here? I'm not even calling function POP. Michael ====================== module Data.Stack (Stack, emptyStack, isEmptyStack, push, pop, top) where newtype Stack a = Stack [a] emptyStack = Stack [] isEmptyStack (Stack xs) = null xs push x (Stack xs) = Stack (x:xs) pop (Stack (_:xs)) = Stack xs top (Stack (x:_)) = x ====================== [michael@localhost ~]$ ghci Stack.hs GHCi, version 6.10.4: http://www.haskell.org/ghc/  :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. [1 of 1] Compiling Data.Stack       ( Stack.hs, interpreted ) Ok, modules loaded: Data.Stack. *Data.Stack> let s1 = emptyStack *Data.Stack> top (push 1 s1) 1 *Data.Stack> top (push 2 s1) 2 *Data.Stack> top (push 3 s1) 3 *Data.Stack> let s2 = pop s1 *Data.Stack> top s2 *** Exception: Stack.hs:8:0-28: Non-exhaustive patterns in function pop *Data.Stack> --- On Fri, 2/5/10, Casey Hawthorne wrote: From: Casey Hawthorne Subject: Re: [Haskell-cafe] Stack ADT? To: haskell-cafe@haskell.org Date: Friday, February 5, 2010, 10:36 AM You could also implement stacks with mutable data structures, e.g. STArray, etc. What do you want to use a stack ADT for? Usually stacks are discussed for pedagogical purposes but usually recursion is used if you need a stack like operation. -- Regards, Casey _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

What's going on here? I'm not even calling function POP. *Data.Stack> let s2 = pop s1 *Data.Stack> top s2 *** Exception: Stack.hs:8:0-28: Non-exhaustive patterns in function pop

Haskell being a non strict language, does not evaluate pop s1 when you define let s2 = pop s1. but when you try to use s2 by evaluating "top s2" "pop s1" needs to be evaluated leading to the error in "pop", since the definition of pop, does not deal with the case when the Stack is empty (Stack []).

pop (Stack (_:xs)) = Stack xs top (Stack (x:_)) = x

I see now that what I thought was happening wasn't happening at all.

top (push 1 s1)  gives me the top of the new Stack returned by PUSH. s1 remains unchanged.

Thanks, Michael --- On Fri, 2/5/10, minh thu wrote: From: minh thu Subject: Re: [Haskell-cafe] Stack ADT? To: "michael rice" Cc: haskell-cafe@haskell.org, "Casey Hawthorne" Date: Friday, February 5, 2010, 11:04 AM 2010/2/5 michael rice

Not using Stack for anything, just trying to understand how things can be done in Haskell.

To that end...

What's going on here? I'm not even calling function POP.

Michael

======================

module Data.Stack (Stack, emptyStack, isEmptyStack, push, pop, top) where

newtype Stack a = Stack [a]

emptyStack = Stack [] isEmptyStack (Stack xs) = null xs push x (Stack xs) = Stack (x:xs) pop (Stack (_:xs)) = Stack xs top (Stack (x:_)) = x

======================

[michael@localhost ~]$ ghci Stack.hs GHCi, version 6.10.4: http://www.haskell.org/ghc/  :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. [1 of 1] Compiling Data.Stack       ( Stack.hs, interpreted ) Ok, modules loaded: Data.Stack. *Data.Stack> let s1 = emptyStack *Data.Stack> top (push 1 s1) 1 *Data.Stack> top (push 2 s1) 2 *Data.Stack> top (push 3 s1) 3 *Data.Stack> let s2 = pop s1 *Data.Stack> top s2 *** Exception: Stack.hs:8:0-28: Non-exhaustive patterns in function pop

When you write   push 1 s1 you get a new stack value. you can view it by typing 'it' in ghci (provided you have an instance of Show for it). s1 is still s1, the empty stack. When you write   let s2 = pop s1 Nothing happens yet, but if you want to evaluate s2, e.g. by typing it in ghci, pop will be applied to the empty stack, which is not taken care of in its definition. And you do want evaluate s2 when you eventually write   top s2. HTH, Thu