Re: [Haskell-cafe] Stack ADT?
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 > > == > > [mich...@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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack ADT?
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 > > == > > [mich...@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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack ADT?
> 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack ADT?
What's "going on" is that data structures in Haskell are immutable. Thus, when you call "push" on a stack, you get a new stack with the new element pushed onto it, and the original stack is left un-touched. On Fri, Feb 5, 2010 at 10:56 AM, michael rice wrote: > 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 > > == > > [mich...@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://mc/compose?to=haskell-c...@haskell.org> > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack ADT?
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 == [mich...@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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack ADT?
> "Casey" == Casey Hawthorne writes: Casey> You could also implement stacks with mutable data structures, Casey> e.g. STArray, etc. Casey> What do you want to use a stack ADT for? BTW, There is a Myers stack in Edison. Disclaimer - I don't know what a Myers stack is. -- Colin Adams Preston Lancashire ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack ADT?
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
Re: [Haskell-cafe] Stack ADT?
On Feb 5, 2010, at 6:38 AM, 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 module Stack(Stack,push,pop,top,emptyStack,stackEmpty) where ... Or just use a list. A more Haskellish approach to stacks than using "pop" and "top" would be something like this: newtype Stack t = [t] emptyStack = Stack [] stackPush (Stack s) = Stack (x:s) viewStack (Stack []) = Nothing viewStack (Stack (top:rest)) = Just (top, Stack rest) Instead of if stackEmpty s then ... else ... top s ... pop s ... do case viewStack s of Nothing -> ... Just (top, rest) -> ... Note that none of the functions in this interface can fail. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack ADT?
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.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack ADT?
Am Donnerstag 04 Februar 2010 23:18:34 schrieb Daniel Peebles: > > 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? Also type safety, I think. However, I prefer newtype Stack a = Stack [a] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack ADT?
> > 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 > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack ADT?
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 To be more complete. module Stack(Stack,push,pop,top,emptyStack,stackEmpty) where push:: a-> Stack a -> Stack a pop :: Stack a -> Stack a top :: Stack a -> a emptyStack :: Stack a stackEmpty :: Stack a -> Bool 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
Re: [Haskell-cafe] Stack ADT?
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
Re: [Haskell-cafe] Stack ADT?
I was looking here: http://www.haskell.org/haskellwiki/Abstract_data_type I haven't done much with modules so I'm guessing what you've provided is the guts of StackImpl, to hide the implementation? Thanks, Michael --- On Thu, 2/4/10, Sebastian Fischer wrote: From: Sebastian Fischer Subject: Re: [Haskell-cafe] Stack ADT? To: "haskell-cafe Cafe" Date: Thursday, February 4, 2010, 12:16 PM On Feb 4, 2010, at 6:07 PM, michael rice wrote: > Can't find a Stack datatype on Hoogle? Where should I look? Could not find one on Hackage either. Probably because its so easy to handcraft your own: 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 I saw such stacks in Haskell only for educational purposes. Usually, people seem to use lists directly. Sebastian --Underestimating the novelty of the future is a time-honored tradition. (D.G.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack ADT?
On Feb 4, 2010, at 6:07 PM, michael rice wrote: Can't find a Stack datatype on Hoogle? Where should I look? Could not find one on Hackage either. Probably because its so easy to handcraft your own: 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 I saw such stacks in Haskell only for educational purposes. Usually, people seem to use lists directly. Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Stack ADT?
Can't find a Stack datatype on Hoogle? Where should I look? Michael ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
