Haskell: O que é a forma normal de cabeça fraca?

O que significa a Forma Normal de Cabeça Fraca (WHNF)? O que significa a forma normal da cabeça (HNF) e a forma normal (NF)?

Mundo Real Haskell afirma:

A function seq familiar avalia uma expressão para o que chamamos de forma normal da cabeça (abreviado HNF). Ele pára quando atinge o construtor mais externo (a “cabeça”). Isto é distinto da forma normal (NF), em que uma expressão é completamente avaliada.

Você também ouvirá os programadores de Haskell se referirem à forma normal de cabeça fraca (WHNF). Para dados normais, a forma normal da cabeça fraca é igual à forma normal da cabeça. A diferença só surge para funções, e é muito abstrusa para nos preocupar aqui.

Eu li alguns resources e definições ( Haskell Wiki e Haskell Mail List e Free Dictionary ), mas eu não entendi. Alguém pode dar um exemplo ou fornecer uma definição leiga?

Eu estou supondo que seria semelhante a:

WHNF = thunk : thunk HNF = 0 : thunk NF = 0 : 1 : 2 : 3 : [] 

Como o seq e ($!) relacionam com o WHNF e o HNF?

Atualizar

Eu ainda estou confuso. Eu sei que algumas das respostas dizem para ignorar o HNF. A partir da leitura das várias definições, parece que não há diferença entre os dados regulares no WHNF e no HNF. No entanto, parece que há uma diferença quando se trata de uma function. Se não houve diferença, por que é necessária a foldl' ?

Outro ponto de confusão é o Wiki de Haskell, que afirma que seq reduz a WHNF, e não fará nada ao seguinte exemplo. Então eles dizem que eles têm que usar seq para forçar a avaliação. Isso não está forçando isso para o HNF?

Código de estouro da pilha newbie comum:

 myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0) 

As pessoas que entendem seq e a forma normal da cabeça fraca (whnf) podem entender imediatamente o que está errado aqui. (acc + x, len + 1) já está em whnf, então seq, que reduz um valor para whnf, não faz nada para isso. Este código irá construir thunks exatamente como o exemplo foldl original, eles estarão dentro de uma tupla. A solução é apenas forçar os componentes da tupla, por exemplo

 myAverage = uncurry (/) . foldl' (\(acc, len) x -> acc `seq` len `seq` (acc+x, len+1)) (0,0) 

– Wiki de Haskell em Stackoverflow

Vou tentar dar uma explicação em termos simples. Como outros apontaram, a forma normal da cabeça não se aplica a Haskell, então não a considerarei aqui.

Forma normal

Uma expressão na forma normal é totalmente avaliada, e nenhuma sub-expressão poderia ser avaliada mais adiante (isto é, ela não contém thunks não avaliados).

Essas expressões estão todas em forma normal:

 42 (2, "hello") \x -> (x + 1) 

Essas expressões não estão no formato normal:

 1 + 2 -- we could evaluate this to 3 (\x -> x + 1) 2 -- we could apply the function "he" ++ "llo" -- we could apply the (++) (1 + 1, 2 + 2) -- we could evaluate 1 + 1 and 2 + 2 

Forma normal da cabeça fraca

Uma expressão na forma normal de cabeça fraca foi avaliada para o construtor de dados mais externo ou abstração de lambda (a cabeça ). Sub-expressões podem ou não ter sido avaliadas . Portanto, toda forma de expressão normal também está na forma normal da cabeça fraca, embora o oposto não seja válido em geral.

Para determinar se uma expressão está na forma normal de cabeça fraca, só precisamos olhar para a parte mais externa da expressão. Se é um construtor de dados ou um lambda, está na forma normal da cabeça fraca. Se é um aplicativo de function, não é.

Essas expressões estão na forma normal da cabeça fraca:

 (1 + 1, 2 + 2) -- the outermost part is the data constructor (,) \x -> 2 + 2 -- the outermost part is a lambda abstraction 'h' : ("e" ++ "llo") -- the outermost part is the data constructor (:) 

Como mencionado, todas as expressões de formulário normal listadas acima também estão na forma normal de cabeça fraca.

Essas expressões não estão na forma normal de cabeça fraca:

 1 + 2 -- the outermost part here is an application of (+) (\x -> x + 1) 2 -- the outermost part is an application of (\x -> x + 1) "he" ++ "llo" -- the outermost part is an application of (++) 

Stack overflow

