Copyright	[2016..2017] Trevor L. McDonell
License	BSD3
Maintainer	Trevor L. McDonell <tmcdonell@cse.unsw.edu.au>
Stability	experimental
Portability	non-portable (GHC extensions)
Safe Haskell	None
Language	Haskell2010

Data.Array.Accelerate.Data.Fold

Description

Combine folds in Applicative style to generate multiple results with a single pass over the array. Based on Max Rabkin's "Beautiful Folding" [1] and talks by Gabriel Gonzalez [2].

Synopsis

data Fold i o where
- Fold :: (Elt w, Monoid (Exp w)) => (i -> Exp w) -> (Exp w -> o) -> Fold i o
runFold :: (Shape sh, Elt i, Elt o) => Fold (Exp i) (Exp o) -> Acc (Array (sh :. Int) i) -> Acc (Array sh o)

Documentation

data Fold i o where #

Fold describes how to process data of some input type into some output type, via a reduction using some intermediate Monoid w. For example, both sum and length below use the Sum monoid:

sum = Fold (lift . Sum) (getSum . unlift)
length = Fold (\_ -> 1) (getSum . unlift)

The key is that Folds can be combined using Applicative in order to produce multiple outputs from a single reduction of the array. For example:

average = (/) <$> sum <*> length

This computes both the sum of the array as well as its length in a single traversal, then combines both results to compute the average.

Because Fold has some numeric instances, this can also be defined more succinctly as:

average = sum / length

A more complex example:

sumOfSquares = Fold (lift . Sum . (^2)) (getSum . unlift)
standardDeviation = sqrt ((sumOfSquares / length) - (sum / length) ^ 2)

These will all execute with a single reduction kernel and a single map to summarise (combine) the results.

Constructors

Fold :: (Elt w, Monoid (Exp w)) => (i -> Exp w) -> (Exp w -> o) -> Fold i o

Instances

Functor (Fold i) #
Instance details Defined in Data.Array.Accelerate.Data.Fold Methods fmap :: (a -> b) -> Fold i a -> Fold i b # (<$) :: a -> Fold i b -> Fold i a #
Applicative (Fold i) #
Instance details Defined in Data.Array.Accelerate.Data.Fold Methods pure :: a -> Fold i a # (<>) :: Fold i (a -> b) -> Fold i a -> Fold i b # liftA2 :: (a -> b -> c) -> Fold i a -> Fold i b -> Fold i c # (>) :: Fold i a -> Fold i b -> Fold i b # (<*) :: Fold i a -> Fold i b -> Fold i a #
Floating b => Floating (Fold a (Exp b)) #
Instance details Defined in Data.Array.Accelerate.Data.Fold Methods pi :: Fold a (Exp b) # exp :: Fold a (Exp b) -> Fold a (Exp b) # log :: Fold a (Exp b) -> Fold a (Exp b) # sqrt :: Fold a (Exp b) -> Fold a (Exp b) # (**) :: Fold a (Exp b) -> Fold a (Exp b) -> Fold a (Exp b) # logBase :: Fold a (Exp b) -> Fold a (Exp b) -> Fold a (Exp b) # sin :: Fold a (Exp b) -> Fold a (Exp b) # cos :: Fold a (Exp b) -> Fold a (Exp b) # tan :: Fold a (Exp b) -> Fold a (Exp b) # asin :: Fold a (Exp b) -> Fold a (Exp b) # acos :: Fold a (Exp b) -> Fold a (Exp b) # atan :: Fold a (Exp b) -> Fold a (Exp b) # sinh :: Fold a (Exp b) -> Fold a (Exp b) # cosh :: Fold a (Exp b) -> Fold a (Exp b) # tanh :: Fold a (Exp b) -> Fold a (Exp b) # asinh :: Fold a (Exp b) -> Fold a (Exp b) # acosh :: Fold a (Exp b) -> Fold a (Exp b) # atanh :: Fold a (Exp b) -> Fold a (Exp b) # log1p :: Fold a (Exp b) -> Fold a (Exp b) # expm1 :: Fold a (Exp b) -> Fold a (Exp b) # log1pexp :: Fold a (Exp b) -> Fold a (Exp b) # log1mexp :: Fold a (Exp b) -> Fold a (Exp b) #
Fractional b => Fractional (Fold a (Exp b)) #
Instance details Defined in Data.Array.Accelerate.Data.Fold Methods (/) :: Fold a (Exp b) -> Fold a (Exp b) -> Fold a (Exp b) # recip :: Fold a (Exp b) -> Fold a (Exp b) # fromRational :: Rational -> Fold a (Exp b) #
Num b => Num (Fold a (Exp b)) #
Instance details Defined in Data.Array.Accelerate.Data.Fold Methods (+) :: Fold a (Exp b) -> Fold a (Exp b) -> Fold a (Exp b) # (-) :: Fold a (Exp b) -> Fold a (Exp b) -> Fold a (Exp b) # (*) :: Fold a (Exp b) -> Fold a (Exp b) -> Fold a (Exp b) # negate :: Fold a (Exp b) -> Fold a (Exp b) # abs :: Fold a (Exp b) -> Fold a (Exp b) # signum :: Fold a (Exp b) -> Fold a (Exp b) # fromInteger :: Integer -> Fold a (Exp b) #

runFold :: (Shape sh, Elt i, Elt o) => Fold (Exp i) (Exp o) -> Acc (Array (sh :. Int) i) -> Acc (Array sh o) #

Apply a Fold to an array.