Apply a function to a specified position in a list.

Overwrite an element at a specified position in a list.

Check whether a list has duplicates.

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

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.

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

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.

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

Map a function over all values in an IntMap.

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

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

Delete a key from the XIntMap.

Delete a list of keys from a XIntMap.

Insert a new key-value pair in the XIntMap.

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

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

Check whether the given key is in the XIntMap.

The empty XIntMap.

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

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

Convert a XIntMap to an IntMap.

Return the smallest key never used in the XIntMap.

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

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.

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.

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.

Iterate a function n times. Example:

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

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

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

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

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

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

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

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

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

Monadic version of loop.

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

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.

Same as zipRightWithRightStrictM, but ignore the result.

Monadic version of fold_right_zip.

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

Like foldRightPairM, but ignore the final result.

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

Same as sequence_right, but ignore the result.

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

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

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

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

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

Take two functions f : a → b and g : c → d, and return f ⊕ g : a ⊕ c → c ⊕ d.

Monadic version of map_either.

Take two functions f : a → b and g : c → d, and return f × g : a × c → c × d.

Monadic version of map_pair.

A version of the ceiling function that returns an Integer.

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

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.

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.

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.

Convert a bit vector to an integer, signed.

Exclusive or operation on booleans.

Exclusive or operation on bit vectors.

A general list-to-string function. Example:

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

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

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

Convert a List to a BList.

Convert a BList to a List.

Fast concatenation of BLists or string buffers.

The empty BList.

Concatenate a list of BLists.

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.

Convert a string to a string buffer.

Convert a string buffer to a string.

The empty string buffer.

Concatenate a list of string buffers.

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

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 reflexivity, 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.

Witness the fact that a=a.

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

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

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

Often a low-level function, such as qcdata_zip or 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 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, ())))).