Safe Haskell | None |
---|---|
Language | Haskell98 |
Monadic combinators. Code like
f <<< xs ~~~ ys ... Stream.sum
will generate efficient GHC core for a dynamic program comparable to
sum [ f (xs!(i,k)) (ys!(k,j)) | k<-[i..j]]
.
- (#<<) :: (StreamGen m t3 (t, t1, t2), Apply (t2 -> m b)) => Fun (t2 -> m b) -> t3 -> DIM2 -> Stream m b
- (<<<) :: (StreamGen m t3 (t, t1, t2), Apply (t2 -> b)) => Fun (t2 -> b) -> t3 -> DIM2 -> Stream m b
- (|||) :: Monad m => (t -> Stream m a) -> (t -> Stream m a) -> t -> Stream m a
- (...) :: (t1 -> s) -> (s -> t) -> t1 -> t
- (..@) :: (t1 -> s) -> (t1 -> s -> t) -> t1 -> t
- makeLeft_MinRight :: (Ord head, Num head1, Num head, Monad m1, Monad m) => (head1, head) -> head -> xs -> ys -> Box (((:.) ((:.) tail head1) head2, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head2, t, t1)) (((:.) ((:.) ((:.) tail1 head) head) head, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head) head) head, t2, t3) ((:.) ((:.) ((:.) tail1 head) head) head, t2, t3))) xs ys
- makeMinLeft_Right :: (Ord head1, Ord head, Num head1, Num head, Monad m1, Monad m) => head1 -> (head, head1) -> xs -> ys -> Box (((:.) ((:.) tail head1) head1, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head1, t, t1)) (((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3))) xs ys
- (-~+) :: (Ord head, Num head1, Num head, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head1) head2, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head2, t, t1)) (((:.) ((:.) ((:.) tail1 head) head) head, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head) head) head, t2, t3) ((:.) ((:.) ((:.) tail1 head) head) head, t2, t3))) xs ys
- (+~-) :: (Ord head1, Ord head, Num head1, Num head, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head1) head1, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head1, t, t1)) (((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3))) xs ys
- (-~~) :: (Ord head, Num head1, Num head, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head1) head2, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head2, t, t1)) (((:.) ((:.) ((:.) tail1 head) head) head, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head) head) head, t2, t3) ((:.) ((:.) ((:.) tail1 head) head) head, t2, t3))) xs ys
- (~~-) :: (Ord head1, Ord head, Num head1, Num head, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head1) head1, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head1, t, t1)) (((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3))) xs ys
- (+~--) :: (Ord head1, Ord head, Num head1, Num head, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head1) head1, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head1, t, t1)) (((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3))) xs ys
- (~~~) :: (Ord head2, Num head2, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head1) head, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head, t, t1)) (((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3) ((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3))) xs ys
- (+~+) :: (Ord head2, Num head2, Num head1, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head1) head, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head, t, t1)) (((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3) ((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3))) xs ys
- (!-~+) :: (Ord head1, Ord head, Num head1, Num head, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head) head, t, t1) -> m ((:.) ((:.) ((:.) tail head) head) head, t, t1)) (((:.) ((:.) ((:.) tail1 head2) head1) head1, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head2) head1) head1, t2, t3) ((:.) ((:.) ((:.) tail1 head2) head1) head1, t2, t3))) xs ys
- (+~-!) :: (Num head2, Num head, Monad m1, Monad m, Eq head2) => xs -> ys -> Box (((:.) ((:.) tail head1) head, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head) head, t, t1)) (((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3) ((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3))) xs ys
- (-~-) :: (Num head2, Num head1, Monad m1, Monad m, Eq head2) => xs -> ys -> Box (((:.) ((:.) tail head1) head, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head, t, t1)) (((:.) ((:.) ((:.) tail1 head2) head2) head2, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head2) head2) head2, t2, t3) ((:.) ((:.) ((:.) tail1 head2) head2) head2, t2, t3))) xs ys
Apply functions to arguments.
(#<<) :: (StreamGen m t3 (t, t1, t2), Apply (t2 -> m b)) => Fun (t2 -> m b) -> t3 -> DIM2 -> Stream m b infixl 8 Source
A monadic version of the function application combinator. Applies f
which has a monadic effect.
(<<<) :: (StreamGen m t3 (t, t1, t2), Apply (t2 -> b)) => Fun (t2 -> b) -> t3 -> DIM2 -> Stream m b infixl 8 Source
Pure function application combinator. Applies f
which is pure. The
arguments to f
, meaning t
can be monadic, however!
Combine multiple right-hand sides of a non-terminal in a context-free
(|||) :: Monad m => (t -> Stream m a) -> (t -> Stream m a) -> t -> Stream m a infixl 7 Source
If both, xs
and ys
are streams of candidate answers, they can be
combined here. The answer (or sort) type of xs
and ys
has to be the
same. Works like (++)
for lists.
Reduce streams to single answers.
(...) :: (t1 -> s) -> (s -> t) -> t1 -> t infixl 6 Source
Reduces a streams of answers to the type of stored answers. The resulting type could be scalar, which it will be for highest-performance algorithms, or it could be a subset of answers stored in some kind of data structure.
(..@) :: (t1 -> s) -> (t1 -> s -> t) -> t1 -> t infixl 6 Source
Specialized version of choice function application, with a choice function that needs to know the subword index it is working on.
Combinators to chain function arguments.
General combinator creation.
makeLeft_MinRight :: (Ord head, Num head1, Num head, Monad m1, Monad m) => (head1, head) -> head -> xs -> ys -> Box (((:.) ((:.) tail head1) head2, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head2, t, t1)) (((:.) ((:.) ((:.) tail1 head) head) head, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head) head) head, t2, t3) ((:.) ((:.) ((:.) tail1 head) head) head, t2, t3))) xs ys Source
General function to create combinators. The left-hand side xs
in xs
will have a size between comb
ysminL
and maxL
, while ys
and
/everything to its right will be guaranteed minR
size.
makeMinLeft_Right :: (Ord head1, Ord head, Num head1, Num head, Monad m1, Monad m) => head1 -> (head, head1) -> xs -> ys -> Box (((:.) ((:.) tail head1) head1, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head1, t, t1)) (((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3))) xs ys Source
Create combinators which are to be used in the right-most position of a
chain. 1st, they make sure that the second to last region has a size of at
least minL
. 2nd, they constrain the last argument to a size between minR
and maxR
.
A number of often-used combinators.
(-~+) :: (Ord head, Num head1, Num head, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head1) head2, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head2, t, t1)) (((:.) ((:.) ((:.) tail1 head) head) head, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head) head) head, t2, t3) ((:.) ((:.) ((:.) tail1 head) head) head, t2, t3))) xs ys infixl 9 Source
(+~-) :: (Ord head1, Ord head, Num head1, Num head, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head1) head1, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head1, t, t1)) (((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3))) xs ys infixl 9 Source
(-~~) :: (Ord head, Num head1, Num head, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head1) head2, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head2, t, t1)) (((:.) ((:.) ((:.) tail1 head) head) head, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head) head) head, t2, t3) ((:.) ((:.) ((:.) tail1 head) head) head, t2, t3))) xs ys infixl 9 Source
(~~-) :: (Ord head1, Ord head, Num head1, Num head, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head1) head1, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head1, t, t1)) (((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3))) xs ys infixl 9 Source
(+~--) :: (Ord head1, Ord head, Num head1, Num head, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head1) head1, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head1, t, t1)) (((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3) ((:.) ((:.) ((:.) tail1 head2) head) head, t2, t3))) xs ys Source
(~~~) :: (Ord head2, Num head2, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head1) head, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head, t, t1)) (((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3) ((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3))) xs ys infixl 9 Source
(+~+) :: (Ord head2, Num head2, Num head1, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head1) head, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head, t, t1)) (((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3) ((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3))) xs ys infixl 9 Source
xs +~+ ys
with xs
and ys
non-empty. The non-emptyness constraint on
ys
works only for two arguments. With three or more arguments, a
left-leaning combinator to the right of ys
is required to establish
non-emptyness.
(!-~+) :: (Ord head1, Ord head, Num head1, Num head, Monad m1, Monad m) => xs -> ys -> Box (((:.) ((:.) tail head) head, t, t1) -> m ((:.) ((:.) ((:.) tail head) head) head, t, t1)) (((:.) ((:.) ((:.) tail1 head2) head1) head1, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head2) head1) head1, t2, t3) ((:.) ((:.) ((:.) tail1 head2) head1) head1, t2, t3))) xs ys infixl 9 Source
ls ~~~ xs !-~+ ys
with xs having a size of one and ls
further to the
left having a size of one or more.
(+~-!) :: (Num head2, Num head, Monad m1, Monad m, Eq head2) => xs -> ys -> Box (((:.) ((:.) tail head1) head, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head) head, t, t1)) (((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3) ((:.) ((:.) ((:.) tail1 head3) head2) head2, t2, t3))) xs ys infixl 9 Source
xs +~-! ys ~~~ rs
with ys
having a size of one and rs
further to the
right having a size of one.
(-~-) :: (Num head2, Num head1, Monad m1, Monad m, Eq head2) => xs -> ys -> Box (((:.) ((:.) tail head1) head, t, t1) -> m ((:.) ((:.) ((:.) tail head1) head1) head, t, t1)) (((:.) ((:.) ((:.) tail1 head2) head2) head2, t2, t3) -> m1 (Step ((:.) ((:.) ((:.) tail1 head2) head2) head2, t2, t3) ((:.) ((:.) ((:.) tail1 head2) head2) head2, t2, t3))) xs ys infixl 9 Source
xs -~- ys
produces an answer only if both xs
and ys
have size one.
The total size here then is two.