8

在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类型签名而感到困惑。我现在同意，我不应该在运行时检查类型。但是，是否可以在编译时检查类型？如何使该功能仅适用于平面列表？还是我应该彻底改变我的思维方式？

4

4 回答 4

19

在 Haskell 中，您不能真正以与在 Scheme 中相同的方式来考虑嵌套列表，因为它们不是相同的数据结构。Haskell 列表是同质的，而 Lisp“列表”实际上更接近于玫瑰树（如下面的 CAMcCann 所指出的）。作为一个说明性示例，看一下WYAS48 解析部分如何定义LispVal.

如果你真的，真的，真的想进行运行时类型检查，即使这通常是一个坏主意并且在 Haskell 中非常不合常规，请查看Data.Typeable。此响应也可能有用。

这个问题的真正答案是“你需要在 Haskell 和 Lisp 中以不同的方式思考你的论点，这导致永远不需要在运行时自己执行这个检查”（我说这是一个 Common Lisper，所以我理解这是多么令人沮丧那就是开始）。

附录：响应您的编辑，Haskell 的类型系统自动确保这一点。例如，如果你有一个 type 的函数foo :: [Int] -> Int，并且你传递它["One", "Two", "Three"]or [[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.

我真的希望这不会让你更困惑。

于 2013-04-16T15:20:46.670 回答
13

这对于标准的 Haskell 列表来说既不可能也不必要，因为 Haskell 是强类型的。列表的所有元素本身都是列表（在这种情况下，类型是[a] = [[b]]some 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!"]]
于 2013-04-16T14:31:00.727 回答
11

函数类型[a] -> Bool隐含的意思是forall a. [a] -> Bool，换句话说，它为所有可能的元素类型的列表定义相同。这确实包括类型[[Int]]或[[[String]]]任何您能想到的嵌套深度。但是元素类型是什么对你的函数没有影响。

就这个函数而言，输入总是一个列表，其元素是一些不透明的、未知的类型。它永远不会接收包含相同不透明类型的嵌套列表。

于 2013-04-16T14:57:50.307 回答
1

好吧，我想，在 Haskell 中，您仅限于http://ideone.com/sPhRCP：

main = do   -- your code goes here
    print $isFlat [Node 1, Node 2, Node 3]
    print $isFlat [Node 1, Node 2, Branch [Node 3, Node 4, Node 5], Node 6]

data Tree a = Node a | Branch [Tree a]

isFlat :: [Tree a] -> Bool
isFlat = all isNode where
                      isNode (Node _) = True
                      isNode _ = False

在非严格类型语言中，每个对象都有运行时类型信息，因此可以是多态的。这可能是一个复杂的强制网络，例如在 Scala 中（如果您使用 C++ 则不太复杂），或者只是“一切都是对象，对象就是一切”，就像在纯动态语言（Lisp、JS、...） .
Haskell 是严格类型的。

于 2013-09-05T07:31:16.990 回答