Como eu uso o fix e como ele funciona?

87

Fiquei um pouco confuso com a documentação do fix(embora ache que entenda o que ela deve fazer agora), então olhei o código-fonte. Isso me deixou mais confuso:

fix :: (a -> a) -> a
fix f = let x = f x in x

Como exatamente isso retorna um ponto fixo?

Decidi experimentar na linha de comando:

Prelude Data.Function> fix id
...

E fica lá. Agora, para ser justo, isso está no meu antigo macbook, que é meio lento. No entanto, essa função não pode ser muito cara do ponto de vista computacional, uma vez que qualquer coisa passada para o id retorna a mesma coisa (sem mencionar que não está consumindo tempo da CPU). O que estou fazendo errado?

Jason Baker
fonte
68
A resposta da pegadinha é "consertar não tem utilidade real, está lá apenas para que você possa digitar fix errorghci e se sentir bem consigo mesmo".
Thomas M. DuBuisson
3
@TomMD - Engraçado. Vou me lembrar disso se alguém me perguntar o que o remédio faz e eu me sentir mal-humorado. :-)
Jason Baker
2
Normalmente escrevo fixcomo fix f = f (fix f). Curto, simples, funciona e idêntico à definição matemática.
newacct
20
@newacct, sim, é como eu penso nisso também. Mas aquele aqui pode levar a estruturas mais eficientes. Você pode ver a diferença se avaliar, digamos fix (1:) !! (10^8),. O original faz isso em memória constante, o seu usa memória linear (o que o torna um pouco mais lento também). Ou seja, usar o let "dá um nó mais forte" e permite que uma estrutura de dados circular seja gerada, enquanto a sua não.
luqui
22
Você também poderia ter reinventado fix! me ajudou a entender fixmuito.
fredoverflow

Respostas:

90

Você não está fazendo nada errado. fix idé um loop infinito.

Quando dizemos que fixretorna o menor ponto fixo de uma função, queremos dizer isso no sentido da teoria do domínio . Então fix (\x -> 2*x-1)é não vai voltar 1, porque embora 1é um ponto fixo dessa função, não é o menos um na ordenação de domínio.

Não posso descrever a ordenação do domínio em um ou dois parágrafos, então vou encaminhá-lo ao link de teoria do domínio acima. É um excelente tutorial, fácil de ler e bastante esclarecedor. Eu recomendo.

Para a visualização de 10.000 pés, fixé uma função de ordem superior que codifica a ideia de recursão . Se você tiver a expressão:

let x = 1:x in x

O que resulta na lista infinita [1,1..], você poderia dizer a mesma coisa usando fix:

fix (\x -> 1:x)

(Ou simplesmente fix (1:)), que diz encontre-me um ponto fixo da (1:)função, IOW um valor xtal que x = 1:x... exatamente como definimos acima. Como você pode ver pela definição, fixnada mais é do que essa ideia - recursão encapsulada em uma função.

É um conceito verdadeiramente geral de recursão também - você pode escrever qualquer função recursiva dessa forma, incluindo funções que usam recursão polimórfica . Por exemplo, a função típica de fibonacci:

fib n = if n < 2 then n else fib (n-1) + fib (n-2)

Pode ser escrito da fixseguinte maneira:

fib = fix (\f -> \n -> if n < 2 then n else f (n-1) + f (n-2))

Exercício: expanda a definição de fixpara mostrar que essas duas definições de fibsão equivalentes.

Mas para uma compreensão completa, leia sobre a teoria do domínio. É uma coisa muito legal.

luqui
fonte
32
Esta é uma maneira relacionada de pensar sobre fix id: fixpega uma função do tipo a -> ae retorna um valor do tipo a. Por idser polimórfico para qualquer a, fix idterá o tipo a, ou seja, qualquer valor possível. Em Haskell, o único valor que pode ser de qualquer tipo é bottom, ⊥, e é indistinguível de um cálculo sem terminação. Portanto, fix idproduz exatamente o que deveria, o valor inferior. Um perigo de fixé que se ⊥ for um ponto fixo de sua função, então é por definição o ponto menos fixo, portanto fixnão terminará.
John L
4
@JohnL em Haskell undefinedtambém é um valor de qualquer tipo. Você pode definir fixcomo: fix f = foldr (\_ -> f) undefined (repeat undefined).
didest
1
@Diego seu código é equivalente a _Y f = f (_Y f).
Will Ness de
25

Eu não alego entender isso de forma alguma, mas se isso ajudar alguém ... então uau.

Considere a definição de fix. fix f = let x = f x in x. A parte incompreensível é que xé definido como f x. Mas pense nisso por um minuto.

x = f x

Como x = fx, então podemos substituir o valor de xno lado direito disso, certo? Portanto ...

x = f . f $ x -- or x = f (f x)
x = f . f . f $ x -- or x = f (f (f x))
x = f . f . f . f . f . f . f . f . f . f . f $ x -- etc.

Portanto, o truque é, para encerrar, fdeve gerar algum tipo de estrutura, de modo que um fpadrão posterior possa corresponder a essa estrutura e encerrar a recursão, sem realmente se preocupar com o "valor" completo de seu parâmetro (?)

A menos, é claro, que você queira fazer algo como criar uma lista infinita, como ilustrou luqui.

A explicação fatorial de TomMD é boa. A assinatura de tipo de Fix é (a -> a) -> a. A assinatura de tipo para (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1)é (b -> b) -> b -> b, em outras palavras (b -> b) -> (b -> b),. Então podemos dizer isso a = (b -> b). Dessa forma, fix pega nossa função, que é a -> a, ou realmente, (b -> b) -> (b -> b)e vai retornar um resultado do tipo a, ou seja, b -> bou seja, outra função!

