在Haskell解开结的任何好工具？

Question

我有一个具有几种不同类型的内部循环链接的数据结构,从cycle命令的意义上讲它是无限的.是否有任何有趣的模块可以将这些结构折叠成使用索引的平面数据结构？

我感兴趣的序列化完整的数据结构,既通过Read和Show以及通过Data.Serialize或相似.

构建顺序索引显然有很好的功能,但基于内存地址哈希值的索引也可以正常工作.

Answer 1

这实际上是不可能的; 从纯代码中无法检测到列表repeat 1是循环的.实际上,在Haskell的足够深奥的实现上,它甚至可能不是循环的.

这是对哈斯克尔普遍的实现技术上是可行的,但是使用一种被称为观察到的共享,¹但它是相当复杂的,除非你是一个非常有经验的程序员的Haskell,大多数时候你并不真的想解决你的问题与可观察的共享.

除非你有非常特殊的要求才能使这个好主意,否则我建议你代表你的结构直接表示的循环图; 例如,使用图形库,例如标准Data.Graph或FGL.

但是,如果您确实想尝试可观察共享,我建议使用data-reify包(如Haskell中的类型安全可观察共享中所述),它只需要一个简单的类型类实例并且具有一个安全的IO基于接口的界面; 它基本上是基于内存地址(实际上是StableNames),正如你的建议.

除非你真的需要,否则你不应该使用可观察共享的原因之一是它会破坏参照透明度; 例如,它可以让你分辨repeat 1和1 : repeat 1,甚至let xs = 1 : xs in xs和let f x = x : f x in f 1,这些依赖于编译器的优化的!

¹可观察共享背后的基本思想是公开标准Haskell实现完成的共享,基本上可以概括为"重复值不复制它们"; 所以let xs = 1:xs in xs是循环列表,因为整个的相同值用于xs它的尾部,而不是每次重新计算它,并且(\x -> (x,x)) expensive(在expensive某些长时间运行的计算中产生大的结果)只会产生两个指针expensive,而不是而不是复制thunk(这意味着,即使你强制两个字段,计算也只会进行一次,结果只会在内存中存储一​​次).

Answer 2

正如@Paul Johnson的回答中所提到的,您可以构建结构的标签版本,并使用标签作为引用结构不同部分的方法.

但是当你需要它时,你可以消除标签,留下一个优化的结构,并将所有的结打结.保留原始版本以进行序列化,但在算法需要时使用优化版本.

这是一些代码:

import Debug.Trace
import Data.Map

data Tree a name = Leaf a | Fork (Tree a name) (Tree a name) | Name name deriving Show

instance Monad (Tree a) where
    return x = Name x
    Leaf a >>= f = Leaf a
    Fork l r >>= f = Fork (l >>= f) (r >>= f)
    Name a >>= f = f a

tie :: Map String (Tree Int String) -> Map String (Tree Int ())
tie tree = let result = fmap (>>= find) tree
               find name = trace ("Looking up " ++ name) $ flip (findWithDefault (Leaf 0)) result name
           in  result

treerefs :: Map String (Tree Int String)
treerefs = ("root"  `insert` Fork (Name "left") (Name "right")) $
           ("left"  `insert` Fork (Leaf 1)      (Name "root"))  $
           ("right" `insert` Fork (Name "root") (Leaf 2))       $
           empty

trees = tie treerefs
root = findWithDefault (Leaf 0) "root" trees

p (Leaf a) = "Leaf " ++ show a
p (Fork _ _) = "Fork"
p (Name n) = "Name " ++ show n

l (Fork a _) = a
r (Fork _ b) = b

test = p (r (r (r (l (r (l (l (r (l (r (r (l root))))))))))))

注意你如何轻松地序列化,treerefs但你可以root快速遍历.我将trace调用放入,以便您可以查看名称查找的频率.它确实关闭了循环(至少在GHC中).

更通用的是,Tree您可以使用此处的方法来加速打结.(我上面的例子没有完全利用Monad实例,但我想与该论文建立联系.)与之比较loeb.