Control.Applicative.Successors

A value of type Succs a represents a step in a graph with nodes of type a, or in other words, a node plus the list of its successors.

The Applicative instance for Succs a is such that the node represented by a <*> b is the application of the node of a applied to the node of b, and (more importantly) the successors modeled by a <*> b are the node of a applied to the succesors of b in addition to the succesors of a applied to the node of b. This way, at most one step is taken.

>>> (++) <$> Succs "0" ["1","2"] <*> Succs "A" ["B","C"]
Succs "0A" ["1A","2A","0B", "0C"]

>>> skip x = Succs [x] [[]]
>>> getSuccs $ (concat <$> traverse skip "Hello")
["ello","Hllo","Helo","Helo","Hell"]

This applicative functor can be useful to define shrink functions for QuickCheck, using the helper

shrinkSuccs x = Succs x (shrink x)

as explained in a StackExchange answer.

Documentation

data Succs a

Constructors

Succs a [a]

Instances

Monad Succs

Methods

(>>=) :: Succs a -> (a -> Succs b) -> Succs b

(>>) :: Succs a -> Succs b -> Succs b

return :: a -> Succs a

fail :: String -> Succs a

Functor Succs

Methods

fmap :: (a -> b) -> Succs a -> Succs b

(<$) :: a -> Succs b -> Succs a

Applicative Succs

Methods

pure :: a -> Succs a

(<*>) :: Succs (a -> b) -> Succs a -> Succs b

(*>) :: Succs a -> Succs b -> Succs b

(<*) :: Succs a -> Succs b -> Succs a

Eq a => Eq (Succs a)

Methods

(==) :: Succs a -> Succs a -> Bool

(/=) :: Succs a -> Succs a -> Bool

Show a => Show (Succs a)

Methods

showsPrec :: Int -> Succs a -> ShowS

show :: Succs a -> String

showList :: [Succs a] -> ShowS

getCurrent :: Succs t -> t

Returns the represented node

Properties:

getCurrent (pure x)  == x

getCurrent (f <*> x) == (getCurrent f) (getCurrent x)

getCurrent (x >>= k) == getCurrent (k (getCurrent x))

getSuccs :: Succs t -> [t]

Returns the represented successors

getSuccs (pure x)  == []

getSuccs (f <*> x) == map ($ getCurrent x) (getSuccs f) ++ map (getCurrent f) (getSuccs x)

getSuccs (x >>= k) == map (getCurrent . k) (getSuccs x) ++ getSuccs k (getCurrent x)