Data.Label.Zipper

Contents

Usage
Zipper functionality
Convenience operators, types, and exports
- Re-exports

Description

PEZ is a generic zipper library. It uses lenses from the fclabels package to reference a "location" to move to in the zipper. The zipper is restricted to types in the Typeable class, allowing the user to "move up" through complex data structures such as mutually-recursive types, where the compiler could not otherwise type-check the program. . Both the Typeable class and fclabels lenses can be derived in GHC, making it easy for the programmer to use a zipper with a minimum of boilerplate.

Synopsis

Usage

First import the library, which brings in the Typeable and fclabels modules. You will also want to enable a few extensions: TemplateHaskell, DeriveDataTypeable, TypeOperators

 module Main where

 import Data.Label.Zipper

Create a datatype, deriving an instance of the Typeable class, and generate a lens using Template Haskell functionality from fclabels:

 data Tree a = Node { 
     _leftNode :: Tree a
   , _val      :: a 
   , _rightNode :: Tree a }
   | Nil  
   deriving (Typeable,Show)

 $(mkLabels [''Tree])

Now we can go crazy using Tree in a Zipper:

 treeBCD = Node (Node Nil 'b' Nil) 'c' (Node Nil 'd' Nil)
 
 descendLeft :: (Typeable a)=> Zipper1 (Tree a) -> Zipper1 (Tree a)
 descendLeft = moveFloor (to leftNode) -- stops at Nil constructor

 insertLeftmost :: (Typeable a)=> a -> Tree a -> Maybe (Tree a)
 insertLeftmost a = close . setf newNode . descendLeft . zipper
     where newNode = Node Nil a Nil

 treeABCD = insertLeftmost 'a' treeBCD

Because of the flexibility of fclabels, this zipper library can be used to express moving about in reversible computations simply by defining such a lens, for instance:

 stringRep :: (Show b, Read b) => b :-> String
 stringRep = lens show (const . read)

Another exciting possibility are zippers that can perform validation, refusing to close if a field is rejected.

Zipper functionality

data Zipper a b Source

Encapsulates a data type a at a focus b, supporting various Motion operations

Instances

Typeable2 Zipper

A note on failure in zipper operations:

Most operations on a Zipper return a result in a Failure class monad, throwing various types of failures. Here is a list of failure scenarios:

a move Up arrives at a type that could not be cast to the type expected
a move (Up 1) when already atTop, i.e. we cannot ascend anymore
a move to a label (e.g. foo :: FooBar :~> FooBar) causes a failure in the getter function of the lens, usually because the focus was the wrong constructor for the lens
a move (Up n) causes the setter of the lens we used to arrive at the current focus to fail on the value of the current focus. This is not something that happens for normal lenses, but is desirable for structures that enforce extra-type-system constraints.
a close cannot re-build the structure because some setter failed, as above. Again, this does not occur for TH'generated lenses.

See the failure package for details.

Creating and closing Zippers

zipper :: a -> Zipper a aSource

create a zipper with the focus on the top level.

close :: Zipper a b -> Maybe aSource

re-assembles the data structure from the top level, returning Nothing if the structure cannot be re-assembled.

Note: For standard lenses produced with mkLabels this will never fail. However setters defined by hand with lens can be used to enforce arbitrary constraints on a data structure, e.g. that a type Odd Int can only hold an odd integer. This function returns Nothing in such cases, which corresponds to the LensSetterFailed constructor of UpErrors

Moving around

class Exception (ThrownBy mot) => Motion mot whereSource

Types of the Motion class describe "paths" up or down (so to speak) through a datatype. The exceptions thrown by each motion are enumerated in the associated type ThrownBy mot. The Motion type that will return the focus to the last location after doing a 'moveSaving is given by Returning mot.

Associated Types

type ThrownBy mot :: *Source

type Returning mot :: * -> * -> *Source

Methods

