CODEWITHSUNDEEP
haskellcategory-theoryrecursive-datastructuresfixpoint-combinators
Jeffrey Benjamin Brown
Jeffrey Benjamin Brown

Reputation: 3709

Attach extra information at every level of a recursive data type?

(This is not specifically a Haskell question.)

I have a recursive data structure. I would like to attach some kind of extra information at every level of it. Here's a simplified example, in which I'm adding either an X or a Y to every level of a tree:

import Data.Functor.Foldable

data Wrap a = X a | Y a
  deriving Show

data TreeF a b = Leaf a | TreeF a b b
  deriving Show

depth1 :: Wrap (TreeF Int ())
depth1 = X (Leaf 1)

depth2 :: Wrap (TreeF Int (Wrap (TreeF Int ())))
depth2 = Y (TreeF 1 (X $ Leaf 1) (Y $ Leaf 1))

-- depthInfinity :: Fix something something ...

(The definition of TreeF is, to me, unnatural. I would prefer to define data Tree a = Leaf a | Tree a (Tree a) (Tree a), but I can't figure out how to state my question if I do that. So instead I've written it in the form of a Base functor, ala Data.Functor.Foldable.)

The Wrap type can be used to attach the information X or Y to some kind of data. depth1' is a depth-1 TreeF in which the Wrap flag has been attached at every level (it's only got one level). depth2 is a depth-2 TreeF in which, again, the Wrap flag has been attached at every level (it's got two levels).

How can I create a "Wrapped Tree" of arbitrary depth? How should I write its type signature? Is there a category-theoretic term for this kind of data mashup?

Upvotes: 1

Views: 119

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 152707

You could use

Fix (Compose Wrap (TreeF Int))

but I probably wouldn't. If you definitely want to go the open recursion route, making your own variant of Fix is probably sanest:

data WrapData = X | Y
data LabeledFix a f = Labeled a (f (LabeledFix a f))
-- ... and then use LabeledFix WrapData (TreeF Int)

But even saner still is to just use plain old closed recursion. You don't even have to make your type any more special than it already was; just:

data Tree a = Leaf a | Branch a (Tree a) (Tree a)
-- ... and then use Tree (WrapData, Int)

Upvotes: 6

Related Questions