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?
Casey == Casey Hawthorne cas...@istar.ca 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?
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 cas...@istar.ca wrote: From: Casey Hawthorne cas...@istar.ca 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?
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 nowg...@yahoo.com 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 cas...@istar.ca* wrote: From: Casey Hawthorne cas...@istar.ca 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?
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?
2010/2/5 michael rice nowg...@yahoo.com 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?
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 not...@gmail.com wrote: From: minh thu not...@gmail.com Subject: Re: [Haskell-cafe] Stack ADT? To: michael rice nowg...@yahoo.com Cc: haskell-cafe@haskell.org, Casey Hawthorne cas...@istar.ca Date: Friday, February 5, 2010, 11:04 AM 2010/2/5 michael rice nowg...@yahoo.com 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
[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
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
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 s...@informatik.uni-kiel.de wrote: From: Sebastian Fischer s...@informatik.uni-kiel.de Subject: Re: [Haskell-cafe] Stack ADT? To: haskell-cafe Cafe haskell-cafe@haskell.org 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 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?
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?
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 cas...@istar.ca 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?
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?
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?
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
