The Quipper System

Safe HaskellNone

Libraries.Auxiliary

Contents

Description

This module provides miscellaneous general-purpose auxiliary functions.

Synopsis

List operations

applyAt :: Int -> (a -> a) -> [a] -> [a] Source #

Apply a function to a specified position in a list.

overwriteAt :: Int -> a -> [a] -> [a] Source #

Overwrite an element at a specified position in a list.

has_duplicates :: Ord a => [a] -> Bool Source #

Check whether a list has duplicates.

substitute :: Eq a => [a] -> a -> [a] -> [a] Source #

substitute string character replacement: Replace the first occurrence of character in string by replacement.

Set and Map related operations

map_provide :: Ord k => k -> a -> Map k a -> Map k a Source #

Insert the given key-value pair in a Map, but only if the given key is not already present. If the key is present, keep the old value.

intset_inserts :: [Int] -> IntSet -> IntSet Source #

Insert the elements of a list in an IntSet (cf. insert).

intmap_zip :: IntMap x -> IntMap y -> IntMap (x, y) Source #

Take two IntMaps with the same domain, and form a new IntMap whose values are pairs. It is an error if the two inputs don't have identical domains.

intmap_zip_errmsg :: IntMap x -> IntMap y -> String -> IntMap (x, y) Source #

Like intmap_zip, but also takes an error message to use in case of domain mismatch.

intmap_map :: (x -> y) -> IntMap x -> IntMap y Source #

Map a function over all values in an IntMap.

intmap_mapM :: Monad m => (x -> m y) -> IntMap x -> m (IntMap y) Source #

Monadic version of intmap_map. Map a function over all values in an IntMap.

XIntMaps

data XIntMap a Source #

A XIntMap is just like an IntMap, except that it supports some additional efficient operations: to find the smallest unused key, to find the set of all keys ever used in the past, and to reserve a set of keys so that they will not be allocated. Moreover, it keeps track of the highest key ever used (whether or not it is still used in the current map).

Instances

Show a => Show (XIntMap a) # 

Methods

showsPrec :: Int -> XIntMap a -> ShowS #

show :: XIntMap a -> String #

showList :: [XIntMap a] -> ShowS #

xintmap_delete :: Int -> XIntMap a -> XIntMap a Source #

Delete a key from the XIntMap.

xintmap_deletes :: [Int] -> XIntMap a -> XIntMap a Source #

Delete a list of keys from a XIntMap.

xintmap_insert :: Int -> a -> XIntMap a -> XIntMap a Source #

Insert a new key-value pair in the XIntMap.

xintmap_inserts :: [(Int, a)] -> XIntMap a -> XIntMap a Source #

Insert a list of key-value pairs in the XIntMap.

xintmap_lookup :: Int -> XIntMap a -> Maybe a Source #

Look up the value at a key in the XIntMap. Return Nothing if not found.

xintmap_member :: Int -> XIntMap a -> Bool Source #

Check whether the given key is in the XIntMap.

xintmap_freshkey :: XIntMap a -> Int Source #

Return the first free key in the XIntMap, but without actually using it yet.

xintmap_freshkeys :: Int -> XIntMap a -> [Int] Source #

Return the next k unused keys in the XIntMap, but without actually using them yet.

xintmap_size :: XIntMap a -> Int Source #

Return the smallest key never used in the XIntMap.

xintmap_dirty :: XIntMap a -> IntSet Source #

A wire is dirty if it is touched but currently free.

xintmap_reserves :: IntSet -> XIntMap a -> XIntMap a Source #

Reserve a set of keys in the XIntMap. For any keys that are not free, do nothing. All keys must have been used before; for example, this is the case if they were returned by xintmap_dirty.

xintmap_unreserves :: IntSet -> XIntMap a -> XIntMap a Source #

Unreserve a list of keys in the XIntMap. If any key is currently used, do nothing. All keys must have been reserved before, and (therefore) must have been used before.

xintmap_makeclean :: XIntMap a -> XIntMap a Source #

Make an exact copy of the XIntMap, except that the set of touched wires is initially set to the set of used wires. In other words, we mark all free and reserved wires as untouched.

Various map- and fold-like list combinators

loop :: (Eq int, Num int) => int -> t -> (t -> t) -> t Source #

Iterate a function n times. Example:

loop 3 x f = f (f (f x))

