piet-0.1: A Piet interpreter




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 Source

The RollStack type.



isEmpty :: RollStack a -> BoolSource

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

top :: RollStack a -> Maybe aSource

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


empty :: RollStack aSource

O(1). Construct an empty Stack.

singleton :: a -> RollStack aSource

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

Insert delete and roll operations

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

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

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

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



:: Int

Number of rolls

-> Int


-> 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 aSource

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

toList :: RollStack a -> [a]Source

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