move :: (Typeable b, Typeable c, Failure (ThrownBy mot) m) => mot b c -> Zipper a b -> m (Zipper a c)Source

Move to a new location in the zipper, either returning the new zipper, or throwing err in some Failure class type (from the failure pkg.)

The return type can be treated as Maybe for simple exception handling or one can even use something like control-monad-exception to get powerful typed, checked exceptions.

moveSaving :: (Typeable b, Typeable c, Failure (ThrownBy mot) m) => mot b c -> Zipper a b -> m (Returning mot c b, Zipper a c)Source

like move but saves the Motion that will return us back to the location we started from in the passed zipper.

Instances

Motion To
Motion UpCasting
Motion Up

newtype Up c b Source

a Motion upwards in the data type. e.g. move (Up 2) would move up to the grandparent level, as long as the type of the focus after moving is b. Inline type signatures are often helpful to avoid ambiguity, e.g. (Up 2 :: Up Char (Tree Char)) read as "up two levels, from a focus of type Char to Tree Char".

This Motion type throws UpErrors

Constructors

Up
Fields upLevel :: Int

Instances

Category Up
LevelDelta Up
Motion Up
Bounded (Up c b)
Enum (Up c b)
Eq (Up c b)
Integral (Up c b)
Num (Up c b)
Ord (Up c b)
Real (Up c b)
Show (Up c b)

data UpCasting c b Source

indicates a Motion upwards in the zipper until we arrive at a type which we can cast to b, otherwise throwing UpErrors

Constructors

UpCasting

Instances

Typeable2 UpCasting
Motion UpCasting
Eq (UpCasting c b)
Show (UpCasting c b)

data To a b Source

A Motion type describing an incremental path "down" through a data structure. Use to to move to a location specified by a fclabels lens.

Use restore to return to a previously-visited location in a zipper, with previous history intact, so:

 (\(l,ma)-> move l <$> ma) (closeSaving z)  ==  Just z

Use flatten to turn this into a standard fclabels lens, flattening the incremental move steps.

Throws errors of type ToErrors:

Instances

Typeable2 To
Category To
LevelDelta To
Motion To

to :: (Typeable a, Typeable b) => (a :~> b) -> To a bSource

use a fclabels label to define a Motion "down" into a data type.

Error types

Every defined Motion has an associated error type, thrown in a Failure class monad (see failure). These types are also part of a small Exception hierarchy.

data ZipperException Source

The root of the exception hierarchy for Zipper move operations:

Instances

Show ZipperException
Typeable ZipperException
Exception ZipperException

data UpErrors Source

Constructors

CastFailed
LensSetterFailed
MovePastTop

Instances

Eq UpErrors
Show UpErrors
Typeable UpErrors
Exception UpErrors

data ToErrors Source

Constructors

LensGetterFailed

Instances

Eq ToErrors
Show ToErrors
Typeable ToErrors
Exception ToErrors

Repeating movements

moveWhile :: (Failure (ThrownBy mot) m, Motion mot, Typeable c) => (c -> Bool) -> mot c c -> Zipper a c -> m (Zipper a c)Source

Apply a motion each time the focus matches the predicate, raising an error in m otherwise

moveUntil :: (Failure (ThrownBy mot) m, Motion mot, Typeable c) => (c -> Bool) -> mot c c -> Zipper a c -> m (Zipper a c)Source

Apply a motion zero or more times until the focus matches the predicate

 moveUntil p = moveWhile (not . p)

moveFloor :: (Motion m, Typeable a, Typeable b) => m b b -> Zipper a b -> Zipper a bSource

Apply the given Motion to a zipper until the Motion fails, returning the last location visited. For instance moveFloor (to left) z might return the left-most node of a zippered tree z.

 moveFloor m z = maybe z (moveFloor m) $ move m z

The zipper focus

a fclabels lens for setting, getting, and modifying the zipper's focus. Note: a zipper may fail to close if the lens used to reach the current focus performed some validation.

