Data.RollStack
Description
This module implements a customized stack for the Piet programming language.
In addition to the common push, pop and top operations, the
a RollStack provides a roll (see below) command, which is the
reason for using a Sequence and not a list as underlying data
structure.
Whenever the O-notation is used, n describes the number of elements within the stack.
- data RollStack a
- isEmpty :: RollStack a -> Bool
- top :: RollStack a -> Maybe a
- empty :: RollStack a
- singleton :: a -> RollStack a
- push :: a -> RollStack a -> RollStack a
- pop :: RollStack a -> Maybe (a, RollStack a)
- roll :: Int -> Int -> RollStack a -> RollStack a
- fromList :: [a] -> RollStack a
- toList :: RollStack a -> [a]
Stack type
The RollStack type.
Query
Construction
Insert delete and roll operations
pop :: RollStack a -> Maybe (a, RollStack a)Source
O(1). Pop the top element from the RollStack if it is not empty.
Arguments
| :: Int | Number of rolls |
| -> Int | Depth |
| -> RollStack a | Original |
| -> RollStack a | Rotated |
O(log(n)). A single roll to depth n is defined as burying the top
value on the stack n deep and bringing all values above it up by 1
place. A negative number of rolls rolls in the opposite direction. A
negative depth results in an error.