Copyright	Andrew G. Seniuk 2014-2015
License	BSD-style (see the LICENSE file)
Maintainer	Andrew Seniuk <rasfar@gmail.com>
Stability	experimental
Portability	non-portable (uses Data.Generics.Basics)
Safe Haskell	None
Language	Haskell2010

SAI.Data.Generics.Shape.SYB.Filter

Contents

Lifted result, but good structure preservation (via glue nodes)
Lifted argument, as well as result; same transformation
Unlifted result, but less structure preserved (no glue nodes)
Lifted argument, less structure preservation (no glue nodes)
Experimental, but sufficient for the task

Description

This package provides SYB shape support: generic mapping to homogeneous types, and related features. Complements existing Uniplate and TH shape libraries. See http://www.fremissant.net/shape-syb for more information.

The present module provides limited support for structure-changing transformations, some generic, others on the homogeneous types.

Synopsis

Lifted result, but good structure preservation (via glue nodes)

These functions simplify the structure by removing all possible Nothing nodes, without disrupting the lineal relations obtaining between Just nodes.

Recall that

type HomoM r = Homo (Maybe r)

and

type BiM r = Bi (Maybe r) = Homo (Dynamic, Maybe r)

See Shape.SYB for other functions involving HomoM and BiM.

filterHomoM :: (r -> Bool) -> Homo r -> HomoM r Source

Tolerate lifted nodes in the result, in exchange for better structure preservation.

Lineal ordering is preserved among Just nodes.

In the end, this is probably the most useful (unless one that takes a generic predicate, and acts on original types obtained via fromDyn[amic]...).

filterBiM :: (r -> Bool) -> Bi r -> BiM r Source

As per filterHomoM, but we string along the Dynamic component.

Lifted argument, as well as result; same transformation

Note that these functions don't take a predicate; the filtering predicate is encoded in the Maybe r input.

filterHomoMM :: HomoM r -> HomoM r Source

Tolerate lifted nodes in the result, in exchange for better structure preservation.

Lineal ordering is preserved among Just nodes.

filterBiMM :: BiM r -> BiM r Source

As per filterHomoMM, but we string along the Dynamic component.

Unlifted result, but less structure preserved (no glue nodes)

These filter functions produce trees containing only nodes which satisfy the predicate, and yet which inherit the structure of the argument to some extent.

For each node N, the algorithm acts on all children C of N which fail the predicate. The transformation is to move the grandchildren of N via C into child position, in place of C, which is elided. Recurse to fixed point. (You'd think one of bottom-up or top-down would do it in one pass, but ... maybe I did something wrong...)

Other transformations are possible; see also filterHomoM_.

filterHomo :: (r -> Bool) -> Homo r -> Homo r Source

filterHetero :: Typeable r => (r -> Bool) -> Hetero -> Hetero Source

filterBi :: (r -> Bool) -> Bi r -> Bi r Source

Lifted argument, less structure preservation (no glue nodes)

These don't require a predicate or default values, depending instead on Nothing for default, and on the predicate being encoded as Nothing / Just.

filterHomoM_ :: HomoM r -> [Homo r] Source

filterHomoM_ acts on a lifted type to avoid needing to specify any default values; however, the root node cannot be eliminated by this algorithm, so in case the root is a Nothing, we need to return its child branches as a forest.

filterHomoM_' :: r -> HomoM r -> Homo r Source

filterHomoM_ plus a root default value in the homogeneous type; this allows us to always return a single rooted tree in type Homo r. Compare to filterHomoM_ which, lacking such a root default, is obliged to return [Homo r].

Experimental, but sufficient for the task

gfilter :: forall r d. Data d => (forall d. (Data d, Typeable d) => d -> Maybe r) -> d -> [Homo r] Source

Takes a generic query (create this with mkQP), and a value, and produce the forest of trees of Just nodes. (Refer to filterHomoM_ for more details.)

gfilter_ :: forall r d. Data d => r -> (forall d. (Data d, Typeable d) => d -> Maybe r) -> d -> Homo r Source

Analogous to gfilter, but takes a default value in r and returns a single tree (instead of a forest). Uses filterHomoM_'.

mkQP :: forall r a b. (Typeable a, Typeable b) => (r -> Bool) -> (b -> Maybe r) -> a -> Maybe r Source

Would like to be able to call this automatically from gfilter, but I think the user code must call it, and pass the result to gfilter...