focus :: forall (~>) a b. Arrow ~> => Lens ~> (Zipper a b) bSource

viewf :: Zipper a b -> bSource

a view function for a Zipper's focus.

 viewf = get focus

setf :: b -> Zipper a b -> Zipper a bSource

set the Zipper's focus.

 setf = set focus

modf :: (b -> b) -> Zipper a b -> Zipper a bSource

modify the Zipper's focus.

 modf = modify focus

Querying Zippers and Motions

atTop :: Zipper a b -> Bool Source

returns True if Zipper is at the top level of the data structure:

level :: Zipper a b -> Int Source

Return our zero-indexed depth in the Zipper. if atTop zipper then level zipper == 0

class Motion m => LevelDelta m whereSource

Motion types which alter a Zipper by a knowable integer quantity. Concretly, the following should hold:

 level (move m z) == level z + delta m

For motions upwards this returns a negative value.

Methods

delta :: (Typeable a, Typeable b) => m a b -> Int Source

Instances

LevelDelta To
LevelDelta Up

Saving and recalling positions in a Zipper

save :: Zipper a b -> To a bSource

Return a path To the current location in the Zipper. This lets you return to a location in your data type with restore.

 save = fst . closeSaving

closeSaving :: Zipper a b -> (To a b, Maybe a)Source

Close the zipper, returning the saved path back down to the zipper's focus. See close

restore :: (Typeable a, Typeable b, Failure ToErrors m) => To a b -> a -> m (Zipper a b)Source

Enter a zipper using the specified Motion.

Saving and restoring lets us for example: find some location within our structure using a Zipper, save the location, fmap over the entire structure, and then return to where we were safely, even if the "shape" of our structure has changed.

 restore s = move s . zipper

flatten :: (Typeable a, Typeable b) => To a b -> a :~> bSource

Extract a composed lens that points to the location we saved. This lets us modify, set or get a location that we visited with our Zipper, after closing the Zipper, using fclabels get and set.

Convenience operators, types, and exports

type Zipper1 a = Zipper a aSource

a simple type synonym for a Zipper where the type at the focus is the same as the type of the outer (unzippered) type. Cleans up type signatures for simple recursive types:

Re-exports

These re-exported functions should be sufficient for the most common - zipper functionality

class Typeable a where

The class Typeable allows a concrete representation of a type to be calculated.

Methods

typeOf :: a -> TypeRep

Takes a value of type a and returns a concrete representation of that type. The value of the argument should be ignored by any instance of Typeable, so that it is safe to pass undefined as the argument.

Instances

Typeable Bool
Typeable Char
Typeable Double
Typeable Float
Typeable Int
Typeable Int8
Typeable Int16
Typeable Int32
Typeable Int64
Typeable Integer
Typeable Ordering
Typeable RealWorld
Typeable Word
Typeable Word8
Typeable Word16
Typeable Word32
Typeable Word64
Typeable Exp
Typeable Match
Typeable Clause
Typeable Pat
Typeable Type
Typeable Dec
Typeable Name
Typeable FunDep
Typeable Pred
Typeable TyVarBndr
Typeable ()
Typeable SomeException
Typeable ErrorCall
Typeable ArithException
Typeable TypeRep
Typeable TyCon
Typeable NameFlavour
Typeable NameSpace
Typeable Info
Typeable ClassInstance
Typeable Fixity
Typeable FixityDirection
Typeable Lit
Typeable Body
Typeable Guard
Typeable Stmt
Typeable Range
Typeable FamFlavour
Typeable Foreign
Typeable Callconv
Typeable Safety
Typeable Pragma
Typeable InlineSpec
Typeable Strict
Typeable Con
Typeable Kind
Typeable ModName
Typeable PkgName
Typeable OccName
Typeable ZipperException
Typeable ToErrors
Typeable UpErrors
(Typeable1 s, Typeable a) => Typeable (s a)	One Typeable instance for all Typeable1 instances

