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
.
Apenas pelos tipos e códigos postados, na verdade não há garantia de que
sN
será doNode
construtor, e o código pode falhar em tempo de execução. Mas se olharmos para o contexto que você vinculou, mas não copiou,nodeEQKey
está definido para retornar True apenas paraNode
objetos cujo campo correspondenodeEQKey
ao parâmetro de. Portanto, a segunda equação pode atualizar seu , com segurançanValue
, pois seu corpo só será executado se sua guarda corresponder, o que só acontecerá sesN
for umNode
withnKey == k
.O compilador não garante que este nó terá o formato correto; a verificação acontece em tempo de execução. Mas se você ativar o
-Wall
, você será avisado sobre uma correspondência de padrão incompleta, que pode falhar em tempo de execução.