Data.RollStack

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.

Stack type

data RollStack a

The RollStack type.

Instances

Functor RollStack

Foldable RollStack

Eq a => Eq (RollStack a)

Ord a => Ord (RollStack a)

Show a => Show (RollStack a)

Query

isEmpty :: RollStack a -> Bool

O(1). Tests, if a RollStack is empty.

top :: RollStack a -> Maybe a

O(1). Looks at the top element of the RollStack. Returns Nothing if the stack is empty.

Construction

empty :: RollStack a

O(1). Construct an empty Stack.

singleton :: a -> RollStack a

O(1). Construct a RollStack containing a single element.

Insert delete and roll operations

push :: a -> RollStack a -> RollStack a

O(1). Push an element on the RollStack.

pop :: RollStack a -> Maybe (a, RollStack a)

O(1). Pop the top element from the RollStack if it is not empty.

roll

Arguments

:: Int

Number of rolls

-> Int

Depth

-> RollStack a

Original RollStack

-> RollStack a

Rotated RollStack

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.

List conversion

fromList :: [a] -> RollStack a

O(n). Convert a list into a Stack. The list's head will be the first element of the Stack

toList :: RollStack a -> [a]

O(n). Convert a RollStack to a list. The top of the RollStack will be the list's head.