A avaliação de uma expressão para a forma normal de cabeça fraca pode exigir que outras expressões sejam avaliadas primeiro por WHNF. Por exemplo, para avaliar 1 + (2 + 3) para WHNF, primeiro temos que avaliar 2 + 3 . Se a avaliação de uma única expressão levar a muitas dessas avaliações aninhadas, o resultado será um estouro de pilha.

Isso acontece quando você cria uma expressão grande que não produz nenhum construtor de dados ou lambdas até que uma grande parte dela tenha sido avaliada. Estes são frequentemente causados ​​por este tipo de uso de foldl :

 foldl (+) 0 [1, 2, 3, 4, 5, 6] = foldl (+) (0 + 1) [2, 3, 4, 5, 6] = foldl (+) ((0 + 1) + 2) [3, 4, 5, 6] = foldl (+) (((0 + 1) + 2) + 3) [4, 5, 6] = foldl (+) ((((0 + 1) + 2) + 3) + 4) [5, 6] = foldl (+) (((((0 + 1) + 2) + 3) + 4) + 5) [6] = foldl (+) ((((((0 + 1) + 2) + 3) + 4) + 5) + 6) [] = (((((0 + 1) + 2) + 3) + 4) + 5) + 6 = ((((1 + 2) + 3) + 4) + 5) + 6 = (((3 + 3) + 4) + 5) + 6 = ((6 + 4) + 5) + 6 = (10 + 5) + 6 = 15 + 6 = 21 

Observe como ele tem que ir bem fundo antes que ele possa obter a expressão na forma normal da cabeça fraca.

Você pode se perguntar, por que Haskell não reduz as expressões internas antes do tempo? Isso é por causa da preguiça de Haskell. Como não é possível presumir que, em geral, toda subexpressão será necessária, as expressões são avaliadas externamente em.

(O GHC tem um analisador de rigor que detecta algumas situações em que uma subexpressão é sempre necessária e pode avaliá-lo antecipadamente. Isso é apenas uma otimização, no entanto, e você não deve confiar nele para salvar você de overflows).

Este tipo de expressão, por outro lado, é completamente seguro:

 data List a = Cons a (List a) | Nil foldr Cons Nil [1, 2, 3, 4, 5, 6] = Cons 1 (foldr Cons Nil [2, 3, 4, 5, 6]) -- Cons is a constructor, stop. 

Para evitar a construção dessas grandes expressões quando sabemos que todas as subexpressões terão que ser avaliadas, queremos forçar as partes internas a serem avaliadas antes do tempo.

seq

seq é uma function especial usada para forçar expressões a serem avaliadas. Sua semântica é que seq xy significa que sempre que y é avaliado para a forma normal de cabeça fraca, x também é avaliado para a forma normal de cabeça fraca.

É entre outros lugares usados ​​na definição de foldl' , a variante rígida do foldl .

 foldl' fa [] = a foldl' fa (x:xs) = let a' = fax in a' `seq` foldl' fa' xs 

Cada iteração de foldl' força o acumulador a WHNF. Evita, portanto, construir uma grande expressão e, portanto, evita o transbordamento da pilha.

 foldl' (+) 0 [1, 2, 3, 4, 5, 6] = foldl' (+) 1 [2, 3, 4, 5, 6] = foldl' (+) 3 [3, 4, 5, 6] = foldl' (+) 6 [4, 5, 6] = foldl' (+) 10 [5, 6] = foldl' (+) 15 [6] = foldl' (+) 21 [] = 21 -- 21 is a data constructor, stop. 

Mas como o exemplo no HaskellWiki menciona, isso não salva você em todos os casos, já que o acumulador é avaliado apenas para o WHNF. No exemplo, o acumulador é uma tupla, portanto, ele apenas forçará a avaliação do construtor da tupla e não acc len .

 f (acc, len) x = (acc + x, len + 1) foldl' f (0, 0) [1, 2, 3] = foldl' f (0 + 1, 0 + 1) [2, 3] = foldl' f ((0 + 1) + 2, (0 + 1) + 1) [3] = foldl' f (((0 + 1) + 2) + 3, ((0 + 1) + 1) + 1) [] = (((0 + 1) + 2) + 3, ((0 + 1) + 1) + 1) -- tuple constructor, stop. 

Para evitar isso, devemos fazer com que a avaliação do construtor de tuplas force a avaliação de acc e len . Fazemos isso usando seq .

 f' (acc, len) x = let acc' = acc + x len' = len + 1 in acc' `seq` len' `seq` (acc', len') foldl' f' (0, 0) [1, 2, 3] = foldl' f' (1, 1) [2, 3] = foldl' f' (3, 2) [3] = foldl' f' (6, 3) [] = (6, 3) -- tuple constructor, stop. 

