Subject: Folding nested foldables -- Known pattern?
From: Ivan Perez <[email-masked]>
To: Haskell Cafe <[email-masked]>
Date: Tue, 12 Jul 2022 07:09:47 -0400

Hi café

TL;DR: In Copilot, we have an ad-hoc notion of a nestable data structure
that can be folded into a list. I'm trying to rely on standard classes as
much as possible. Is there a known class to capture the idea of folding
nested data structures (e.g., transitive foldable?)

Details:

In Copilot, we have an ad-hoc notion of a nestable data structure that can
be folded. We use it to provide operations to turn nested, fixed-length
arrays into lists
<https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#flatten>.
We capture that a type class and a type family:

class Flatten <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#Flatten>
a <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043242>
b <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043241>
where  -- | Flatten an array to a list.  flatten
<https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#flatten>
:: Array <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#Array>
n <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043245>
a <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043242>
-> [b <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043241>]

-- | Association between an array and the type of the elements it
contains.type family InnerType
<https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#InnerType>
x <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043160>
where  InnerType
<https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#InnerType>
(Array <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#Array>
_ x <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043159>)
= InnerType <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#InnerType>
x <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043159>
 InnerType <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#InnerType>
x <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043158>
          = x <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043158>

That allows us to define functions such as:

-- | Total number of elements in a possibly nested array.size
<https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#size>
:: forall a <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043105>
n <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043104>
b <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043103>.
(Flatten <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#Flatten>
a <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043105>
b <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043103>,
b <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043103>
~ InnerType <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#InnerType>
a <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043105>)
=> Array <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#Array>
n <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043104>
a <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043105>
-> Intsize <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#size>
xs <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043102>
= length $ (flatten
<https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#flatten>
xs <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043102>
:: [b <https://hackage.haskell.org/package/copilot-core-3.10/docs/src/Copilot.Core.Type.Array.html#local-6989586621679043103>])

I'm trying to rely on standard classes as much as possible, ideally in base
or, if not, in libraries distributed with GHC by default, to minimize the
code we have to maintain in Copilot and facilitate future maintenance.

I know of course of Foldable. Is there a known class to capture the idea of
folding nested data structures onto lists? (something like a transitive
foldable?)

Many thanks,

Ivan