| Safe Haskell | Safe |
|---|---|
| Language | Haskell2010 |
Control.Sized
Description
This module provides the Sized class. Instances of this class are typically collection data types for infinite sets of values with a finite number of values of any given size.
A simple example is Control.Enumerable.Count that just counts the number of values of each size. Control.Enumerable.Values provides all values of a given size. FEAT provides any value in the set much more efficiently.
- module Control.Applicative
- class Alternative f => Sized f where
- kbits :: Sized f => Int -> f Integer
Documentation
module Control.Applicative
class Alternative f => Sized f where Source #
A sized functor is an applicative functor extended with a notion of cost/size of contained values. This is useful for any type of bounded recursion over infinite sets, most notably for various kind of enumerations.
The intention is that every sized functor definition models a (usually) infinite set (technically a bag) with a finite number of values of any given size. As long as every cyclic (recursive) definition has at least one application of pay, this invariant is guaranteed.
The module Control.Enumerable provides sized functor definitions for a lot of data types, such that the size of a value is the number of constructor applications it contains. It also allows deriving these functors for any user defined data type (using Template Haskell).
Minimal complete definition
Methods
Increases the cost/size of all values in the given set.
pair :: f a -> f b -> f (a, b) Source #
aconcat :: [f a] -> f a Source #
Default: aconcat = foldr (<|>) empty
fin :: Integer -> f Integer Source #
Finite numeric types. fin n contains all non-negative numbers below n. This definition is flat, all integers have the same size.
Implementing this function efficiently will have a great impact on applications that use a lot of bounded numeric types (e.g. Int).
Default: aconcat (map pure [0..n-1])
finSized :: Integer -> f Integer Source #
Same as fin but the size of values may differ.
By default, the size of an integer is the number of significant bits in its binary representation. In other words, 0 has size zero, the values for size k>0 in finBits n are in the interval
(2^(k-1),min (2^k-1) n).
naturals :: f Integer Source #
Non-negative integers. By default, the size of an integer is the number of digits in its binary representation.