Implementieren Sie Reißverschluss mit foldr

StackOverflow https://stackoverflow.com/questions/235148

Frage

Ich bin zur Zeit auf Kapitel 4 von Real World Haskell, und ich versuche, meinen Kopf um foldl in Bezug auf foldr implementieren.

(Hier ist ihr Code:) 

myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

Ich dachte, ich würde versuchen, zip zu implementieren mit der gleichen Technik, aber ich glaube, keine Fortschritte zu machen. Ist es überhaupt möglich?

War es hilfreich?

Lösung 

zip2 xs ys = foldr step done xs ys
  where done ys = []
        step x zipsfn []     = []
        step x zipsfn (y:ys) = (x, y) : (zipsfn ys)

Wie das funktioniert: (foldr Schritt xs) gibt eine Funktion, die verbraucht ys; so gehen wir auf die xs Liste nach unten eine verschachtelte Komposition Aufbau von Funktionen, die mit dem entsprechenden Teil des YS wird jeder angewandt werden.

Wie mit ihm kommen: ich mit der allgemeinen Idee gestartet (von ähnlichen Beispiele gesehen), schrieb 

zip2 xs ys = foldr step done xs ys

dann in jedem der folgenden Zeilen wiederum gefüllt mit dem, was es mußte sein, um die Typen und Werte richtig zu machen kommen. Es war am einfachsten zu betrachten die einfachsten Fälle zuerst vor den härteren.

Die erste Zeile geschrieben einfacher als

werden konnte 
zip2 = foldr step done

als mattiast zeigte.

Andere Tipps

Die Antwort war schon hier gegeben worden, aber keine (illustrativ) Ableitung. So auch nach all den Jahren, vielleicht ist es wert das Hinzufügen es.

Es ist eigentlich ganz einfach. Zuerst 

foldr f z xs 
   = foldr f z [x1,x2,x3,...,xn] = f x1 (foldr f z [x2,x3,...,xn])
   = ... = f x1 (f x2 (f x3 (... (f xn z) ...)))

daher von eta-Erweiterung, 

foldr f z xs ys
   = foldr f z [x1,x2,x3,...,xn] ys = f x1 (foldr f z [x2,x3,...,xn]) ys
   = ... = f x1 (f x2 (f x3 (... (f xn z) ...))) ys

Wie sich hier, , wenn f ist unforcierten in seinem zweiten Argument , es wird zuerst arbeiten auf x1 und ys, f x1 r1 ys wo r1 = (f x2 (f x3 (... (f xn z) ...))) = foldr f z [x2,x3,...,xn].

So mit 

f x1 r1 [] = []
f x1 r1 (y1:ys1) = (x1,y1) : r1 ys1

wir für den Durchgang von Informationen ordnen von links nach rechts auf der Liste, die von Aufruf r1 mit dem Rest der Eingabeliste ys1, foldr f z [x2,x3,...,xn] ys1 = f x2 r2 ys1, wie der nächste Schritt. Und das ist das.

Wenn ys kürzer als xs ist (oder die gleiche Länge), der [] Fall für f Brände und die Verarbeitung stoppen. Aber wenn ys länger als xs dann f Fall des [] wird nicht ausgelöst, und wir werden auf die endgültige f xn bekommen z (yn:ysn) Anwendung, 

f xn z (yn:ysn) = (xn,yn) : z ysn

Da wir das Ende der xs erreicht haben, die zip Verarbeitung stoppen müssen: 

z _ = []

Und das bedeutet die Definition z = const [] verwendet werden soll: 

zip xs ys = foldr f (const []) xs ys
  where
    f x r []     = []
    f x r (y:ys) = (x,y) : r ys

Vom Standpunkt der f spielt r die Rolle einer Erfolg Fortsetzung , die Anrufe f, wenn die Verarbeitung fortgesetzt werden soll, nachdem das Paar (x,y) ausgesendet hat.

