Foldable instance for a Trie-Set

Question

I have a Set-like data structure, implemented as a Trie, with a definition like this:

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)

And an insert operation that looks like this:

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)

And I can get a kind of foldr that looks like this:

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 :))

But I can't figure out the Foldable instance for Trie. The foldrTrie seems to have all of the necessary functionality, but I just can't figure out the types.

Here's an example of the foldr behaviour I'm looking for:

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"]

What I can't manage is the type signature for Foldable:

instance Foldable Trie a where

I tried making my Trie have a second type parameter:

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

So that I might be able to do something like this:

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 :))

but I couldn't figure out the types.

A more general way to frame the question might be like this: if I had a data structure which could store only lists, would I be able to define foldr on that data structure, so it treated the lists it stored as each element? What would the type for that data structure look like?

Answer 1

This is probably not what you want to do, but you could wrap a generic data structure into a GADT that only allows lists to be stored on the leafs. Simple example using trees instead of Tries for simplicity's sake: suppose the generic data structure is Tree, and we want to make LTree which only allows trees of lists:

{-# LANGUAGE GADTs #-}

import Prelude hiding (foldr)
import Data.Foldable
import Data.Tree

foldrForListTrees :: ([a] -> b -> b) -> b -> Tree [a] -> b
foldrForListTrees = error "This is the one you are supposed to be able to write"

data LTree a where
    MkLTree :: Tree [a] -> LTree [a]

instance Foldable LTree where
    foldr f ys0 (MkLTree xs) = foldrForListTrees f ys0 xs