8

你好 Haskellers 和 Haskellettes，

在阅读http://learnyouahaskell.com/时，我的一个朋友遇到了一个问题：

是否可以在 Haskell 中编写一个递归函数，如果所有 sub-sub-_-sublists 都为空，则返回 True。我的第一个猜测是 - 应该是 - 但我在编写类型注释时遇到了一个大问题。

他尝试了类似的东西

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

这是 - 不工作 - :-)

我想出了类似的东西

  • 用 concat 折叠 - 得到一个长列表
    （给我实现问题）
  • 或制作一个无限的树状数据类型 - 并从列表中制作它
    （尚未实现）

但对于这个问题，后者听起来有点矫枉过正。你的想法是什么——在这样一个阳光明媚的星期天;-)

提前致谢

作为对所有评论的回应——我想补充的是这种糟糕的风格，这只是一个实验！
不要在家尝试做这个！;-)

4

2 回答 2

5

类型类怎么样？

{-# 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-10T15:34:52.837 回答
4

由于以下原因，仅使用参数多态性是不可能的。

考虑这些值：

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

显然，您希望您的函数同时使用xand y，因此它的类型必须是null1 :: [a] -> Bool。（有人可以帮我使这个论点看起来正式吗？我怎样才能证明这是唯一的最具体的无上下文类型，可以用[Int] -> Booland统一[Double] -> Bool？类型之间的关系有名称吗？）

现在，如果您有这种类型，那么null1 z将等于，null1 x因为它们仅在列表元素的值上有所不同，而这些值是从中抽象出来的。（甚至不再接近正式证明:()

您想要的z是null2 :: [[a]] -> Bool，它的行为会有所不同，因此给出null1和null2相同的名称将需要重载。（见 FUZxxl 的回答）

于 2011-07-10T16:03:25.090 回答