Safe Haskell | None |
---|

This module provides the GTA framework on join lists, such as definitions of the data structure and its algebra, parallel/serial generators, aggregators, etc.

- data JoinList a
- data JoinListAlgebra b a = JoinListAlgebra {}
- joinize :: forall a. [a] -> JoinList a
- dejoinize :: forall a. JoinList a -> [a]
- segs :: [a] -> Semiring a s -> s
- inits :: [a] -> Semiring a s -> s
- tails :: [a] -> Semiring a s -> s
- subs :: [a] -> Semiring a s -> s
- assigns :: [m] -> [a] -> Semiring (m, a) s -> s
- paths :: BinTree a a -> Semiring a s -> s
- assignsBy :: (a -> [m]) -> [a] -> Semiring (m, a) s -> s
- mapJ :: forall b a. (b -> a) -> JoinListMapFs b a
- count :: Num a => Semiring b a
- maxsum :: (Ord a, Num a) => Semiring a (AddIdentity a)
- maxsumsolution :: (Ord a, Num a) => Semiring a (AddIdentity a, Bag (JoinList a))
- maxsumWith :: (Ord a, Num a) => (b -> a) -> Semiring b (AddIdentity a)
- maxsumKWith :: (Ord a, Num a) => Int -> (b -> a) -> Semiring b [AddIdentity a]
- maxsumsolutionXKWith :: (Ord a, Num a) => Semiring c b -> Int -> (c -> a) -> Semiring c [(AddIdentity a, b)]
- maxsumsolutionXWith :: (Ord a, Num a) => Semiring c b -> (c -> a) -> Semiring c (AddIdentity a, b)
- maxsumsolutionWith :: (Ord a, Num a) => (b -> a) -> Semiring b (AddIdentity a, Bag (JoinList b))
- maxsumsolutionKWith :: (Ord a, Num a) => Int -> (b -> a) -> Semiring b [(AddIdentity a, Bag (JoinList b))]
- maxprodWith :: (Ord a, Num a) => (b -> a) -> Semiring b (AddIdentity a)
- maxprodKWith :: (Ord a, Num a) => Int -> (b -> a) -> Semiring b [AddIdentity a]
- maxprodsolutionXKWith :: (Ord a, Num a) => Semiring c b -> Int -> (c -> a) -> Semiring c [(AddIdentity a, b)]
- maxprodsolutionXWith :: (Ord a, Num a) => Semiring c b -> (c -> a) -> Semiring c (AddIdentity a, b)
- maxprodsolutionWith :: (Ord a, Num a) => (b -> a) -> Semiring b (AddIdentity a, Bag (JoinList b))
- maxprodsolutionKWith :: (Ord a, Num a) => Int -> (b -> a) -> Semiring b [(AddIdentity a, Bag (JoinList b))]
- segsP :: NFData s => [a] -> Semiring a s -> s
- initsP :: NFData s => [a] -> Semiring a s -> s
- tailsP :: NFData s => [a] -> Semiring a s -> s
- subsP :: NFData s => [a] -> Semiring a s -> s
- assignsP :: NFData s => [m] -> [a] -> Semiring (m, a) s -> s
- assignsByP :: NFData s => (a -> [m]) -> [a] -> Semiring (m, a) s -> s
- crossConcat :: Bag (JoinList a) -> Bag (JoinList a) -> Bag (JoinList a)
- bagOfSingleton :: a -> Bag (JoinList a)
- emptyBag :: Bag (JoinList a)
- bagOfNil :: Bag (JoinList a)
- bagUnion :: Bag (JoinList a) -> Bag (JoinList a) -> Bag (JoinList a)
- type Semiring a s = GenericSemiring (JoinListAlgebra a) s
- prop_Associativity :: Eq b => JoinListAlgebra a b -> (b, b, b) -> Bool
- prop_Identity :: Eq b => JoinListAlgebra a b -> b -> Bool
- data JoinListMapFs b b'
- homJ :: (a -> a -> a) -> (b -> a) -> a -> JoinList b -> a
- homJ' :: (a -> a -> a) -> (b -> a) -> a -> JoinListAlgebra b a
- mapMap :: (b -> b') -> GenericSemiring (JoinListAlgebra b') a -> GenericSemiring (JoinListAlgebra b) a
- perms :: [a] -> Semiring a s -> s
- permsP :: NFData s => [a] -> Semiring a s -> s

# Documentation

Join lists.

x ++ y ==> x `Times` y [a] ==> Single a [] ==> Nil

We assume that `Times`

is associative and `Nil`

is its identity:

x `Times` (y `Times` z) == (x `Times` y) `Times` z x `Times` Nil == Nil `Times` x == x

Eq a => Eq (JoinList a) | |

