Tenho estudado profundamente foldTree
a função em Haskell, que é definida da seguinte forma:
foldTree :: (a -> [b] -> b) -> Tree a -> b
foldTree f = go where
go (Node x ts) = f x (map go ts)
Recentemente me deparei com a seguinte interpretação da frase:
quando chamamos
f x vs
, assumimos quex
evs
já estão vinculados a valores conhecidos.
go (Node x ts) = f x (map go ts)
- O valor de
x
já está vinculado da maneira esperada e familiar. - Entretanto, nenhum valor está vinculado
vs
ainda; a vinculação devs
é adiada até que a recursão em toda a subfloresta seja concluída.
A menção de um elemento de tempo (usando termos como "já" e "ainda") me confunde. Para entender melhor isso, comecei a experimentar alguns conceitos emprestados de provas de dedução natural e indução. Especificamente, tentei conceituar o segundo argumento de f
como segue:
- Presumo que um tipo
[b]
esteja definido. - Então, considero a definição real de
f
em termos de combinação deste[b]
tipo assumido com oa
tipo para definir a expressão geralfoldTree f tree
, ondetree
tem tipoTree a
.
Como eu poderia refinar essa linha de pensamento em termos de suposições e não usar avaliação de função real, assumindo que está correta? Alternativamente, há outra perspectiva formal ou intuitiva que eu poderia adotar para entender melhor essa função e sua mecânica?
Isto é consequência de uma avaliação preguiçosa [Haskell-wiki] .
Bem, ele se vincula a uma expressão , com
map go ts
, e é isso. Quandof
precisa do(s) valor(es)[b]
dele forçará a avaliação daquela árvore de expressão. Isso significa que ele começará a avaliarmap go ts
. É possível que a árvore não tenha filhos, nesse casomap
retornará uma lista vazia.Se a árvore tiver filhos, ela avaliará a lista conforme os nós necessários por meio de avaliação preguiçosa e nem mesmo avaliará com o de um dos filhos.
go ti
ti
Node
Mas como em Haskell as funções são puras, a ordem essencialmente não importa. Você pode simplesmente fingir que esses itens são avaliados.