So r ist "Was ist mit mehr ys getan, wenn es mehr xs sind" und z = const [], die nil -Fall in foldr, ist ", was mit ys getan wird, wenn es keine weiteren xs "sind . Oder f kann selbst stoppen, Rückkehr [] wenn ys erschöpft ist.

Beachten Sie, wie ys als eine Art Akkumulationswert verwendet wird, die von links nach rechts entlang der Liste xs geführt wird, von einem Aufruf von f zum nächsten ( „Akkumulieren“ Schritt zu sein, hier, von dem ihr ein Kopfelement Strippe ).

Natürlich diese nach links Falte entspricht, in dem ein Akkumulationsschritt „Anwendung der Funktion“ ist, mit z = id die endgültige akkumulierte Wert zurückkehrt, wenn „es nicht mehr xs sind“: 

foldl f a xs =~ foldr (\x r a-> r (f a x)) id xs a

Auch für endliche Listen 

foldr f a xs =~ foldl (\r x a-> r (f x a)) id xs a

Und da die Kombinationsfunktion zu entscheiden, ob bekommt fortzusetzen oder nicht, ist es nun möglich, nach links faltet zu haben, die früh stoppen: 

foldlWhile t f a xs = foldr cons id xs a
  where 
    cons x r a = if t x then r (f a x) else a

oder ein Skipping links falten, foldlWhen t ... mit 

    cons x r a = if t x then r (f a x) else r a

etc.

Ich fand einen Weg mit ganz ähnlichen Verfahren wie bei Ihnen: 

myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
    where step a f (b:bs) = (a,b):(f bs)
          step a f [] = []

Für die nicht-native Haskellers hier, ich habe eine Schema-Version dieses Algorithmus geschrieben, um zu verdeutlichen, was tatsächlich passiert ist: 

> (define (zip lista listb)
    ((foldr (lambda (el func)
           (lambda (a)
             (if (empty? a)
                 empty
                 (cons (cons el (first a)) (func (rest a))))))
         (lambda (a) empty)
         lista) listb))
> (zip '(1 2 3 4) '(5 6 7 8))
(list (cons 1 5) (cons 2 6) (cons 3 7) (cons 4 8))

Die foldr Ergebnisse in einer Funktion, die, wenn sie auf eine Liste angewandt wird, die Zip der Liste zurück mit der Liste auf die Funktion gegeben gefaltet. Die Haskell versteckt den inneren lambda wegen lazy evaluation.

Um brechen sie weiter:

Nehmen Sie Reißverschluss-Eingang: ‚(1 2 3) Die foldr func wird aufgerufen mit 

el->3, func->(lambda (a) empty)

Damit erweitert sich zu: 

(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a))))

Wenn wir das waren jetzt zurückkehren, würden wir eine Funktion, die eine Liste mit einem Element nimmt und gibt das Paar (3-Element): 

> (define f (lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a)))))
> (f (list 9))
(list (cons 3 9))

Weiter ruft foldr jetzt func mit 

