Comment puis-je utiliser correctif, et comment fonctionne-t-il?

Question

Je suis un peu confus par la documentation fix (même si je pense que je comprends ce qu'il est censé faire maintenant), je regardais le code source. Cela m'a laissé plus confus:

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

Comment exactement ce retour un point fixe?

J'ai décidé de l'essayer à la ligne de commande:

Prelude Data.Function> fix id
...

Et il se bloque là. Maintenant, pour être juste, c'est sur mon vieux macbook qui est un peu lent. Cependant, cette fonction ne peut pas être aussi informatiquement cher puisque tout passé pour id APPORTE arrière même chose (pour ne pas mentionner qu'il mange jusqu'à peu de temps CPU). Qu'est-ce que je fais mal?

Answer 1

Vous faites mal rien. fix id est une boucle infinie.

Quand nous disons que fix retourne le point fixe moins d'une fonction, nous voulons dire que dans le domaine la théorie sens de. Alors fix (\x -> 2*x-1) est pas va revenir 1, parce que même si 1 est un point fixe de cette fonction, il n'est pas le moins un dans l'ordre de domaine.

Je ne peux pas décrire l'ordre de domaine dans un simple paragraphe ou deux, donc je vais vous référer au lien de la théorie de domaine ci-dessus. Il est un excellent tutoriel, facile à lire et très instructif. Je le recommande fortement.

Pour la vue de 10.000 pieds, fix est une fonction d'ordre supérieur qui code pour l'idée de récursivité . Si vous avez l'expression:

let x = 1:x in x

Quels sont les résultats dans la liste infinie [1,1..], on pourrait dire la même chose en utilisant fix:

fix (\x -> 1:x)

(Ou tout simplement fix (1:)), qui dit me trouver un point fixe de la fonction (1:), OIEau une valeur telle que x x = 1:x ... tout comme nous avons défini ci-dessus. Comme vous pouvez le voir dans la définition, fix est rien de plus que cette idée -. Récursion encapsulé dans une fonction

Il est un concept vraiment général de récursivité et - vous pouvez écrire une fonction récursive de cette façon, y compris les fonctions qui utilisent récursion polymorphes. Ainsi, par exemple la fonction de fibonacci typique:

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

Peut être écrit en utilisant fix cette façon:

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

Exercice:. Élargir la définition de fix pour montrer que ces deux définitions de fib sont équivalentes

Mais pour une bonne compréhension, lu sur la théorie de domaine. Il est vraiment cool stuff.

Answer 2

Je ne prétends pas comprendre du tout, mais si cela aide tout le monde ... Youpi alors.

Considérez la définition de fix. fix f = let x = f x in x. La partie ahurissants est que x est définie comme f x. Mais pensez à ce sujet pendant une minute.

x = f x

Puisque x = f x, alors nous pouvons remplacer la valeur de x sur le côté droit de ça, non? Ainsi donc ...

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.

Le truc est donc, pour mettre fin, f doit générer une sorte de structure, de sorte qu'un f plus tard peut correspondre à motif que la structure et mettre fin à la récursion, sans réellement se soucier de la « valeur » complète de son paramètre ( ?)

À moins, bien sûr, vous voulez faire quelque chose comme créer une liste infinie, comme illustré Luqui.

explication factoriel de TomMD est bon. La signature de type Fix est (a -> a) -> a. La signature de type pour (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) est (b -> b) -> b -> b, en d'autres termes, (b -> b) -> (b -> b). On peut donc dire que a = (b -> b). De cette façon, notre solution prend fonction, ce qui est a -> a, ou vraiment, (b -> b) -> (b -> b), et renvoie un résultat de type a, autrement dit, b -> b, autrement dit, une autre fonction!

Attendez, je pensais qu'il était censé revenir un point fixe ... pas une fonction. Eh bien, il fait, en quelque sorte (puisque les fonctions sont données). Vous pouvez imaginer que cela nous a donné la fonction définitive pour trouver un factoriel. Nous lui avons donné une fonction qui dind't savent récursion (d'où l'un des paramètres est une fonction utilisée pour récursion), et fix a enseigné comment récursion.

Rappelez-vous comment je dit que f doit générer une sorte de structure de sorte qu'un match plus tard modèle f de boîte et mettre fin? Eh bien, ce n'est pas tout à fait raison, je suppose. TomMD a montré comment nous pouvons étendre x d'appliquer la fonction et pas vers le boîtier de base. Pour sa fonction, il a utilisé un if / then, et qui est ce qui provoque la résiliation. Après les remplacements répétés, la partie in de la définition de l'ensemble des fix finalement cesse d'être défini en termes de x et qui est quand il est calculable et complet.

Answer 3

Vous avez besoin d'un moyen pour mettre fin à la fixpoint. L'expansion de votre exemple, il est évident que ce ne sera pas la fin:

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

Voici un exemple réel de moi à l'aide fixe (note que je ne me fixe souvent et était probablement fatigué / ne pas se soucier du code lisible quand j'ai écrit ceci):

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

WTF, vous dites! Eh bien, oui, mais il y a quelques points vraiment utiles ici. Tout d'abord, votre premier argument de fix devrait normalement être une fonction qui est le cas de « récursion » et le second argument est les données sur lesquelles agir. Voici le même code en fonction du nom:

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

Si vous êtes encore confus alors peut-être factoriel sera un exemple plus facile:

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

Avis de l'évaluation:

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, vous ne voyez cela? Ce x est devenu une fonction au sein de notre branche then.

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 -->

Dans ce qui précède, vous devez vous rappeler x = f x, d'où les deux arguments de x 2 à la fin au lieu d'2.

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

Et je vais arrêter ici!

Answer 4

Comment je comprends qu'il est, il trouve une valeur de la fonction, de telle sorte qu'il sort la même chose que vous lui donnez. Le hic est, il sera toujours non défini choisissez (ou une boucle infinie, dans haskell, indéfini et boucles infinies sont les mêmes) ou tout ce qui a le plus undefineds en elle. Par exemple, avec id,

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

Comme vous pouvez le voir, non défini est un point fixe, donc fix choisira que. Si vous faites place (\ x-> 1: x).

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

fix ne peuvent pas choisir non défini. Pour le rendre un peu plus relié à des boucles infinies.

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

Encore une fois, une légère différence. Alors, quel est le point fixe? Essayons 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

Il est le même! Étant donné que c'est le seul point fixe, fix doit régler là-dessus. Désolé fix, pas de boucles infinies ou non défini pour vous.