Data.Unfoldable

Class of data structures that can be unfolded.

Unfoldable

class Unfoldable t 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
  unfold fa = choose
    [ pure Empty
    , Leaf <$> fa
    , Node <$> unfold fa <*> fa <*> unfold fa
    ]

i.e. it follows closely the instance for Traversable, but instead of matching on an input value, we choose from a list of all cases.

Instead of manually writing the Unfoldable instance, you can add a deriving Generic1 to your datatype and declare an Unfoldable instance without giving a definition for unfold.

For example the previous example can be simplified to just:

{-# LANGUAGE DeriveGeneric #-}

import GHC.Generics

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

instance Unfoldable Tree

Methods

unfold :: Unfolder f => f a -> f (t a)

Given a way to generate elements, return a way to generate structures containing those elements.

unfold :: (ADT1 t, Constraints1 t Unfoldable, Unfolder f) => f a -> f (t a)

Given a way to generate elements, return a way to generate structures containing those elements.

Instances

Unfoldable []

Methods

unfold :: Unfolder f => f a -> f [a]

Unfoldable Maybe

Methods

unfold :: Unfolder f => f a -> f (Maybe a)

Unfoldable Identity

Methods

unfold :: Unfolder f => f a -> f (Identity a)

Unfoldable Tree

Methods

unfold :: Unfolder f => f a -> f (Tree a)

Unfoldable Seq

Methods

unfold :: Unfolder f => f a -> f (Seq a)

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

Methods

unfold :: Unfolder f => f a -> f (Either a a)

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

Methods

unfold :: Unfolder f => f a -> f (a, a)

Unfoldable f => Unfoldable (Reverse * f)

Methods

unfold :: Unfolder f => f a -> f (Reverse * f a)

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

Methods

unfold :: Unfolder f => f a -> f (Constant * a a)

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

Methods

unfold :: Unfolder f => f a -> f (Product * p q a)

(Unfoldable p, Unfoldable q) => Unfoldable (Sum * p q)

Methods

unfold :: Unfolder f => f a -> f (Sum * p q a)

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

Methods

unfold :: Unfolder f => f a -> f (Compose * * p q a)

unfold_ :: (Unfoldable t, Unfolder f) => f (t ())

Unfold the structure, always using () as elements.

unfoldBF :: (Unfoldable t, Unfolder f) => f a -> f (t a)

Breadth-first unfold, which orders the result by the number of choose calls.

unfoldBF_ :: (Unfoldable t, Unfolder f) => f (t ())

Unfold the structure breadth-first, always using () as elements.

Specific unfolds

unfoldr :: Unfoldable t => (b -> Maybe (a, b)) -> b -> Maybe (t a)

unfoldr builds a data structure from a seed value. It can be specified as:

unfoldr f z == fromList (Data.List.unfoldr f z)

fromList :: Unfoldable t => [a] -> Maybe (t a)

Create a data structure using the list as input. This can fail because there might not be a data structure with the same number of element positions as the number of elements in the list.

leftMost :: Unfoldable t => Maybe (t ())

Always choose the first constructor.

rightMost :: Unfoldable t => Maybe (t ())

Always choose the last constructor.

allDepthFirst :: Unfoldable t => [t ()]

Generate all the values depth-first.

allToDepth :: Unfoldable t => Int -> [t ()]

Generate all the values upto a given depth, depth-first.

allBreadthFirst :: Unfoldable t => [t ()]

Generate all the values breadth-first.

randomDefault :: (Random a, RandomGen g, Unfoldable t) => g -> (t a, g)

Generate a random value, can be used as default instance for Random.

arbitraryDefault :: (Arbitrary a, Unfoldable t) => Gen (t a)

Provides a QuickCheck generator, can be used as default instance for Arbitrary.