CODEWITHSUNDEEP
haskell
Chetan
Chetan

Reputation: 448

How to map over an ADT's constructor's arguments?

I have a data type (shown below in GADT form):

data Test a where
  C1 :: Int -> a -> Test a
  C2 :: Test a -> Test a -> a -> Test a
  C3 :: Test a -> a -> Test a
  ...

What I want to do, is to be able to apply some function Monoid m => Test a -> m generically to any given instance of Test a in the constructor, then mappend it all.

So for example, given f:

f :: Test a -> [Int]
f (C1 n _) = [n]
f _        = []

I'd like some function g that can map this over each constructor argument like so:

g :: Monoid m => (Test a -> m) -> Test a -> m
g f v@(C1 Int _) = f v
g f (C2 x y _)   = f x `mappend` f y
g f (C3 x _)     = f x
...

Except that I don't want to write g, I want to write a generic version of g, that can do this for any supported data type (I'm thinking GHC.Generics might be a good fit for this, but haven't been able to get the types right). i.e. I'd like to separate the actual mechanics of traversing my data structure (the repeating application of f with a mappend based fold) from the interesting bits (the terminal case of C1 in g above)

Any ideas?

Upvotes: 3

Views: 291

Answers (2)

kosmikus
kosmikus

Reputation: 19657

Looks like what you want to do is more or less exactly what the function composFold does as described in the paper "A pattern for almost compositional functions" (Section 3).

The uniplate package claims to have a compatibility layer for compos-like operations, with

composOpMonoid :: (Uniplate a, Monoid m) => (a -> m) -> a -> m

corresponding to the operation you seem to be looking for.

Upvotes: 0

luqui
luqui

Reputation: 60533

Practically, I'd look a bit deeper into GHC.Generics, and definitely read the SYB paper if you haven't.

I'll outline another approach here which is to use fixpoint types, which is a pretty slick fit for this problem.

newtype Mu f = Roll { unroll :: f (Mu f) }

-- Replace all recursive constructors with r.
-- If any of them are nonregular (e.g. C3 :: Test Int -> Test a)
-- then this approach gets quite a bit more complicated, so I hope not.
data TestF a r where
  C1 :: Int -> a -> TestF a r
  C2 :: r -> r -> a -> TestF a r
  ...

-- This will take care of finding the recursive constructors
deriving instance Foldable (TestF a) 

-- This is your actual type (might want to wrap it in a newtype)
type Test a = Mu (TestF a)

foldMapRec :: (Foldable f, Monoid m) => (Mu f -> m) -> Mu f -> m
foldMapRec f (Roll a) = foldMap f a

In practice I haven't actually gotten much use out of fixpoint types, they always seem to be more hassle than they're worth. But with PatternSynonyms now implemented I think it's somewhat nicer. Anyway, just wanted to show you this for your consideration.

Upvotes: 1

Related Questions