Free-like data structure:

Here’s some playing around in a gist (I called it Gree).

It shows that to come from regular Free / have a Monad instance: you need to be able to peek under layers.

gist.github.com

https://gist.github.com/LiamGoodacre/89a6de441a158dd5f8abe890604d3aff

Main.hs

{-# OPTIONS_GHC -Wall #-}
{-# LANGUAGE GADTs, BlockArguments, LambdaCase, DerivingStrategies, UndecidableInstances #-}

module Main where

import Control.Monad.Free
import Data.Functor.Adjunction

data Gree f z where
  P :: z -> Gree f z

This file has been truncated. show original

Yet another very related variant would be the following pairing:

data Spine f i o where
  Z :: Spine f x x
  S :: Spine f i (f o) -> Spine f i o

data Spree f z where
  Spree :: Spine f i o -> i -> Spree f o

Same but different:

type Compositions :: Nat -> (Type -> Type) -> Type -> Type
type family Compositions n f x where
  Compositions 0 f x = x
  Compositions n f x = f (Compositions (n - 1) f x)

data Snee f z where
  Snee :: SNat n -> Compositions n f x -> Snee f x

^ one fun thing about this one is that it’s on display that join follows addition of the nat.

…However, all these representations are generally a pain to work with .