Dyl*_*lan 17 haskell data-structures
如果我有一个递归ADT
data MyType = A | B | C MyType | D MyType MyType
我可以编写一个函数来确定是否MyType包含A类似的实例:
hasA :: MyType -> Bool
hasA A = True
hasA B = False
hasA (C x) = hasA x
hasA (D x y) = (hasA x) || (hasA y)
这适用于非循环实例,但它不会停止循环结构,例如
let x = C x in hasA x
相反,在这个例子中它应该返回False.在其他情况下(利用D),它将错误地停止而不是返回True.
那么,问题是我如何最容易地编写类似于hasA循环结构的函数？Racket以这种形式有一个特别好的功能define/fix,它允许你创建一个像hasA预期的那样的行为,并返回False上面例子中的结构,几乎没有任何额外的代码.有没有办法在Haskell中做类似的事情？它有延伸吗？
编辑:我现在发现define/fix实际上是由Matt Might创建的一个宏,它利用了Racket的元编程功能,而不是内置功能,但这并没有使它成为Racket的一个很棒的功能.也许这个宏可以在Haskell中重现？
Dan*_*ner 11
在Hackage上搜索的关键词是可观察的共享.这些结果中的data-reify包看起来特别相关:
data-reify提供[sic]将递归结构转换为显式图的能力.许多(隐式或显式)递归数据结构可以通过类型类实例赋予此功能.这为使用Ref进行可观察共享提供了另一种选择.