Ord a => Ord (JoinList a) | |

Read a => Read (JoinList a) | |

Show a => Show (JoinList a) | |

NFData a => NFData (JoinList a) | |

GenericSemiringStructure (JoinListAlgebra b) (JoinList b) (JoinListMapFs b) | Instance declaration of GTA.Data.GenericSemiringStructure for join lists. The implementation is quite straightforward. This can be generated automatically by |

data JoinListAlgebra b a Source

The algebra of join lists.

We assume that `times`

is associative and `nil`

is its identity, inheriting those of `Times`

and `Nil`

:

x `times` (y `times` z) == (x `times` y) `times` z x `times` nil == nil `times` x == x

This can be generated automatically by `genAllDecl ''JoinList`

.

GenericSemiringStructure (JoinListAlgebra b) (JoinList b) (JoinListMapFs b) | Instance declaration of GTA.Data.GenericSemiringStructure for join lists. The implementation is quite straightforward. This can be generated automatically by |

segs :: [a] -> Semiring a s -> sSource

This generates all segments (continuous subsequences) of a given list.

For example,

`>>>`

Bag [[1],[2],[3],[2,3],[1,2],[1,2,3],[]]`segs [1,2,3] `aggregateBy` result`

inits :: [a] -> Semiring a s -> sSource

This generates all prefixes of a given list.

For example,

`>>>`

Bag [[],[1],[1,2],[1,2,3]]`inits [1,2,3] `aggregateBy` result`

tails :: [a] -> Semiring a s -> sSource

This generates all suffixes of a given list.

For example,

`>>>`

Bag [[1,2,3],[2,3],[3],[]]`tails [1,2,3] `aggregateBy` result`

subs :: [a] -> Semiring a s -> sSource

This generates all subsequences of a given list.

For example,

`>>>`

Bag [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]`subs [1,2,3] `aggregateBy` result`

assigns :: [m] -> [a] -> Semiring (m, a) s -> sSource

This generates all assignments of elements of the first list to elements of the second list.

For example,

`>>>`

Bag [[(True,1),(True,2),(True,3)],[(True,1),(True,2),(False,3)],[(True,1),(False,2),(True,3)],[(True,1),(False,2),(False,3)],[(False,1),(True,2),(True,3)],[(False,1),(True,2),(False,3)],[(False,1),(False,2),(True,3)],[(False,1),(False,2),(False,3)]]`assigns [True,False] [1,2,3] `aggregateBy` result`

paths :: BinTree a a -> Semiring a s -> sSource

This generates all paths from the root to leaves of a given binary tree.

For example,

`>>>`

Bag [[1,2],[1,3,4],[1,3,5]]`*Main GTA.Data.BinTree> paths (BinNode 1 (BinLeaf 2) (BinNode 3 (BinLeaf 4) (BinLeaf 5))) `aggregateBy` result`

assignsBy :: (a -> [m]) -> [a] -> Semiring (m, a) s -> sSource

This is a generalization of `assigns`

: the values to be assigned is dependent of the target.

For example,

`>>>`

Bag [[(True,1),(True,2),(True,3)],[(True,1),(True,2),(False,3)],[(False,1),(True,2),(True,3)],[(False,1),(True,2),(False,3)]]`assignsBy (\a -> if odd a then [True, False] else [True]) [1,2,3] `aggregateBy` result`

mapJ :: forall b a. (b -> a) -> JoinListMapFs b aSource

Wrapper for `JoinListMapFs`

.

maxsumsolution :: (Ord a, Num a) => Semiring a (AddIdentity a, Bag (JoinList a))Source

The aggregator to find items with the maximum sum.

maxsumWith :: (Ord a, Num a) => (b -> a) -> Semiring b (AddIdentity a)Source

The aggregator to take the maximum sum after `map f`

.

maxsumKWith :: (Ord a, Num a) => Int -> (b -> a) -> Semiring b [AddIdentity a]Source

The *best-k* extension of `maxsumWith`

.

maxsumsolutionXKWith :: (Ord a, Num a) => Semiring c b -> Int -> (c -> a) -> Semiring c [(AddIdentity a, b)]Source

The *best-k* extension of `maxsumsolutionXWith`

.

maxsumsolutionXWith :: (Ord a, Num a) => Semiring c b -> (c -> a) -> Semiring c (AddIdentity a, b)Source

The tupling of maxsumsolution and a given semiring. The second component is the aggregation of the maximum items by the given semiring.

maxsumsolutionWith :: (Ord a, Num a) => (b -> a) -> Semiring b (AddIdentity a, Bag (JoinList b))Source

The aggregator to find items with the maximum sum after `map f`

.

maxsumsolutionKWith :: (Ord a, Num a) => Int -> (b -> a) -> Semiring b [(AddIdentity a, Bag (JoinList b))]Source

