Test.LeanCheck.Tiers

Utilities functions for manipulating tiers (sized lists of lists)

Additional tiers constructors

consFromList :: Listable a => ([a] -> b) -> [[b]]

Given a constructor that takes a list, return tiers of applications of this constructor.

This is equivalent to cons1.

consFromAscendingList :: Listable a => ([a] -> b) -> [[b]]

Given a constructor that takes a list with ascending elements, return tiers of applications of this constructor.

For example, a Bag represented as a list.

consFromAscendingList Bag

consFromStrictlyAscendingList :: Listable a => ([a] -> b) -> [[b]]

Given a constructor that takes a list with ascending elements, return tiers of applications of this constructor.

For example, a Set represented as a list.

consFromAscendingList Set

consFromSet :: Listable a => ([a] -> b) -> [[b]]

Given a constructor that takes a set of elements (as a list), return tiers of applications of this constructor.

For example, a Set represented as a list.

consFromAscendingList Set

consFromNoDupList :: Listable a => ([a] -> b) -> [[b]]

Given a constructor that takes a list with no duplicate elements, return tiers of applications of this constructor.

Products of tiers

product3With :: (a -> b -> c -> d) -> [[a]] -> [[b]] -> [[c]] -> [[d]]

Like productWith, but over 3 lists of tiers.

productMaybeWith :: (a -> b -> Maybe c) -> [[a]] -> [[b]] -> [[c]]

Take the product of lists of tiers by a function returning a Maybe value discarding Nothing values.

Tiers of lists

listsOf :: [[a]] -> [[[a]]]

Given tiers of values, returns tiers of lists of those values

listsOf [[]] == [[[]]]

listsOf [[x]] == [ [[]]
                 , [[x]]
                 , [[x,x]]
                 , [[x,x,x]]
                 , ...
                 ]

listsOf [[x],[y]] == [ [[]]
                     , [[x]]
                     , [[x,x],[y]]
                     , [[x,x,x],[x,y],[y,x]]
                     , ...
                     ]

ascendingListsOf :: [[a]] -> [[[a]]]

Given tiers of values, returns tiers of lists of elements in ascending order (from tiered enumeration).

strictlyAscendingListsOf :: [[a]] -> [[[a]]]

Given tiers of values, returns tiers of lists of elements in strictly ascending order (from tiered enumeration). If you only care about whether elements are in returned lists, this returns the tiers of all sets of values.

strictlyAscendingListsOf [[0],[1],[2],...] ==
  [ [[]]
  , [[0]]
  , [[1]]
  , [[0,1],[2]]
  , [[0,2],[3]]
  , [[0,3],[1,2],[4]]
  , [[0,1,2],[0,4],[1,3],[5]]
  , ...
  ]

setsOf :: [[a]] -> [[[a]]]

Returns tiers of sets represented as lists of values (no repeated sets). Shorthand for strictlyAscendingListsOf.

noDupListsOf :: [[a]] -> [[[a]]]

Given tiers of values, returns tiers of lists with no repeated elements.

noDupListsOf [[0],[1],[2],...] ==
  [ [[]]
  , [[0]]
  , [[1]]
  , [[0,1],[1,0],[2]]
  , [[0,2],[2,0],[3]]
  , ...
  ]

products :: [[[a]]] -> [[[a]]]

Generates several lists of the same size.

products [ xss, yss, zss ] ==

Tiers of all lists combining elements of tiers: xss, yss and zss

listsOfLength :: Int -> [[a]] -> [[[a]]]

Given tiers, returns tiers of lists of a given length.

deleteT :: Eq a => a -> [[a]] -> [[a]]

Delete the first occurence of an element in a tier.

For tiers without repetitions, the following holds:

deleteT x = normalizeT . (`suchThat` (/= x))

normalizeT :: [[a]] -> [[a]]

Normalizes tiers by removing an empty tier from the end of a list of tiers.

normalizeT [xs0,xs1,...,xsN,[]] = [xs0,xs1,...,xsN]

Note this will only remove a single empty tier:

normalizeT [xs0,xs1,...,xsN,[],[]] = [xs0,xs1,...,xsN,[]]

Tiers of choices

choices :: [[a]] -> [[(a, [[a]])]]

Lists tiers of all choices of values from tiers. Choices are pairs of values and tiers excluding that value.

choices [[False,True]] == [[(False,[[True]]),(True,[[False]])]]
choices [[1],[2],[3]]
  == [ [(1,[[],[2],[3]])]
     , [(2,[[1],[],[3]])]
     , [(3,[[1],[2],[]])] ]

Each choice is sized by the extracted element.

ascendingChoices :: [[a]] -> [[(a, [[a]])]]

strictlyAscendingChoices :: [[a]] -> [[(a, [[a]])]]

Like choices, but paired tiers are always strictly ascending (in terms of enumeration).

strictlyAscendingChoices [[False,True]] == [[(False,[[True]]),(True,[[]])]]
strictlyAscendingChoices [[1],[2],[3]]
  == [ [(1,[[],[2],[3]])]
     , [(2,[[],[],[3]])]
     , [(3,[[],[],[]])]
     ]