Defining a seemingly simple Foldable instance

Question

What would the Foldable instance for this datatype look like?

data X t = X t [X t]

I tried this:

instance Foldable X where
    foldMap f (X x xs) = f x `mappend` foldMap f xs

But got this error:

Occurs check: cannot construct the infinite type: a = X a
When generalising the type(s) for `foldMap'
In the instance declaration for `Foldable X'

Answer 1

xs is a list of items and foldMap needs to be applied to the individual items, not the list itself. Doing this with map gives a list of results that can be combined with mconcat:

instance Foldable X where
  foldMap f (X x xs) = f x `mappend` mconcat (map (foldMap f) xs)