Control.Sized

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.

Documentation

module Control.Applicative

class Alternative f => Sized f where

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

pay

Methods

pay :: f a -> f a

Increases the cost/size of all values in the given set.

pair :: f a -> f b -> f (a, b)

Default: pair a b = (,) $ a * b.

aconcat :: [f a] -> f a

Default: aconcat = foldr (<|>) empty

fin :: Integer -> f Integer

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

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

Non-negative integers. By default, the size of an integer is the number of digits in its binary representation.

Instances

Sized Count

Defined in Control.Enumerable.Count

Methods

pay :: Count a -> Count a

pair :: Count a -> Count b -> Count (a, b)

aconcat :: [Count a] -> Count a

fin :: Integer -> Count Integer

finSized :: Integer -> Count Integer

naturals :: Count Integer

Sized Values

Defined in Control.Enumerable.Values

Methods

pay :: Values a -> Values a

pair :: Values a -> Values b -> Values (a, b)

aconcat :: [Values a] -> Values a

fin :: Integer -> Values Integer

finSized :: Integer -> Values Integer

naturals :: Values Integer

(Typeable f, Sized f) => Sized (Shareable f)

Defined in Control.Enumerable

Methods

pay :: Shareable f a -> Shareable f a

pair :: Shareable f a -> Shareable f b -> Shareable f (a, b)

aconcat :: [Shareable f a] -> Shareable f a

fin :: Integer -> Shareable f Integer

finSized :: Integer -> Shareable f Integer

naturals :: Shareable f Integer

kbits :: Sized f => Int -> f Integer