A seção sobre Thunks e Weak Head Normal Form na descrição do Haskell Wikibooks da preguiça fornece uma descrição muito boa do WHNF junto com esta representação útil:

Avaliando o valor (4, [1, 2]) passo a passo. O primeiro estágio é completamente desvalorizado; todas as formas subsequentes estão em WHNF e a última também está em forma normal.

Avaliando o valor (4, [1, 2]) passo a passo. O primeiro estágio é completamente desvalorizado; todas as formas subsequentes estão em WHNF e a última também está em forma normal.

Uma boa explicação com exemplos é dada em http://foldoc.org/Weak+Head+Normal+Form A forma normal da cabeça simplifica até mesmo os bits de uma expressão dentro de uma abstração de function, enquanto a forma normal da cabeça “fraca” para em abstrações de function .

Da fonte, se você tiver:

 \ x -> ((\ y -> y+x) 2) 

que está na forma normal da cabeça fraca, mas não na forma normal da cabeça … porque a possível aplicação está presa dentro de uma function que ainda não pode ser avaliada.

A forma normal da cabeça real seria difícil de implementar eficientemente. Isso exigiria bisbilhotar dentro das funções. Portanto, a vantagem da forma normal da cabeça fraca é que você ainda pode implementar funções como um tipo opaco e, portanto, é mais compatível com as linguagens e otimização compiladas.

Programas Haskell são expressões e são executados por meio de avaliação .

Para avaliar uma expressão, substitua todos os aplicativos de function por suas definições. A ordem em que você faz isso não importa muito, mas ainda é importante: comece com o aplicativo mais externo e prossiga da esquerda para a direita; isso é chamado de avaliação preguiçosa .

Exemplo:

  take 1 (1:2:3:[]) => { apply take } 1 : take (1-1) (2:3:[]) => { apply (-) } 1 : take 0 (2:3:[]) => { apply take } 1 : [] 

A avaliação é interrompida quando não há mais aplicativos de function a serem substituídos. O resultado está na forma normal (ou na forma normal reduzida , RNF). Não importa em qual ordem você avalie uma expressão, você sempre terminará com a mesma forma normal (mas somente se a avaliação terminar).

Existe uma descrição ligeiramente diferente para avaliação lenta. Ou seja, diz que você deve avaliar tudo apenas para a forma normal da cabeça fraca . Existem precisamente três casos para uma expressão estar no WHNF:

  • Um construtor: constructor expression_1 expression_2 ...
  • Uma function interna com poucos argumentos, como (+) 2 ou sqrt
  • Uma expressão lambda: expressão \x -> expression

Em outras palavras, o header da expressão (ou seja, o aplicativo de function mais externa) não pode ser avaliado mais adiante, mas o argumento de function pode conter expressões não avaliadas.

Exemplos de WHNF:

 3 : take 2 [2,3,4] -- outermost function is a constructor (:) (3+1) : [4..] -- ditto \x -> 4+5 -- lambda expression 

Notas

  1. A “cabeça” no WHNF não se refere ao header de uma lista, mas ao aplicativo de function mais externa.
  2. Às vezes, as pessoas chamam expressões não avaliadas de “thunks”, mas não acho que seja uma boa maneira de compreendê-lo.
  3. A forma normal da cabeça (HNF) é irrelevante para o Haskell. Difere do WHNF em que os corpos das expressões lambda também são avaliados até certo ponto.

O WHNF não quer que o corpo de lambdas seja avaliado, então

 WHNF = \a -> thunk HNF = \a -> a + c 

seq quer que seu primeiro argumento esteja em WHNF, então

 let a = \bcde -> (\f -> b + c + d + e + f) b b = a 2 in seq b (b 5) 

avalia para

 \de -> (\f -> 2 + 5 + d + e + f) 2 

em vez de, o que estaria usando o HNF

 \de -> 2 + 5 + d + e + 2 

Basicamente, suponha que você tenha algum tipo de thunk, t .

Agora, se quisermos avaliar t para WHNF ou NHF, que são os mesmos, exceto para funções, descobriríamos que temos algo como

t1 : t2 onde t1 e t2 são thunks. Nesse caso, t1 seria seu 0 (ou melhor, um thunk a 0 sem nenhum unboxing extra)

seq e $! avaliar o WHNF. Observe que

 f $! x = seq x (fx)