Espere, pensei que deveria retornar um ponto fixo ... não uma função. Bem, é verdade, mais ou menos (já que funções são dados). Você pode imaginar que nos deu a função definitiva de encontrar um fatorial. Demos a ela uma função que não sabe como recursar (portanto, um dos parâmetros para ela é uma função usada para recursar), e fixensinamos como recursar.

Lembra que eu disse que isso ftem que gerar algum tipo de estrutura para que um fpadrão posterior possa combinar e terminar? Bem, isso não é exatamente certo, eu acho. TomMD ilustrou como podemos expandir xpara aplicar a função e avançar em direção ao caso base. Para sua função, ele usou um if / then, e é isso que causa a rescisão. Após substituições repetidas, a inparte de toda a definição de fixeventualmente deixa de ser definida em termos de xe é quando é computável e completa.

Dan Burton
fonte
Obrigado. Esta é uma explicação muito útil e prática.
kizzx2
17

Você precisa de uma maneira para o ponto de fixação terminar. Expandindo seu exemplo, é óbvio que não vai terminar:

fix id
--> let x = id x in x
--> id x
--> id (id x)
--> id (id (id x))
--> ...

Aqui está um exemplo real de como eu uso correção (observe que não uso correção com frequência e provavelmente estava cansado / não me preocupei com código legível quando escrevi isso):

(fix (\f h -> if (pred h) then f (mutate h) else h)) q

WTF, você diz! Bem, sim, mas existem alguns pontos realmente úteis aqui. Em primeiro lugar, seu primeiro fixargumento geralmente deve ser uma função que é o caso de 'recurse' e o segundo argumento são os dados sobre os quais agir. Aqui está o mesmo código de uma função nomeada:

getQ h
      | pred h = getQ (mutate h)
      | otherwise = h

Se você ainda está confuso, talvez o fatorial seja um exemplo mais fácil:

fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 5 -->* 120

Observe a avaliação:

fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 3 -->
let x = (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x in x 3 -->
let x = ... in (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 3 -->
let x = ... in (\d -> if d > 0 then d * (x (d-1)) else 1) 3

Oh, você acabou de ver isso? Isso xse tornou uma função dentro do nosso thenramo.

let x = ... in if 3 > 0 then 3 * (x (3 - 1)) else 1) -->
let x = ... in 3 * x 2 -->
let x = ... in 3 * (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 2 -->

No exemplo acima, você precisa se lembrar x = f x, daí os dois argumentos de x 2no final em vez de apenas 2.

let x = ... in 3 * (\d -> if d > 0 then d * (x (d-1)) else 1) 2 -->

E vou parar por aqui!

Thomas M. DuBuisson
fonte
Sua resposta é o que realmente fez fixsentido para mim. Minha resposta depende muito do que você já disse.
Dan Burton
@Thomas ambas as suas sequências de redução estão incorretas. :) id xapenas reduz a x(que então reduz novamente a id x). - Então, na 2ª amostra ( fact), quando a xconversão é forçada pela primeira vez, o valor resultante é lembrado e reutilizado. O recálculo de (\recurse ...) xaconteceria com a definição de y g = g (y g)não compartilhamento , não com esta definição de compartilhamentofix . - Fiz a edição de teste aqui - você pode usá-la ou posso fazer a edição, se você aprovar.
Will Ness de
na verdade, quando fix idé reduzido, let x = id x in xtambém força o valor do aplicativo id xdentro do letquadro (conversão), então ele reduz para let x = x in x, e isso faz um loop. Parece que sim.
Will Ness de
Corrigir. Minha resposta está usando o raciocínio equacional. Mostrar a redução à la Haskell, que se preocupa com a ordem de avaliação, só serve para confundir o exemplo sem nenhum ganho real.
Thomas M. DuBuisson
1
A questão é marcada com haskell e letrec (ou seja, o let recursivo, com compartilhamento). A distinção entre fixe Y é muito clara e importante em Haskell. Não vejo o que adianta mostrar a ordem de redução errada quando a correta é ainda mais curta, muito mais clara e fácil de seguir e reflete corretamente o que realmente está acontecendo.
Will Ness
3

Pelo que entendi, ele encontra um valor para a função, de modo que produza a mesma coisa que você deu a ele. O problema é que ele sempre escolherá indefinido (ou um loop infinito, em haskell, os loops indefinidos e infinitos são o mesmo) ou o que quer que tenha mais indefinidos. Por exemplo, com id,

λ <*Main Data.Function>: id undefined
*** Exception: Prelude.undefined

Como você pode ver, indefinido é um ponto fixo, então fixo escolheremos. Em vez disso, faça (\ x-> 1: x).

λ <*Main Data.Function>: undefined
*** Exception: Prelude.undefined
λ <*Main Data.Function>: (\x->1:x) undefined
[1*** Exception: Prelude.undefined

Portanto, fixnão pode escolher indefinido. Para torná-lo um pouco mais conectado a loops infinitos.

λ <*Main Data.Function>: let y=y in y
^CInterrupted.
λ <*Main Data.Function>: (\x->1:x) (let y=y in y)
[1^CInterrupted.

Novamente, uma pequena diferença. Então, qual é o ponto fixo? Vamos tentar repeat 1.

λ <*Main Data.Function>: repeat 1
[1,1,1,1,1,1, and so on
λ <*Main Data.Function>: (\x->1:x) $ repeat 1
[1,1,1,1,1,1, and so on

É o mesmo! Uma vez que este é o único ponto fixo, fixdeve se estabelecer nele. Desculpe fix, sem loops infinitos ou indefinidos para você.

PyRulez
fonte