The *best-k* extension of `maxsumsolutionWith`

.

maxprodWith :: (Ord a, Num a) => (b -> a) -> Semiring b (AddIdentity a)Source

The aggregator to take the maximum product of *non-negative* numbers after `map f`

.

maxprodKWith :: (Ord a, Num a) => Int -> (b -> a) -> Semiring b [AddIdentity a]Source

The *best-k* extension of `maxprodWith`

.

maxprodsolutionXKWith :: (Ord a, Num a) => Semiring c b -> Int -> (c -> a) -> Semiring c [(AddIdentity a, b)]Source

The *best-k* extension of `maxprodsolutionXWith`

.

maxprodsolutionXWith :: (Ord a, Num a) => Semiring c b -> (c -> a) -> Semiring c (AddIdentity a, b)Source

The tupling of maxprodsolution and a given semiring. The second component is the aggregation of the maximum items by the given semiring.

maxprodsolutionWith :: (Ord a, Num a) => (b -> a) -> Semiring b (AddIdentity a, Bag (JoinList b))Source

The aggregator to find items with the maximum product. The numbers have to be *non-negative*.

maxprodsolutionKWith :: (Ord a, Num a) => Int -> (b -> a) -> Semiring b [(AddIdentity a, Bag (JoinList b))]Source

The *best-k* extension of `maxprodsolutionWith`

.

assignsByP :: NFData s => (a -> [m]) -> [a] -> Semiring (m, a) s -> sSource

Parallel version of `assignsBy`

.

crossConcat :: Bag (JoinList a) -> Bag (JoinList a) -> Bag (JoinList a)Source

Constructor of a bag of join lists.

For example,

`>>>`

Bag [[1,2,4,5],[1,2,6],[3,4,5],[3,6]]`(bag (map joinize [[1,2], [3]])) `crossConcat` (bag (map joinize [[4,5], [6]]))`

bagOfSingleton :: a -> Bag (JoinList a)Source

Constructor of a bag of join lists.

For example,

`>>>`

Bag [[1]]`bagOfSingleton 1`

emptyBag :: Bag (JoinList a)Source

Constructor of a bag of join lists.

For example,

`>>>`

Bag []`emptyBag`

bagOfNil :: Bag (JoinList a)Source

Constructor of a bag of join lists.

For example,

`>>>`

Bag [[]]`bagOfNil`

bagUnion :: Bag (JoinList a) -> Bag (JoinList a) -> Bag (JoinList a)Source

Constructor of a bag of join lists.

For example,

`>>>`

Bag [[1,2],[3],[4,5],[6]]`(bag (map joinize [[1,2], [3]])) `bagUnion` (bag (map joinize [[4,5], [6]]))`

type Semiring a s = GenericSemiring (JoinListAlgebra a) sSource

The usual semiring is a generic semiring of join lists:

a `times` (b `oplus` c) == (a `times` b) `oplus` (a `times` c) (a `oplus` b) `times` c == (a `times` c) `oplus` (b `times` c) a `times` identity == identity `times` a == identity

prop_Associativity :: Eq b => JoinListAlgebra a b -> (b, b, b) -> BoolSource

Property of `times`

of a JoinListAlgebra:

x `times` (y `times` z) == (x `times` y) `times` z

prop_Identity :: Eq b => JoinListAlgebra a b -> b -> BoolSource

data JoinListMapFs b b' Source

A record to hold a function to be applied to elements of a list.

This can be generated automatically by `genAllDecl ''JoinList`

.

GenericSemiringStructure (JoinListAlgebra b) (JoinList b) (JoinListMapFs b) | Instance declaration of GTA.Data.GenericSemiringStructure for join lists. The implementation is quite straightforward. This can be generated automatically by |

homJ :: (a -> a -> a) -> (b -> a) -> a -> JoinList b -> aSource

A wrapper function for JoinList homomorphism.

homJ' :: (a -> a -> a) -> (b -> a) -> a -> JoinListAlgebra b aSource

A fake function of homJ to build `JoinListAlgebra`

instead of executing the homomorphism with it.

mapMap :: (b -> b') -> GenericSemiring (JoinListAlgebra b') a -> GenericSemiring (JoinListAlgebra b) aSource

A transfomer that applies given function to every element in every list in a given bag.

perms :: [a] -> Semiring a s -> sSource

This generates all permutations of a given list.

For example,

`>>>`

Bag ["hoge","hoeg","ohge","oheg","hgoe","hgeo","ghoe","gheo","heog","hego","ehog","ehgo","oghe","ogeh","gohe","goeh","oehg","oegh","eohg","eogh","geho","geoh","egho","egoh"]`perms "hoge" `aggregateBy` result`