Trie-Set 的可折叠实例
Foldable instance for a 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 :))
但我无法找出 Trie
的 Foldable
实例。 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
在该数据结构上,所以它将存储的列表视为每个元素?该数据结构的类型是什么样的?
这可能不是您想做的,但您可以将通用数据结构包装到 GADT 中,该 GADT 只允许列表存储在叶子上。为简单起见,使用树而不是 Tries 的简单示例:假设通用数据结构是 Tree
,我们想要制作 LTree
,它只允许列表树:
{-# 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
我有一个类似 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 :))
但我无法找出 Trie
的 Foldable
实例。 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
在该数据结构上,所以它将存储的列表视为每个元素?该数据结构的类型是什么样的?
这可能不是您想做的,但您可以将通用数据结构包装到 GADT 中,该 GADT 只允许列表存储在叶子上。为简单起见,使用树而不是 Tries 的简单示例:假设通用数据结构是 Tree
,我们想要制作 LTree
,它只允许列表树:
{-# 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