Transformation einer Funktion, die einen Fixpunkt berechnet

Question

Ich habe eine Funktion, die einen festen Punkt in Bezug auf die ITERAT berechnet:

equivalenceClosure :: (Ord a) => Relation a -> Relation a
equivalenceClosure = fst . List.head                -- "guaranteed" to exist 
                   . List.dropWhile (uncurry (/=))  -- removes pairs that are not equal
                   . U.List.pairwise (,)            -- applies (,) to adjacent list elements
                   . iterate ( reflexivity
                             . symmetry
                             . transitivity
                             )

Beachten Sie, dass wir davon abstrahieren können:

findFixedPoint :: (a -> a) -> a -> a
findFixedPoint f = fst . List.head
                 . List.dropWhile (uncurry (/=))  -- dropWhile we have not reached the fixed point
                 . U.List.pairwise (,)            -- applies (,) to adjacent list elements
                 . iterate
                 $ f

Kann diese Funktion in Bezug auf Fix geschrieben werden? Es scheint, als ob es eine Transformation von diesem Schema zu etwas geben sollte, das mit Fix darin besteht, aber ich sehe es nicht.

Answer 1

Hier ist einiges vor sich, von der Mechanik der faulen Bewertung bis zur Definition eines Fixpunkts in die Methode einen Fixpunkt finden. Kurz gesagt, ich glaube, Sie können die möglicherweise falsch austauschen Fixe -of -Funktions -Anwendung im Lambda -Kalkül mit deinen Bedürfnissen.

Es kann hilfreich sein zu beachten iterate) Erfordert einen Startwert für die Abfolge der Funktionsanwendung. Vergleichen Sie dies dem fix Funktion, die keinen solchen Startwert erfordert (als Heads Up geben die Typen dies bereits nach: findFixedPoint ist vom Typ (a -> a) -> a -> a, wohingegen fix hat Typ (a -> a) -> a). Dies liegt von Natur aus daran, dass die beiden Funktionen subtil unterschiedliche Dinge tun.