el->3, func->f ;using f for shorthand
(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

Dies ist eine func, die eine Liste mit zwei Elementen nehmen, jetzt und Reißverschluss sie mit (list 2 3): 

> (define g (lambda (a) (cons (cons 2 (first a)) (f (rest a)))))
> (g (list 9 1))
(list (cons 2 9) (cons 3 1))

Was ist los? 

(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

a, in diesem Fall wird (list 9 1) 

(cons (cons 2 (first (list 9 1))) (f (rest (list 9 1))))
(cons (cons 2 9) (f (list 1)))

Und, wie Sie sich erinnern, f Reißverschlüsse sein Argument mit 3.

Und weiter geht etc ...

Das Problem bei all diesen Lösungen für zip ist, dass sie nur über eine Liste oder andere Falte, was ein Problem sein kann, wenn beide von ihnen sind „gute Produzenten“, im Sprachgebrauch der Liste Fusion. Was Sie wirklich brauchen, ist eine Lösung, die über beide Listen klappt. Glücklicherweise gibt es ein Papier über genau das, genannt "Coroutining Folds mit Hyperfunktionen" .

Sie benötigen einen Hilfstyp, eine Überfunktion, die im Grunde eine Funktion ist, die eine andere Überfunktion als Argument. 

newtype H a b = H { invoke :: H b a -> b }

Die Hyperfunktionen hier im Grunde verwendet, wirken wie ein „Stapel“ von gewöhnlichen Funktionen. 

push :: (a -> b) -> H a b -> H a b
push f q = H $ \k -> f $ invoke k q

Sie müssen auch einen Weg, um zwei Hyperfunktionen zusammen zu stellen, Ende zu Ende. 

(.#.) :: H b c -> H a b -> H a c
f .#. g = H $ \k -> invoke f $ g .#. k

Dies ist im Zusammenhang mit dem Gesetz push: 

(push f x) .#. (push g y) = push (f . g) (x .#. y)

Dies erweist sich als ein assoziativer Operator zu sein, und dies ist die Identität: 

self :: H a a
self = H $ \k -> invoke k self

Sie müssen auch etwas, das alles andere auf der „Stack“ und gibt einen bestimmten Wert absieht: 

base :: b -> H a b
base b = H $ const b

Und schließlich müssen Sie einen Weg, um einen Wert aus einer Überfunktion zu erhalten: 

run :: H a a -> a
run q = invoke q self

run Strings alle der pushed Funktionen zusammen, ein Ende zum anderen, bis er trifft einen base oder Schleifen unendlich.

So, jetzt können Sie beide Listen in Hyperfunktionen falten, Funktionen, die Informationen von einem zum anderen übergeben, und den Endwert montieren. 

zip xs ys = run $ foldr (\x h -> push (first x) h) (base []) xs .#. foldr (\y h -> push (second y) h) (base Nothing) ys where
  first _ Nothing = []
  first x (Just (y, xys)) = (x, y):xys

  second y xys = Just (y, xys)

Der Grund, warum über beiden Listen Angelegenheiten Falten ist wegen etwas GHC tut genannt Liste Fusion , die etwa in der Rede ist? der GHC.Base Modul , aber wahrscheinlich sollte viel mehr sein gut bekannt. Als eine gute Liste Produzent und mit build mit foldr viele nutzlose Produktion und den sofortigen Verzehr von Listenelementen verhindern, und können weitere Optimierungen aus.

Ich habe versucht, diese elegante Lösung selbst zu verstehen, so habe ich versucht, die Arten und die Auswertung selbst abzuleiten. Also, wir brauchen eine Funktion schreiben: 

zip xs ys = foldr step done xs ys

Hier müssen wir step und done ableiten, was auch immer sie sind. Es sei daran erinnert foldr 's Typ, instanziiert Listen: 

foldr :: (a -> state -> state) -> state -> [a] -> state

Doch unser foldr Aufruf muss wie unten etwas instanziert werden, weil wir nicht eine akzeptieren müssen, aber zwei Listen Argumente: 

foldr :: (a -> ? -> ?) -> ? -> [a] -> [b] -> [(a,b)]

Da -> rechtsassoziativ ist, ist dies gleichbedeutend mit: 

foldr :: (a -> ? -> ?) -> ? -> [a] -> ([b] -> [(a,b)])

Unser ([b] -> [(a,b)]) entspricht Typen Variable in dem ursprünglichen state Typ Signatur foldr, deshalb müssen wir jedes Vorkommen von state mit ersetzen: 

foldr :: (a -> ([b] -> [(a,b)]) -> ([b] -> [(a,b)]))
      -> ([b] -> [(a,b)])
      -> [a]
      -> ([b] -> [(a,b)])

Das bedeutet, dass die Argumente, die wir foldr passieren müssen die folgenden Typen haben: 

step :: a -> ([b] -> [(a,b)]) -> [b] -> [(a,b)]
done :: [b] -> [(a,b)]
xs :: [a]
ys :: [b]

Es sei daran erinnert, dass foldr (+) 0 [1,2,3] erweitert zu: 

1 + (2 + (3 + 0))

Wenn also xs = [1,2,3] und ys = [4,5,6,7], unsere foldr Aufruf würde erweitern: 

1 `step` (2 `step` (3 `step` done)) $ [4,5,6,7]

Das bedeutet, dass unser 1 `step` (2 `step` (3 `step` done)) Konstrukt muss eine rekursive Funktion erstellen, die durch [4,5,6,7] und zip die Elemente gehen würde. (Beachten Sie, dass, wenn einer der ursprünglichen Listen länger ist, werden die überschüssigen Werte weggeworfen). IOW, unser Konstrukt muss den Typ [b] -> [(a,b)] haben.

3 `step` done ist unser Basisfall, wo done ein Anfangswert, wie 0 in foldr (+) 0 [1..3]. Wir wollen nichts nach 3 zip, weil 3 der Endwert xs ist, so müssen wir die Rekursion beenden. Wie beurteilen Sie die Rekursion über die Liste in dem Basisfall beenden? Sie kehren leere Liste []. Aber Rückruf done Art Signatur: 

done :: [b] -> [(a,b)]

Deshalb können wir nicht nur [] zurückkehren, müssen wir eine Funktion zurück, die ignorieren würde, was er empfängt. Daher verwenden const : 

done = const [] -- this is equivalent to done = \_ -> []

Lassen Sie uns nun beginnen, herauszufinden, was step sollte. Es kombiniert einen Wert vom Typ a mit einer Funktion vom Typ [b] -> [(a,b)] und gibt eine Funktion vom Typ [b] -> [(a,b)].

In 3 `step` done wissen wir, dass der Ergebniswert, der später zu unserer Reißverschluss Liste gehen muss (3,6) werden (zu wissen, von den ursprünglichen xs und ys). 3 `step` done muss daher bewerten in: 

\(y:ys) -> (3,y) : done ys

Denken Sie daran, wir müssen eine Funktion zurückgeben, innerhalb dessen wir irgendwie die Elemente Reißverschluss, der obige Code ist, was Sinn und typechecks macht.

Nun, da wir davon ausgegangen, wie genau step sollte bewerten, lassen Sie uns die Auswertung weiter. Hier ist, wie alle Reduktionsschritte in unserer foldr Bewertung wie folgt aussehen: 

3 `step` done -- becomes
(\(y:ys) -> (3,y) : done ys)
2 `step` (\(y:ys) -> (3,y) : done ys) -- becomes
(\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys)
1 `step` (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) -- becomes
(\(y:ys) -> (1,y) : (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) ys)

Die Auswertung gibt Anlass zu dieser Implementierung von Schritt (beachten Sie, dass wir für ys Konto früh aus Elementen ausgeführt wird durch eine leere Liste zurückkehrt): 

step x f = \[] -> []
step x f = \(y:ys) -> (x,y) : f ys

So wird die volle Funktion zip wie folgt umgesetzt: 

zip :: [a] -> [b] -> [(a,b)]
zip xs ys = foldr step done xs ys
  where done = const []
        step x f [] = []
        step x f (y:ys) = (x,y) : f ys

PS: Wenn Sie von Eleganz Falten inspiriert sind, lesen Sie Schreiben foldl mit foldr und dann Graham Hutton Ein Tutorial über die Universalität und Ausdruckskraft der Falte .

Ein einfacher Ansatz: 

lZip, rZip :: Foldable t => [b] -> t a -> [(a, b)]

-- implement zip using fold?
lZip xs ys = reverse.fst $ foldl f ([],xs) ys
     where f  (zs, (y:ys)) x = ((x,y):zs, ys)

-- Or;
rZip xs ys = fst $ foldr f ([],reverse xs) ys
     where f x (zs, (y:ys))  = ((x,y):zs, ys)
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top