Tape- Bidirectionally infinite streams, akin to the tape of a Turing machine.

CopyrightCopyright (c) 2014 Kenneth Foner
Safe HaskellSafe-Inferred



This module implements two-way infinite streams with a focused element, akin to a Turing machine's tape. This structure is also known by the name of a list zipper (although in this case it's a list zipper with the additional criterion that the list is infinite in both directions).



data Tape a Source

A Tape is like a Turing-machine tape: infinite in both directions, with a focus in the middle.




viewL :: Stream a

the side of the Tape left of focus

focus :: a

the focused element

viewR :: Stream a

the side of the Tape right of focus


Functor Tape 
Applicative Tape

A tape is Applicative, where the <*> is equivalent to its ComonadApply instance (required by law), and a pure value is the tape consisting of copies of that value in both directions.

Comonad Tape

Tapes form a comonad, where extract gives the focus element and duplicate gives a diagonalized Tape (Tape a) such that extract . extract . moveL . duplicate == extract . moveL and likewise for moveR.

ComonadApply Tape

Applying one tape to another moves them together. This is like the Applicative instances for ZipList and Stream.

Distributive Tape

Tapes are Distributive because we can replicate their structure on the outside of a functor by sending movement commands through the functor via fmap moveL and fmap moveR, and using fmap focus to remove the extra structure inside the functor. As stated in the Distributive documentation, this can only work if all Tapes have the same cardinality of holes, and if there is no extra information to propagate from outside the functor -- hence, an Indexed tape can't be made into a Distributive, as there's no way to extract the index from the functor.

unfold Source


:: (c -> (a, c))

leftwards unfolding function

-> (c -> a)

function giving the focus value from the seed

-> (c -> (a, c))

rightwards unfolding function

-> c

seed value

-> Tape a 

Produce a Tape from a seed value, ala unfoldr for lists, or unfold for Streams.

iterate Source


:: (a -> a)

leftwards iteration function

-> (a -> a)

rightwards iteration function

-> a

focus value

-> Tape a 

Produce a Tape consisting of the infinite iteration of two functions to a starting focus value, ala iterate for lists or Streams.

enumerate :: Enum a => a -> Tape a Source

Given an enumerable type, produce the Tape where the left side is the sequence of predecessors, and the right side is the sequence of successors.

moveL :: Tape a -> Tape a Source

The functions moveR and moveL move the focus on the tape right and left, respectively.

moveR :: Tape a -> Tape a Source

The functions moveR and moveL move the focus on the tape right and left, respectively.

tapeOf :: a -> Tape a Source

Gives a Tape containing infinite copies of the given element.