Lassen Sie uns etwas tiefer in das eintauchen. Erstens sollte ich sagen, dass Sie möglicherweise ein bisschen mehr Informationen geben müssen (z. , dein findFixedPoint Funktion ist äquivalent in Ergebnis zu fix, Für ein Nur bestimmte Funktionen

Schauen wir uns einen Code an:

{-# LANGUAGE RankNTypes #-}                                                      

import Control.Monad.Fix                                                                              
import qualified Data.List as List                                                                   

findFixedPoint :: forall a. Eq a => (a -> a) -> a -> a                                                
findFixedPoint f = fst . List.head                                                                    
                 . List.dropWhile (uncurry (/=))  -- dropWhile we have not reached the fixed point    
                 . pairwise (,)                   -- applies (,) to adjacent list elements            
                 . iterate f                                                                          

pairwise :: (a -> a -> b) -> [a] -> [b]                                                             
pairwise f []           = []                                                                        
pairwise f (x:[])       = []                                                                        
pairwise f (x:(xs:xss)) = f x xs:pairwise f xss

Vergleichen Sie dies mit der Definition von fix:

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

Und Sie werden feststellen, dass wir eine ganz andere Art von finden Fixpunkt (dh wir missbrauchen eine faule Bewertung, um einen Fixpunkt für die Funktionsanwendung in der Funktion zu generieren mathematischer Sinn, wo wir nur die Bewertung aufhören iff* Die auf sich selbst angewendete resultierende Funktion bewertet dieselbe Funktion.

Lassen Sie uns zur Illustration einige Funktionen definieren:

lambdaA = const 3
lambdaB = (*)3          

und sehen wir den Unterschied zwischen sehen fix und findFixedPoint:

*Main> fix lambdaA               -- evaluates to const 3 (const 3) = const 3
                                 -- fixed point after one iteration           
3                                  
*Main> findFixedPoint lambdaA 0  -- evaluates to [const 3 0, const 3 (const 3 0), ... thunks]
                                 -- followed by grabbing the head.
3                                  
*Main> fix lambdaB               -- does not stop evaluating      
^CInterrupted.                   
*Main> findFixedPoint lambdaB 0  -- evaluates to [0, 0, ...thunks]
                                 -- followed by grabbing the head
0                            

Wenn wir den Startwert nicht angeben können, was ist dann was ist fix benutzt für? Es stellt sich heraus, dass durch Hinzufügen fix Für den Lambda -Kalkül erhalten wir die Fähigkeit, die Bewertung rekursiger Funktionen anzugeben. In Betracht ziehen fact' = \rec n -> if n == 0 then 1 else n * rec (n-1), Wir können den Fixpunkt von berechnen fact' wie:

*Main> (fix fact') 5
120      

wo bei der Bewertung (fix fact') gilt wiederholt fact' sich selbst, bis wir die erreichen gleich Funktion, was wir dann mit dem Wert anrufen 5. Wir können das sehen in:

  fix fact'
= fact' (fix fact')
= (\rec n -> if n == 0 then 1 else n * rec (n-1)) (fix fact')
= \n -> if n == 0 then 1 else n * fix fact' (n-1)
= \n -> if n == 0 then 1 else n * fact' (fix fact') (n-1)
= \n -> if n == 0 then 1
        else n * (\rec n' -> if n' == 0 then 1 else n' * rec (n'-1)) (fix fact') (n-1)
= \n -> if n == 0 then 1
        else n * (if n-1 == 0 then 1 else (n-1) * fix fact' (n-2))
= \n -> if n == 0 then 1
        else n * (if n-1 == 0 then 1
                  else (n-1) * (if n-2 == 0 then 1
                                else (n-2) * fix fact' (n-3)))
= ...

Was bedeutet das alles? Abhängig von der Funktion, mit der Sie sich befassen, können Sie nicht unbedingt in der Lage sein, verwenden fix Berechnen Sie die Art von Fixpunkt, die Sie möchten. Dies hängt meines Wissens von den fraglichen Funktionen ab. Nicht alle Funktionen haben die Art von Fixpunkt von berechnet von fix!

*Ich habe es vermieden, über die Domänentheorie zu sprechen, da ich glaube, dass es nur ein bereits subtiles Thema verwechseln würde. Wenn Sie neugierig sind, fix findet a sicher nett von festem Punkt, nämlich der am wenigsten verfügbare Fixpunkt des Poset, über die Funktion wird angegeben.

Answer 2

Nur für das Protokoll, es ist möglich Um die Funktion zu definieren findFixedPoint Verwendung fix. Wie Raeez betont hat, können rekursive Funktionen in Bezug auf die Weise definiert werden fix. Die Funktion, an der Sie interessiert sind, kann rekursiv definiert werden als:

findFixedPoint :: Eq a => (a -> a) -> a -> a
findFixedPoint f x = 
   case (f x) == x of
       True  -> x
       False -> findFixedPoint f (f x)

Dies bedeutet, dass wir es definieren können als fix ffp wo ffp ist:

ffp :: Eq a => ((a -> a) -> a -> a) -> (a -> a) -> a -> a
ffp g f x = 
   case (f x) == x of
       True  -> x
       False -> g f (f x)

Für ein konkretes Beispiel nehmen wir das an, das f ist definiert als

f = drop 1

Für jede endliche Liste ist es leicht zu erkennen l wir haben findFixedPoint f l == []. Hier ist, wie fix ffp würde funktionieren, wenn das "Wertargument" [] ist:

(fix ffp) f []
    = { definition of fix }
ffp (fix ffp) f []
    = { f [] = [] and definition of ffp }
[]

Andererseits hätten wir: Wenn das "Wertargument" [42] ist, hätten wir:

fix ffp f [42]
    = { definition of fix }
ffp (fix ffp) f [42]
    = { f [42] =/= [42] and definition of ffp }
(fix ffp) f (f [42])
    = { f [42] = [] }
(fix ffp) f []
    = { see above }
[]