Складной экземпляр для Trie-Set

У меня есть структура данных типа Set, реализованная как Trie, с таким определением:

import qualified Data.Map as M
import Data.Foldable (Foldable, foldr)
import Prelude hiding (foldr)
import Data.Maybe (fromMaybe)

data Trie a = Trie { endHere :: Bool 
                   , getTrie :: M.Map a (Trie a)
                   } deriving (Eq)

И операция вставки, которая выглядит так:

insert :: (Ord a, Foldable f) => f a -> Trie a -> Trie a
insert = foldr f (\(Trie _ m) -> Trie True m) where
  f e a = overMap (M.alter (Just . a . fromMaybe (Trie False M.empty)) e)

overMap :: Ord b => (M.Map a (Trie a) -> M.Map b (Trie b)) -> Trie a -> Trie b
overMap f (Trie e m) = Trie e (f m)

И я могу получить разновидность foldr, которая выглядит так:

foldrTrie :: ([a] -> b -> b) -> b -> Trie a -> b
foldrTrie f i (Trie a m) = M.foldrWithKey ff s m where
  s    = if a then f [] i else i
  ff k = flip (foldrTrie $ f . (k :))

Но я не могу определить экземпляр Foldable для Trie. foldrTrie, кажется, имеет все необходимые функции, но я просто не могу понять типы.

Вот пример поведения foldr, которое я ищу:

fromList :: (Ord a, Foldable f, Foldable g) => f (g a) -> Trie a
fromList = foldr insert (Trie False M.empty)

toList :: (Ord a) => Trie a -> [[a]]
toList = foldr (:) [] -- replace foldr here with foldrTrie and you'll get the 
                      -- desired behaviour

toList (fromList ["abc", "def"]) -- ["abc","def"]

Я не могу управлять подписью типа для Foldable:

instance Foldable Trie a where

Я попытался сделать свой Trie параметром второго типа:

data Trie a (f a) = Trie { endHere :: Bool
                         , getTrie :: M.Map a (Trie a (f a))
                         } deriving (Eq)

Чтобы я мог сделать что-то вроде этого:

instance Foldable Trie a f where
  foldr f i (Trie a m) = M.foldrWithKey ff s m where
    s    = if a then f [] i else i
    ff k = flip (foldrTrie $ f . (k :))

но я не мог понять типы.

Более общий способ постановки вопроса может быть таким: если бы у меня была структура данных, которая могла бы хранить только списки, смог бы я определить foldr в этой структуре данных, чтобы он обрабатывал списки, которые он хранится как каждый элемент? Как будет выглядеть тип этой структуры данных?