loop_with_index :: (Eq int, Num int) => int -> t -> (int -> t -> t) -> t Source #

Like loop, but also pass a loop counter to the function being iterated. Example:

loop_with_index 3 x f = f 2 (f 1 (f 0 x))

fold_right_zip :: ((w, a, b) -> (w, c)) -> (w, [a], [b]) -> (w, [c]) Source #

Combine right-to-left zipping and folding. Example:

fold_right_zip f (w0, [a,b,c], [x,y,z]) = (w3, [a',b',c'])
 where f (w0,c,z) = (w1,c')
       f (w1,b,y) = (w2,b')
       f (w2,a,x) = (w3,a')

zip_strict :: [a] -> [b] -> [(a, b)] Source #

A "strict" version of zip, i.e., raises an error when the lists are not of the same length.

zip_strict_errmsg :: [a] -> [b] -> String -> [(a, b)] Source #

Like zip_strict, but also takes an explicit error message to use in case of failure.

zip_rightstrict :: [a] -> [b] -> [(a, b)] Source #

A "right strict" version of zip, i.e., raises an error when the left list is shorter than the right one.

zip_rightstrict_errmsg :: [a] -> [b] -> String -> [(a, b)] Source #

A version of zip_rightstrict that also takes an explicit error message to use in case of failure.

zipWith_strict :: (a -> b -> c) -> [a] -> [b] -> [c] Source #

A "strict" version of zipWith, i.e., raises an error when the lists are not of the same length.

zipWith_rightstrict :: (a -> b -> c) -> [a] -> [b] -> [c] Source #

A "right strict" version of zipWith, i.e., raises an error when the right list is shorter than the left one.

Monadic versions of list combinators

loopM :: (Eq int, Num int, Monad m) => int -> t -> (t -> m t) -> m t Source #

Monadic version of loop.

loop_with_indexM :: (Eq int, Num int, Monad m) => int -> t -> (int -> t -> m t) -> m t Source #

Monadic version of loop_with_index. Thus,

loop_with_indexM 3 x0 f

will do the following:

do
  x1 <- f 0 x0
  x2 <- f 1 x1
  x3 <- f 2 x2    
  return x3

zipRightWithRightStrictM :: Monad m => (a -> b -> m c) -> [a] -> [b] -> m [c] Source #

A right-to-left version of zipWithM, which is also "right strict", i.e., raises an error when the right list is shorter than the left one. Example:

zipRightWithM f [a,b] [x,y] = [f a x, f b y],

computed right-to-left.

zipRightWithRightStrictM_ :: Monad m => (a -> b -> m c) -> [a] -> [b] -> m () Source #

Same as zipRightWithM, but ignore the result.

fold_right_zipM :: Monad m => ((w, a, b) -> m (w, c)) -> (w, [a], [b]) -> m (w, [c]) Source #

Monadic version of fold_right_zip.

foldRightPairM :: Monad m => (w, [a], [b]) -> ((w, a, b) -> m w) -> m w Source #

Fold over two lists with state, and do it right-to-left. For example,

foldRightPairM (w0, [1,2,3], [a,b,c]) f

will do the following:

do
  w1 <- f (w0, 3, c)
  w2 <- f (w1, 2, b)
  w3 <- f (w2, 1, a)
  return w3

foldRightPairM_ :: Monad m => (w, [a], [b]) -> ((w, a, b) -> m w) -> m () Source #

Like foldRightPairM, but ignore the final result.

sequence_right :: Monad m => [m a] -> m [a] Source #

A right-to-left version of sequence: Evaluate each action in the sequence from right to left, and collect the results.

sequence_right_ :: Monad m => [m a] -> m () Source #

Same as sequence_right, but ignore the result.

Loops

We provide a syntax for "for"-style loops.

for :: Monad m => Int -> Int -> Int -> (Int -> m ()) -> m () Source #

A "for" loop. Counts from a to b in increments of s.

Standard notation:

for i = a to b by s do
  commands             
end for

Our notation:

for a b s $ \i -> do
  commands
endfor

endfor :: Monad m => m () Source #

Mark the end of a "for"-loop. This command actually does nothing, but can be used to make the loop look prettier.

foreach :: Monad m => [a] -> (a -> m b) -> m () Source #

Iterate a parameter over a list of values. It can be used as follows:

foreach [1,2,3,4] $ \n -> do
  <<<loop body depending on the parameter n>>>
endfor

The loop body will get executed once for each n ∈ {1,2,3,4}.

Operations for monads

mmap :: Monad m => (a -> b) -> m a -> m b Source #

Every monad is a functor. Input a function f : ab and output m f : m am b.

monad_join1 :: Monad m => m (a -> m b) -> a -> m b Source #

Remove an outer application of a monad from a monadic function.

Operations for disjoint unions

map_either :: (a -> b) -> (c -> d) -> Either a c -> Either b d Source #

Take two functions f : ab and g : cd, and return fg : accd.

map_eitherM :: Monad m => (a -> m b) -> (c -> m d) -> Either a c -> m (Either b d) Source #

Monadic version of map_either.

Operations for tuples

map_pair :: (a -> b) -> (c -> d) -> (a, c) -> (b, d) Source #

Take two functions f : ab and g : cd, and return f × g : a × cc × d.

map_pairM :: Monad m => (a -> m b) -> (c -> m d) -> (a, c) -> m (b, d) Source #

Monadic version of mappair.

Arithmetic operations

int_ceiling :: RealFrac a => a -> Integer Source #

A version of the ceiling function that returns an Integer.

Bit vectors

type Boollist = [Bool] Source #

The type of bit vectors. True = 1, False = 0.

boollist_of_int_bh :: Integral a => Int -> a -> Boollist Source #

Convert an integer to a bit vector. The first argument is the length in bits, and the second argument the integer to be converted. The conversion is big-headian (or equivalently, little-tailian), i.e., the head of the list holds the integer's most significant digit.

boollist_of_int_lh :: Integral a => Int -> a -> Boollist Source #

Convert an integer to a bit vector. The first argument is the length in bits, and the second argument the integer to be converted. The conversion is little-headian (or equivalently, big-tailian), i.e., the head of the list holds the integer's least significant digit.

int_of_boollist_unsigned_bh :: Integral a => Boollist -> a Source #

Convert a bit vector to an integer. The conversion is big-headian (or equivalently, little-tailian), i.e., the head of the list holds the integer's most significant digit. This function is unsigned, i.e., the integer returned is ≥ 0.

int_of_boollist_signed_bh :: Integral a => Boollist -> a Source #

Convert a bit vector to an integer, signed.

bool_xor :: Bool -> Bool -> Bool Source #

Exclusive or operation on booleans.

boollist_xor :: Boollist -> Boollist -> Boollist Source #

Exclusive or operation on bit vectors.

Formatting of lists and strings

string_of_list :: String -> String -> String -> String -> (t -> String) -> [t] -> String Source #

A general list-to-string function. Example:

string_of_list "{" ", " "}" "{}" show [1,2,3] = "{1, 2, 3}"

optional :: Bool -> String -> String Source #

optional b s: if b = True, return s, else the empty string. This function is for convenience.

Lists optimized for fast concatenation

data BList a Source #

The type of bidirectional lists. This is similar to [a], but optimized for fast concatenation and appending on both sides.

Instances

Show a => Show (BList a) # 

Methods

showsPrec :: Int -> BList a -> ShowS #

show :: BList a -> String #

showList :: [BList a] -> ShowS #

blist_of_list :: [a] -> BList a Source #

Convert a List to a BList.

list_of_blist :: BList a -> [a] Source #

Convert a BList to a List.

(+++) :: BList a -> BList a -> BList a Source #

Fast concatenation of BLists or string buffers.

blist_empty :: BList a Source #

The empty BList.

blist_concat :: [BList a] -> BList a Source #

Concatenate a list of Blists.

Strings optimized for fast concatenation

type Strbuf = BList Char Source #

A string buffer holds a string that is optimized for fast concatenation. Note that this is an instance of BList, and hence BList operations (in particular +++) can be applied to string buffers. The following functions are synonyms of the respective BList functions, and are provided for convenience.

strbuf_of_string :: String -> Strbuf Source #

Convert a string to a string buffer.

string_of_strbuf :: Strbuf -> String Source #

Convert a string buffer to a string.

strbuf_empty :: Strbuf Source #

The empty string buffer.

strbuf_concat :: [Strbuf] -> Strbuf Source #

Concatenate a list of string buffers.

The identity monad

newtype Id a Source #

The identity monad. Using m = Id gives useful special cases of monadic functions.

Constructors

Id 

Fields

Instances

Monad Id # 

Methods

(>>=) :: Id a -> (a -> Id b) -> Id b #

(>>) :: Id a -> Id b -> Id b #

return :: a -> Id a #

fail :: String -> Id a #

Functor Id # 

Methods

fmap :: (a -> b) -> Id a -> Id b #

(<$) :: a -> Id b -> Id a #

Applicative Id # 

Methods

pure :: a -> Id a #

(<*>) :: Id (a -> b) -> Id a -> Id b #

(*>) :: Id a -> Id b -> Id b #

(<*) :: Id a -> Id b -> Id a #

Identity types

data Identity a b Source #

The type Identity a b witnesses the fact that a and b are the same type. In other words, this type is non-empty if and only if a = b. This property is not guaranteed by the type system, but by the API, via the fact that the operators relexivity, symmetry, and transitivity are the only exposed constructors for this type. The implementation of this type is deliberately hidden, as this is the only way to guarantee its defining property.

Identity types are useful in certain situations. For example, they can be used to define a data type which is polymorphic in some type variable x, and which has certain constructors that are only available when x is a particular type. For example, in the declaration

data ExampleType x = Constructor1 x | Constructor2 x (Identity x Bool),

Constructor1 is available for all x, but Constructor2 is only available when x = Bool.

Instances

Show (Identity a b) # 

Methods

showsPrec :: Int -> Identity a b -> ShowS #

show :: Identity a b -> String #

showList :: [Identity a b] -> ShowS #

reflexivity :: Identity a a Source #

Witness the fact that a=a.

symmetry :: Identity a b -> Identity b a Source #

Witness the fact that a=b implies b=a.

transitivity :: Identity a b -> Identity b c -> Identity a c Source #

Witness the fact that a=b and b=c implies a=c.

identity :: Identity a b -> a -> b Source #

The identity function id : ab, provided that a and b are the same type.

Error messages

type ErrMsg = String -> String Source #

Often a low-level function, such as qcdata_zip and qcdata_promote, throws an error because of a failure of some low-level condition, such as "list too short". To produce error messages that are meaningful to user-level code, these functions do not have a hard-coded error message. Instead, they input a stub error message.

A meaningful error message typically consists of at least three parts:

  • the name of the user-level function where the error occurred, for example: "reverse_generic";
  • what the function was doing when the error occurred, for example: "operation not permitted in reversible circuit";
  • a specific low-level reason for the error, for example: "dynamic lifting".

Thus, a meaningful error message may be: "reverse_generic: operation not permitted in reversible circuit: dynamic lifting".

The problem is that the three pieces of information are not usually present in the same place. The user-level function is often a wrapper function that performs several different mid-level operations (e.g., transforming, reversing). The mid-level function knows what operation was being performed when the error occurred, but often calls a lower-level function to do the actual work (e.g., encapsulating).

Therefore, a stub error message is a function that inputs some lower-level reason for a failure (example: "list too short") and translates this into a higher-level error message (example: "qterm: shape of parameter does not data: list too short").

Sometimes, the stub error message may also ignore the low-level message and completely replace it by a higher-level one. For example, a function that implements integers as bit lists may wish to report a problem with integers, rather than a problem with the underlying lists.

The Curry type class

class Curry fun args res | args res -> fun where Source #

The Curry type class is used to implement functions that have a variable number of arguments. It provides a family of type isomorphisms

fun  ≅  args -> res,

where

fun = a1 -> a2 -> ... -> an -> res,
args = (a1, (a2, (..., (an, ())))).

Minimal complete definition

mcurry, muncurry

Methods

mcurry :: (args -> res) -> fun Source #

Multiple curry: map a function (a1, (a2, (…, ())) → b to its curried form a1a2 → … → b.

muncurry :: fun -> args -> res Source #

Multiple uncurry: map a function a1a2 → … → b to its uncurried form (a1, (a2, (…, ())) → b.

Instances

Curry b () b # 

Methods

mcurry :: (() -> b) -> b Source #

muncurry :: b -> () -> b Source #

Curry fun args res => Curry (a -> fun) (a, args) res # 

Methods

mcurry :: ((a, args) -> res) -> a -> fun Source #

muncurry :: (a -> fun) -> (a, args) -> res Source #