主页 / coding / 问题 / 78547292
Accepted
wildcat
Asked: 2024-05-29 12:21:02 +0800 CST

Haskell 记录更新看似不兼容的类型

  • 772

我试图理解haskell-skiplist 的内部代码。

作者定义了以下代数数据类型和一些相关函数——其细节并不重要。

data Node k v
  = Node { nKey :: k
         , nValue :: v
         , nSibling :: Node k v
         , nChild :: Node k v }
  | Head { nSibling :: Node k v
         , nChild :: Node k v }
  | Nil

nodeLTKey :: forall k v. Ord k => Node k v -> k -> Bool
nodeEQKey :: forall k v. Eq k => Node k v -> k -> Bool
sibling :: forall k v. Node k v -> Node k v

稍后在insert第 113 行附近的函数中，他们定义了一个类型为 的辅助函数Node k v -> (Node k v, Int)。我把我困惑的部分摘录在下面。

go Nil = (Nil, wins)
go n
  | nodeLTKey sN k = (n {nSibling = fst $ go sN}, -1)
  | nodeEQKey sN k = (n {nSibling = sN {nValue = v}}, -1) 
  -- how can they update the inner record?
  where
    sN = sibling n
    -- How can the compiler be sure that sN is a Node and not Head / Nil?

该sibling函数返回 aNode k v并且只有 a 的可能变体之一Node k v实际上具有名为 的字段nValue。我不明白第二个后卫如何确定sN将有一个nValue字段 - 即，sN将是这种Node情况而不是Head/ Nil。

haskell

1 个回答

  1. Best Answer

    仅从发布的类型和代码来看，确实不能保证构造函数sN的类型和代码Node，并且代码可能在运行时失败。但是，如果我们查看您链接但未复制的上下文，则nodeEQKey定义为仅对于Node字段与参数匹配的对象返回 True nodeEQKey。所以第二个方程可以安全地更新它的nValue，因为它的主体只有在它的守卫匹配时才会被执行，而只有当sN是Nodewith时才会发生nKey == k。

    编译器不保证该节点具有正确的形状；检查发生在运行时。但如果您打开-Wall，您将收到不完整模式匹配的警告，这可能会在运行时失败。

    • 2

相关问题