检查Haskell中的列表是否平坦

Question

在The Little Schemer中有一个功能可以检查列表是否是平的:

(define lat?
  (lambda (l)
    (cond
     ((null? l) #t)
     ((atom? (car l)) (lat? (cdr l)))
     (else #f))))

我正在尝试在Haskell中编写相同的递归函数,但没有成功:

is_lat :: [a] -> Bool
is_lat [] = True
is_lat ???

我如何检查参数不在表单中[[a]]？换句话说,[1,2,3]是一个有效的输入,但[[1,3], [2,4]]并[[[1,2,3]]]没有.

我想在接受列表的递归函数中进一步使用它,以确保我只处理平面列表.

编辑:我看到人们因is_lat :: [a] -> Bool类型签名而感到困惑.我现在同意,我不应该在运行时检查类型.但是,是否可以在编译时检查类型？如何使该功能仅适用于平面列表？或者我应该彻底改变我的思维方式？

Answer 1

你不能在Haskell中以与在Scheme中相同的方式考虑嵌套列表,因为它们不是相同的数据结构.Haskell列表是同质的,其中Lisp"列表"实际上更接近玫瑰树(如下面的CAMcCann所指出的).作为一个说明性示例,请查看WYAS48解析部分如何定义LispVal.

如果你真的,真的,真的想要进行运行时类型检查,即使它通常是一个坏主意而且在Haskell中非常传统,请查看Data.Typeable.这种反应也许有用.

这个问题的真正答案是"你需要在Haskell中以不同的方式考虑你的参数,而不是在Lisp中,这导致永远不需要在运行时自己执行这个检查"(我说这是一个Common Lisper,所以我明白这是多么令人沮丧那就是开始).

附录:为了响应您的编辑,Haskell的类型系统自动确保这一点.如果您有类型的功能foo :: [Int] -> Int,例如,你通过它["One", "Two", "Three"]或者[[1, 2, 3]],你会得到一个编译时错误,告诉你什么只是爆炸和原因.如果要专门化一个函数,只需声明一个更具体的类型.

例如(不要写这样的代码,它仅用于说明目的),比如说你有一个简单的函数

myLookup index map = lookup index map 

如果你把它加载到GHCi并运行:t myLookup,它会告诉你函数的类型是myLookup :: Eq a => a -> [(a, b)] -> Maybe b意味着它可以获取任何类型的键Eq(你可以运行的任何东西==).现在,无论出于何种原因,你都要确保只使用数字作为键.您可以通过添加更具体的类型声明来确保它

myLookup :: Int -> [(Int, a)] -> Maybe a
myLookup index map = lookup index map 

现在,即使函数体中没有任何东西阻止它处理其他键类型,如果你试图传递除Int索引之外的其他东西而不是[(Int, a)]映射,你将在编译时得到类型错误.结果,这个

myLookup :: Int -> [(Int, a)] -> Maybe a
myLookup ix lst = lookup ix lst

main :: IO ()
main = putStrLn . show $ myLookup 1 [(1, "Foo")]

将编译并运行正常,但这

myLookup :: Int -> [(Int, a)] -> Maybe a
myLookup ix lst = lookup ix lst

main :: IO ()
main = putStrLn . show $ myLookup "Nope.jpg" [("Foo", 1)]

也不会.在我的机器上,它在编译时出错

/home/inaimathi/test.hs:5:35:
    Couldn't match expected type `Int' with actual type `[Char]'
    In the first argument of `myLookup', namely `"Nope.jpg"'
    In the second argument of `($)', namely
      `myLookup "Nope.jpg" [("Foo", 1)]'
    In the expression:
      putStrLn . show $ myLookup "Nope.jpg" [("Foo", 1)]
Failed, modules loaded: none.

我真的希望这不会让你更进一步.

Answer 2

对于标准的Haskell列表,这既不可能也不必要,因为Haskell是强类型的; 列表的所有元素本身都是列表(在这种情况下,类型是[a] = [[b]]针对某些列表b),或者它们不是.

例如,如果您尝试构建混合列表,您将从编译器中收到错误:

Prelude> ["hello", ["world!"]]

<interactive>:3:12:
    Couldn't match expected type `Char' with actual type `[Char]'
    In the expression: "world!"
    In the expression: ["world!"]
    In the expression: ["hello", ["world!"]]

Answer 3

函数类型[a] -> Bool隐含地意味着forall a. [a] -> Bool,换句话说,它是为所有可能元素类型的列表相同地定义的.这不包括类型,如[[Int]]或[[[String]]]或嵌套你能想到的任何深度.但是对于你的函数来说,元素类型不是 - 也不可能 - 很重要.

就此函数而言,输入始终是一个列表,其元素是一些不透明的未知类型.它永远不会收到包含相同opaque类型的嵌套列表.