Copyright	Copyright (c) 2014 Kenneth Foner
Maintainer	kenneth.foner@gmail.com
Stability	experimental
Portability	non-portable
Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Stream.Tape

Description

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).

Synopsis

Documentation

data Tape a Source

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

Constructors

Tape
Fields 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`

Instances

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

Arguments

:: (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

Arguments

:: (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.