哈斯克尔 - 嵌套空列表

阅读http://learnyouahaskell.com/当我的一个朋友想出了一个问题：

是否有可能在Haskell写一个递归函数，提供真正的，如果所有的子-sub -_-子列表为空。我的第一个猜想是 - 应该是 - 但是我写了一个类型注释的问题很大。

他试图像

nullRec l = if null l 
       then True 
       else if [] `elem` l 
        then nullRec (head [l]) && nullRec (tail l) 
        else False

这是 - 不工作 - :-)

我想出了类似

与CONCAT折叠 - 获得AA单一长串
（给我执行问题）
或制作无限树状数据类型 - 并且使这个从列表
（尚未实施）

但后者听起来有点像矫枉过正这个问题。什么是你的想法 - 在这样;-)

感谢晴朗的周日提前

为所有评论的反应 - 这是不好的风格，我想补充这只是一个实验！
不要在家里试试！ ;-)

来源

2011-07-10 epsilonhalbe

想想这种函数的类型应该是什么（如果您在普通列表上实现它）！ – yatima2975

我想到了 - 它应该是无限的[[... [a] ...]]，但这不可能在哈斯克尔写下来 - 这就是为什么我想出了第二种方法。但有没有更简单的方法来做到这一点。另外我的大脑有点慢，因为我今天生病了。 – epsilonhalbe

生病与否，你走在正确的轨道上！编写一系列函数'nullRec2 :: [[a]] - > Bool'，'nullRec3 :: [[a]] - > Bool'等很简单（尝试一下！），但是你无法让他们轻松适应单一类型签名。您可能需要树型数据，如'数据树a =分支[树a] |节点a'或者可能有类型类的东西（对此方法还没有多少考虑）。 – yatima2975

一个typeclass怎么样？

{-# LANGUAGE FlexibleInstances, OverlappingInstances #-} 

class NullRec a where 
    nullRec :: a -> Bool 

instance NullRec a => NullRec [a] where 
    nullRec [] = True 
    nullRec ls = all nullRec ls 

instance NullRec a where 
    nullRec _ = False 

main = print . nullRec $ ([[[[()]]]] :: [[[[()]]]])

来源

2011-07-10 15:34:52 fuz

更确切地说，您不仅使用类型类别，而且还使用GHC扩展[OverlappingInstances]（http://www.haskell.org/ghc/docs/7.0.4/html/users_guide/type-class-extensions.html ＃实例重叠）。没有这个扩展，即使使用类型类也无法达到问题中所要求的。这强烈表明，如果有人需要实施这个（除了作为实验），该计划可能没有以正确的方式设计。 –

这是不可能使用参数多态性，因为以下原因。

考虑这些值：

x = [8] :: [Int] 
y = [3.0] :: [Double] 
z = [[]] :: [[Int]]

很显然，你希望你的功能，既x和y工作，因此它的类型必须是null1 :: [a] -> Bool。（有人可以帮我做这个说法看起来正式了吗？我怎么能证明这是唯一的最具体的上下文较少型unifiable与[Int] -> Bool和[Double] -> Bool？有没有类型之间的关系的名字吗？）

现在，如果你有这种类型，那么null1 z将等于null1 x，因为它们只在列表元素的值不同，而这些元素从抽象出来。 （甚至还没有接近再次形式化证明:(）

你想为z什么是null2 :: [[a]] -> Bool，这将在行为上有所不同，从而使null1和null2相同的名称将需要重载。（请参阅FUZxxl的答案）

来源

2011-07-10 16:03:25 Rotsor

我觉得这个观点相当有说服力。 – luqui

我觉得'null1。（：[]）:: a - > Bool'使我们更接近形式证明，但我仍然不知道如何做出最后一步（显示'a - > Bool'与'Bool'相同）。 – Rotsor

这是一种相反的自由定理，但是'Int'和'Double'的最大下界（在Haskell上下文无关类型的格子上，以替换为关系）是'a'，因为你不能在它们两个中都替换类型变量（没有任何！），并以相同的类型结束。还是我把我的上下方向混淆了？ – yatima2975

哈斯克尔 - 嵌套空列表

回答

相关问题