Estou tentando entender o código interno de haskell-skiplist .
O autor define o seguinte tipo de dados algébricos e algumas funções relevantes – cujos detalhes realmente não importam.
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
Mais tarde na insert
função na linha 113, eles definem uma função auxiliar do tipo Node k v -> (Node k v, Int)
. Extraí a parte sobre a qual estou confuso abaixo.
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?
A sibling
função retorna a Node k v
e apenas uma das variantes possíveis de a Node k v
possui um campo chamado nValue
. Não entendo como o segundo guarda pode ter certeza de que sN
terá um nValue
campo - ou seja, esse sN
será o Node
caso e não Head
/ Nil
.