Unfoldable

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

Unfold the structure, always using () as elements.

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

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

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

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

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.

Always choose the first constructor.

Always choose the last constructor.

Generate all the values depth-first.

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

Generate all the values breadth-first.

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

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