Given the list of Free data structures, we can sometimes incorporate one of them into an existing data structure.
For example, given some ADT for one's particular usage where some parts could be monoidic but other parts aren't..
data Foo a b = Bar a Foo b | Baz Foo a a appendIsh :: forall a b. Foo a b -> Foo a b -> Foo a b appendIsh = case _, _ of Baz foo a1 a2, Baz foo2 a3 a4 -> Baz (foo1 <> foo2) (a1 <> a3) (a2 <> a4) _, _ -> -- uh......
Monoid instance can still be created if one incorporates an encoding of the Free Monoid (e.g.
List) into the data structure itself:
data Foo a b = Bar a Foo b | Baz Foo a a | Append (Foo a b) (Foo a b) -- Tree-like `Cons` | Empty -- `Nil` instance Semigroup (Foo a b) where append = case _, _ of Baz foo a1 a2, Baz foo2 a3 a4 -> Baz (foo1 <> foo2) (a1 <> a3) (a2 <> a4) l, r -> Append l r instance Monoid (Foo a b) where mempty = Empty
This idea works for
Monoid. Incorporating other such parts from Free data structures into custom ADTs may also apply. I'm not sure whether this pattern has a name, nor what to call it if it doesn't have one.