mkLabels :: [Name] -> Q [Dec]

Derive lenses including type signatures for all the record selectors in a datatype. The types will be polymorphic and can be used in an arbitrary context.

type :~> f a = MaybeLens f a

Lens type for situations in which the accessor functions can fail. This is useful, for example, when accessing fields in datatypes with multiple constructors.

class Monad f => Failure e f where

Methods

failure :: e -> f v

Instances

Failure e []
Failure e Maybe
Exception e => Failure e IO
(MonadTrans t, Failure e m, Monad (t m)) => Failure e (t m)	Instance for all monad transformers, simply lift the `failure` into the base monad.
Failure e (Either e)

class (Typeable e, Show e) => Exception e where

Any type that you wish to throw or catch as an exception must be an instance of the Exception class. The simplest case is a new exception type directly below the root:

 data MyException = ThisException | ThatException
     deriving (Show, Typeable)

 instance Exception MyException

The default method definitions in the Exception class do what we need in this case. You can now throw and catch ThisException and ThatException as exceptions:

*Main> throw ThisException `catch` \e -> putStrLn ("Caught " ++ show (e :: MyException))
Caught ThisException

In more complicated examples, you may wish to define a whole hierarchy of exceptions:

 ---------------------------------------------------------------------
 -- Make the root exception type for all the exceptions in a compiler

 data SomeCompilerException = forall e . Exception e => SomeCompilerException e
     deriving Typeable

 instance Show SomeCompilerException where
     show (SomeCompilerException e) = show e

 instance Exception SomeCompilerException

 compilerExceptionToException :: Exception e => e -> SomeException
 compilerExceptionToException = toException . SomeCompilerException

 compilerExceptionFromException :: Exception e => SomeException -> Maybe e
 compilerExceptionFromException x = do
     SomeCompilerException a <- fromException x
     cast a

 ---------------------------------------------------------------------
 -- Make a subhierarchy for exceptions in the frontend of the compiler

 data SomeFrontendException = forall e . Exception e => SomeFrontendException e
     deriving Typeable

 instance Show SomeFrontendException where
     show (SomeFrontendException e) = show e

 instance Exception SomeFrontendException where
     toException = compilerExceptionToException
     fromException = compilerExceptionFromException

 frontendExceptionToException :: Exception e => e -> SomeException
 frontendExceptionToException = toException . SomeFrontendException

 frontendExceptionFromException :: Exception e => SomeException -> Maybe e
 frontendExceptionFromException x = do
     SomeFrontendException a <- fromException x
     cast a

 ---------------------------------------------------------------------
 -- Make an exception type for a particular frontend compiler exception

 data MismatchedParentheses = MismatchedParentheses
     deriving (Typeable, Show)

 instance Exception MismatchedParentheses where
     toException   = frontendExceptionToException
     fromException = frontendExceptionFromException

We can now catch a MismatchedParentheses exception as MismatchedParentheses, SomeFrontendException or SomeCompilerException, but not other types, e.g. IOException:

*Main> throw MismatchedParentheses catch e -> putStrLn ("Caught " ++ show (e :: MismatchedParentheses))
Caught MismatchedParentheses
*Main> throw MismatchedParentheses catch e -> putStrLn ("Caught " ++ show (e :: SomeFrontendException))
Caught MismatchedParentheses
*Main> throw MismatchedParentheses catch e -> putStrLn ("Caught " ++ show (e :: SomeCompilerException))
Caught MismatchedParentheses
*Main> throw MismatchedParentheses catch e -> putStrLn ("Caught " ++ show (e :: IOException))
*** Exception: MismatchedParentheses

Methods

toException :: e -> SomeException

fromException :: SomeException -> Maybe e

Instances

Exception SomeException
Exception ErrorCall
Exception ArithException
Exception ZipperException
Exception ToErrors
Exception UpErrors