一种用于Trie-Set的可折叠实例

Question

一种用于Trie-Set的可折叠实例

4

我有一个类似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函数，以使其将存储的列表视为每个元素？那么这种数据结构的类型会是什么样子呢？

- oisdk

1

实现可折叠的 Trie 实例，其中 foldr f = foldrTrie $ flip $ foldr f。我认为“Trie 只能存储可折叠的内容”这一说法没有道理。 - user2407038

这个 Trie 旨在作为一种数据结构来存储序列（或更一般地，Foldable）的 Ord 元素。存储在 Trie 中的东西必须是 Foldable，因为这是将某些东西插入到 Trie 中的唯一方法。我希望能够再次使用 foldr 访问 Trie 中的内容，保留它们类似于序列的结构。 - oisdk

我相信有很多方法来表示一个序列，但我不明白 Foldable 是如何做到的。仅使用 Foldable 接口到 Trie，我看不到编写所需函数的方法，因为 Foldable 简单地不能这样做。foldrTrie 比 foldr : (a -> b -> b) -> b -> Trie a -> b 更通用。 - user2407038

我想问的是，如果我有一个只能存储（比如）列表的数据结构，能否在该数据结构上实现 Foldable？机制方面我可以搞定（我想）；但是类型却限制了我。那么这个数据结构的类型签名会是什么样子呢？ - oisdk

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cactus · Accepted Answer

这可能不是您想要做的事情，但是您可以将通用数据结构包装成只允许在叶节点上存储列表的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