I am trying to understand the internal code of haskell-skiplist.
The author defines the following algebraic data type and some relevant functions – the details of which do not really matter.
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
Later in the insert function around line 113, they define a helper function of type Node k v -> (Node k v, Int). I have extracted the part I am confused about below.
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?
The sibling function returns a Node k v and only one of the possible variants of a Node k v actually has a field called nValue. I don’t understand how the second guard can be sure that sN will have an nValue field – i.e that sN will be of the Node case and not Head / Nil.
>Solution :
From just the types and code posted, indeed there is no guarantee that sN will be of the Node constructor, and the code could fail at runtime. But if we look at context you linked but did not copy, nodeEQKey is defined to only return True for Node objects whose field matches nodeEQKey‘s parameter. So the second equation can safely update its nValue, because its body will only be executed if its guard matches, which will only happen if sN is a Node with nKey == k.
The compiler does not guarantee this node will have the right shape; the check happens at runtime. But if you turn on -Wall, you will be warned of an incomplete pattern match, which could fail at runtime.