Data.Unfoldable

Documentation

class Unfoldable f where

Data structures that can be unfolded.

For example, given a data type

 data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

a suitable instance would be

 instance Unfoldable Tree where
   unfoldMap f = choose
     [ spread $ pure Empty
     , spread $ Leaf <$> to f
     , spread $ Node <$> to (unfoldMap f) <*> to f <*> to (unfoldMap f)
     ]

i.e. it follows closely the instance for Traversable, with the addition of choose, spread and to.

The instance can be simplified to:

 instance Unfoldable Tree where
   unfoldMap f = choose
     [ const Empty
     , Leaf . f
     , spread $ Node <$> to (unfoldMap f) <*> to f <*> to (unfoldMap f)
     ]

Methods

unfoldMap :: Splittable s => (s -> a) -> s -> f a

Given a function to generate an element from a seed, and an initial seed, generate a structure.

Instances

Unfoldable []

Unfoldable Maybe

Unfoldable Identity

(Bounded a, Enum a) => Unfoldable (Either a)

(Bounded a, Enum a) => Unfoldable ((,) a)

Unfoldable f => Unfoldable (Reverse f)

(Bounded a, Enum a) => Unfoldable (Constant a)

(Unfoldable p, Unfoldable q) => Unfoldable (Compose p q)

(Unfoldable p, Unfoldable q) => Unfoldable (Product p q)

Specific unfolds

unfold :: (Unfoldable f, Splittable s) => s -> f s

The same as unfoldMap id.

leftMost :: Unfoldable f => f ()

Always choose the first constructor.

rightMost :: Unfoldable f => f ()

Always choose the last constructor.

Helper functions

spread :: Splittable s => State ([s], Int) a -> s -> a

Count the number of times to is used, and split the seed in that many parts.

to :: (s -> a) -> State ([s], Int) a

Signal to spread that this is a subpart that needs a seed.