Safe Haskell | None |
---|

- List operations
- Set and Map related operations
- XIntMaps
- Various map- and fold-like list combinators
- Monadic versions of list combinators
- Loops
- Operations for monads
- Operations for disjoint unions
- Operations for tuples
- Arithmetic operations
- Bit vectors
- Formatting of lists and strings
- Lists optimized for fast concatenation
- Strings optimized for fast concatenation
- The identity monad
- Identity types
- Error messages
- The Curry type class

This module provides miscellaneous general-purpose auxiliary functions.

## Synopsis

- applyAt :: Int -> (a -> a) -> [a] -> [a]
- overwriteAt :: Int -> a -> [a] -> [a]
- has_duplicates :: Ord a => [a] -> Bool
- substitute :: Eq a => [a] -> a -> [a] -> [a]
- map_provide :: Ord k => k -> a -> Map k a -> Map k a
- intset_inserts :: [Int] -> IntSet -> IntSet
- intmap_zip :: IntMap x -> IntMap y -> IntMap (x, y)
- intmap_zip_errmsg :: IntMap x -> IntMap y -> String -> IntMap (x, y)
- intmap_map :: (x -> y) -> IntMap x -> IntMap y
- intmap_mapM :: Monad m => (x -> m y) -> IntMap x -> m (IntMap y)
- data XIntMap a
- xintmap_delete :: Int -> XIntMap a -> XIntMap a
- xintmap_deletes :: [Int] -> XIntMap a -> XIntMap a
- xintmap_insert :: Int -> a -> XIntMap a -> XIntMap a
- xintmap_inserts :: [(Int, a)] -> XIntMap a -> XIntMap a
- xintmap_lookup :: Int -> XIntMap a -> Maybe a
- xintmap_member :: Int -> XIntMap a -> Bool
- xintmap_empty :: XIntMap a
- xintmap_freshkey :: XIntMap a -> Int
- xintmap_freshkeys :: Int -> XIntMap a -> [Int]
- xintmap_to_intmap :: XIntMap a -> IntMap a
- xintmap_size :: XIntMap a -> Int
- xintmap_dirty :: XIntMap a -> IntSet
- xintmap_reserves :: IntSet -> XIntMap a -> XIntMap a
- xintmap_unreserves :: IntSet -> XIntMap a -> XIntMap a
- xintmap_makeclean :: XIntMap a -> XIntMap a
- loop :: (Eq int, Num int) => int -> t -> (t -> t) -> t
- loop_with_index :: (Eq int, Num int) => int -> t -> (int -> t -> t) -> t
- fold_right_zip :: ((w, a, b) -> (w, c)) -> (w, [a], [b]) -> (w, [c])
- zip_strict :: [a] -> [b] -> [(a, b)]
- zip_strict_errmsg :: [a] -> [b] -> String -> [(a, b)]
- zip_rightstrict :: [a] -> [b] -> [(a, b)]
- zip_rightstrict_errmsg :: [a] -> [b] -> String -> [(a, b)]
- zipWith_strict :: (a -> b -> c) -> [a] -> [b] -> [c]
- zipWith_rightstrict :: (a -> b -> c) -> [a] -> [b] -> [c]
- loopM :: (Eq int, Num int, Monad m) => int -> t -> (t -> m t) -> m t
- loop_with_indexM :: (Eq int, Num int, Monad m) => int -> t -> (int -> t -> m t) -> m t
- zipRightWithRightStrictM :: Monad m => (a -> b -> m c) -> [a] -> [b] -> m [c]
- zipRightWithRightStrictM_ :: Monad m => (a -> b -> m c) -> [a] -> [b] -> m ()
- fold_right_zipM :: Monad m => ((w, a, b) -> m (w, c)) -> (w, [a], [b]) -> m (w, [c])
- foldRightPairM :: Monad m => (w, [a], [b]) -> ((w, a, b) -> m w) -> m w
- foldRightPairM_ :: Monad m => (w, [a], [b]) -> ((w, a, b) -> m w) -> m ()
- sequence_right :: Monad m => [m a] -> m [a]
- sequence_right_ :: Monad m => [m a] -> m ()
- for :: Monad m => Int -> Int -> Int -> (Int -> m ()) -> m ()
- endfor :: Monad m => m ()
- foreach :: Monad m => [a] -> (a -> m b) -> m ()
- mmap :: Monad m => (a -> b) -> m a -> m b
- monad_join1 :: Monad m => m (a -> m b) -> a -> m b
- map_either :: (a -> b) -> (c -> d) -> Either a c -> Either b d
- map_eitherM :: Monad m => (a -> m b) -> (c -> m d) -> Either a c -> m (Either b d)
- map_pair :: (a -> b) -> (c -> d) -> (a, c) -> (b, d)
- map_pairM :: Monad m => (a -> m b) -> (c -> m d) -> (a, c) -> m (b, d)
- int_ceiling :: RealFrac a => a -> Integer
- type Boollist = [Bool]
- boollist_of_int_bh :: Integral a => Int -> a -> Boollist
- boollist_of_int_lh :: Integral a => Int -> a -> Boollist
- int_of_boollist_unsigned_bh :: Integral a => Boollist -> a
- int_of_boollist_signed_bh :: Integral a => Boollist -> a
- bool_xor :: Bool -> Bool -> Bool
- boollist_xor :: Boollist -> Boollist -> Boollist
- string_of_list :: String -> String -> String -> String -> (t -> String) -> [t] -> String
- optional :: Bool -> String -> String
- data BList a
- blist_of_list :: [a] -> BList a
- list_of_blist :: BList a -> [a]
- (+++) :: BList a -> BList a -> BList a
- blist_empty :: BList a
- blist_concat :: [BList a] -> BList a
- type Strbuf = BList Char
- strbuf_of_string :: String -> Strbuf
- string_of_strbuf :: Strbuf -> String
- strbuf_empty :: Strbuf
- strbuf_concat :: [Strbuf] -> Strbuf
- newtype Id a = Id {
- getId :: a

- data Identity a b
- reflexivity :: Identity a a
- symmetry :: Identity a b -> Identity b a
- transitivity :: Identity a b -> Identity b c -> Identity a c
- identity :: Identity a b -> a -> b
- type ErrMsg = String -> String
- class Curry fun args res | args res -> fun where

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

:
Replace the first occurrence of `substitute`

string character replacement*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.

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

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

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_empty :: XIntMap a Source #

The empty `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_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 `zipRightWithRightStrictM`

, 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* : *a* → *b* and output
*m* *f* : *m* *a* → *m* *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* : *a* → *b* and *g* : *c* → *d*, and return
*f* ⊕ *g* : *a* ⊕ *c* → *c* ⊕ *d*.

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* : *a* → *b* and *g* : *c* → *d*, and return
*f* × *g* : *a* × *c* → *c* × *d*.

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

Monadic version of `map_pair`

.

# Arithmetic operations

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

# Bit vectors

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.

# 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}"

# Lists optimized for fast concatenation

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

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_empty :: BList a Source #

The empty `BList`

.

# Strings optimized for fast concatenation

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

The identity monad. Using *m* = `Id`

gives useful special cases
of monadic functions.

# Identity types

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`

.

reflexivity :: Identity a a Source #

Witness the fact that *a*=*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`

: *a* → *b*, 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`

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

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

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

Multiple curry: map a function
(*a*_{1}, (*a*_{2}, (…, ())) → *b*
to its curried form
*a*_{1} → *a*_{2} → … → *b*.

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

Multiple uncurry: map a function
*a*_{1} → *a*_{2} → … → *b*
to its uncurried form
(*a*_{1}, (*a*_{2}, (…, ())) → *b*.