derivatives of ADTs are their zippers

zippers.hs

-- list derivation
-- data [a] = [] | a : [a]
{-
  l = 1 + a ⋅ l
  l - a ⋅ l = 1
  l (1 - a) = 1
  
  l = (1 - a)⁻¹

  ∂l = -1 ⋅ -(1 - a)⁻²
     = l²
-}
type ZipList a = ([a], [a])


-- rose tree derivation
data Rose a = Node a [Rose a]
{-
  r = a ⋅ (l∘r)
  ∂r = ∂a ⋅ (l∘r) + a ⋅ ∂(l∘r)
     = (l∘r) + a ⋅ ∂ᵣl ⋅ ∂r
     = (l∘r) + a ⋅ (l∘r)² ⋅ ∂r -- recursive def

  ∂r - a ⋅ (l∘r)² ⋅ ∂r = (l∘r)
  ∂r (1 - a(l∘r)²) = (l∘r)
  ∂r = (l∘r) / (1 - a(l∘r)²) -- this is a pair of a rose list,
                                and a list of rose-list-zippers
-}
newtype ZipRoseR a = MkZipRoseR
  (Either [Rose a] ((a, [Rose a], [Rose a]), ZipRoseR a))

type ZipRose a = ([Rose a], [(a, [Rose a], [Rose a])])