Haskell Stacks : Two Different Ways
I am starting to attempt to understand how Haskell can persist functions sans the variables. You can do it with lists, already. There are plenty of functions that demonstrate the concept. But I want to expand further. I want to try implementing a stack with a list, and then do it with a recursive type. This is what I have for the first one:
I thought the reverse function was neat, but seemingly costly. But, from the Prelude:
We can see a really slick way of doing reverses. "reverse" is merely a function curry of a foldl waiting for the last parameter. Let's see if it is costly:
So, the ones with the same indentation are the same, except the second line is the flip function evaluated. It is what I expected, though. It takes O(n) (?) time (there are two operations on the data: one operation to flip, and another operation to add to the new list. So, maybe it is O(2n)? I forget my algorithm lessons.) It seems though, that the original implementation I provided performs the same though. Maybe expressing it via reverse then is easier.
Lists are, still probably still efficiently implemented, and those operations I am doing are turned into an iteration (tail-call recursion), plus some other magic I don't know about. I have to think of a nifty way of handling it faster though.
Anyway, the other idea I had was to make a stack a recursive data type:
What a wacky idea. I have to think about this one, and read some common examples on this.
putAtEnd [] item = [item]
putAtEnd (x:xs) item = x : putAtEnd xs item
push lst item = putAtEnd lst item
-- or
-- push lst item = reverse (item : (reverse lst))
pop lst = pop_ lst ((length lst) - 1)
pop_ _ 0 = []
pop_ (x:xs) len = x : pop_ xs (len - 1)
-- or
-- pop lst = reverse (tail (reverse lst))
I thought the reverse function was neat, but seemingly costly. But, from the Prelude:
reverse :: [a] -> [a]
reverse = foldl (flip (:)) []
flip f x y = f y x
foldl f z [] = z
foldl f z (x : xs) = foldl f (f z x) xs
We can see a really slick way of doing reverses. "reverse" is merely a function curry of a foldl waiting for the last parameter. Let's see if it is costly:
reverse [1,2,3,4]
-> foldl (flip (:)) [] [1,2,3,4]
-> foldl (flip (:)) (flip [] 1) [2,3,4]
-> foldl (flip (:)) (1 : []) [2,3,4]
-> foldl (flip (:)) (flip [1] 2) [3,4]
-> foldl (flip (:)) (2 : [1]) [3,4]
-> foldl (flip (:)) (flip [2,1] 3) [4]
-> foldl (flip (:)) (3 : [2,1]) [4]
-> foldl (flip (:)) (flip 4 : [3,2,1]) []
-> foldl (flip (:)) [4,3,2,1] []
-> [4,3,2,1]
So, the ones with the same indentation are the same, except the second line is the flip function evaluated. It is what I expected, though. It takes O(n) (?) time (there are two operations on the data: one operation to flip, and another operation to add to the new list. So, maybe it is O(2n)? I forget my algorithm lessons.) It seems though, that the original implementation I provided performs the same though. Maybe expressing it via reverse then is easier.
Lists are, still probably still efficiently implemented, and those operations I am doing are turned into an iteration (tail-call recursion), plus some other magic I don't know about. I have to think of a nifty way of handling it faster though.
Anyway, the other idea I had was to make a stack a recursive data type:
data Stack n m = Item m | StackFrame ((Stack n) (Item m))
-- so ...
(StackFrame (StackFrame (Item 1) (Item 2)) (Item 3))
-- looks like
-- 3
-----
-- 2
-----
-- 1
-----
What a wacky idea. I have to think about this one, and read some common examples on this.

3 Comments:
Hi Brian
Your Stack datatype is essential equal to the normal [] (List) datatype, except that you have ruled out the possibility of an empty stack.
But why don't you just use the following implementation of stacks:
empty = []
push stack elem = elem : stack
pop (elem : stack) = stack
top (elem : stack) = elem
All operations are cheap constant time operations.
Thanks for the info, ken. :)
O(2n) is equivalent to O(n). The function runs in time linearly proportional to the size of the list (n)
;)
Post a Comment
<< Home