Gesetz für Typ [[a]] -> ([a], [a])

8

Ich versuche diese Frage aus meinen Hausaufgaben zu machen:

Wenn Sie willkürlich sind foo :: [[a]] -> ([a], [a]), schreiben Sie ein Gesetz auf, das die Funktion fooerfüllt, und zwar mapin Listen und Paaren.

Ein Zusammenhang: Ich bin ein Student im ersten Jahr, der einen Kurs in funktionaler Programmierung belegt. Während der Kurs eher einführend ist, hat der Dozent viele Dinge aus dem Lehrplan heraus erwähnt, darunter die freien Theoreme. Nachdem ich versucht hatte, Wadlers Artikel zu lesen, rechnete ich damit, dass concat :: [[a]] -> [a]das Gesetz map f . concat = concat . map (map f)für mein Problem relevant erscheint, da wir foo xss = (concat xss, concat' xss)wo concatund concat'welche Funktionen vom Typ haben müssen [[a]] -> [a]. Dann foobefriedigt bimap (map f, map g) . foo = \xss -> ((fst . foo . map (map f)) xss, (snd . foo . map (map g)) xss).

Schon dieses 'Gesetz' scheint zu lang, um richtig zu sein, und ich bin mir auch meiner Logik nicht sicher. Also habe ich darüber nachgedacht, einen kostenlosen Online-Theoremgenerator zu verwenden , aber ich verstehe nicht, was lift{(,)}bedeutet:

forall t1,t2 in TYPES, g :: t1 -> t2.
 forall x :: [[t1]].
  (f x, f (map (map g) x)) in lift{(,)}(map g,map g)

lift{(,)}(map g,map g)
  = {((x1, x2), (y1, y2)) | (map g x1 = y1) && (map g x2 = y2)}

Wie soll ich diese Ausgabe verstehen? Und wie soll ich das Gesetz für die Funktion foorichtig ableiten ?

haskell free-theorem Jingjie YANG
quelle
5
Ich glaube, das sagt das(\(a,b) -> (map f a, map f b)) . foo = foo . map (map f)
AJFarmar

Antworten:

4

Wenn R1und R2Beziehungen sind (sagen wir R_izwischen A_iund B_imit i in {1,2}), dann lift{(,)}(R1,R2)sind die "aufgehobenen" Beziehungspaare zwischen A1 * A2und B1 * B2mit der *Bezeichnung des Produkts (geschrieben (,)in Haskell).

In der gelebten Beziehung sind zwei Paare (x1,x2) :: A1*A2und (y1,y2) :: B1*B2genau dann verwandt, wenn x1 R1 y1und x2 R2 y2. In Ihrem Fall R1und R2sind Funktionen map g, map g, so dass das Heben auch eine Funktion wird : y1 = map g x1 && y2 = map g x2.

Daher das erzeugte

(f x, f (map (map g) x)) in lift{(,)}(map g,map g)

meint:

fst (f (map (map g) x)) = map g (fst (f x))
AND
snd (f (map (map g) x)) = map g (snd (f x))

oder mit anderen Worten:

f (map (map g) x) = (map g (fst (f x)), map g (snd (f x)))

was ich schreiben würde, mit Control.Arrow:

f (map (map g) x) = (map g *** map g) (f x)

oder sogar im punktfreien Stil:

f . map (map g) = (map g *** map g) . f

Dies ist keine Überraschung, da Sie fals geschrieben werden können

f :: F a -> G a
where F a = [[a]]
      G a = ([a], [a])

und F, Gsind functors (in Haskell bräuchten wir ein verwenden , newtypeeine Funktor Instanz zu definieren, aber ich werde das nicht angeben, da es irrelevant). In einem solchen häufigen Fall hat der freie Satz eine sehr schöne Form: für jeden g,

f . fmap_of_F g = fmap_of_G g . f

Dies ist eine sehr schöne Form, genannt fNatürlichkeit ( kann als natürliche Transformation in einer geeigneten Kategorie interpretiert werden). Beachten Sie, dass die beiden foben genannten s tatsächlich auf separaten Typen instanziiert werden, damit die Typen mit dem Rest übereinstimmen.

In Ihrem speziellen Fall ist es, da F a = [[a]]es die Zusammensetzung des []Funktors mit sich selbst ist, daher erhalten wir (nicht überraschend) fmap_of_F g = fmap_of_[] (fmap_of_[] g) = map (map g).

Stattdessen G a = ([a],[a])ist die Zusammensetzung der Funktoren []und H a = (a,a)(technisch gesehen diagonale Funktoren mit dem Produktfunktor zusammengesetzt). Wir haben fmap_of_H h = (h *** h) = (\x -> (h x, h x)), von denen fmap_of_G g = fmap_of_H (fmap_of_[] g) = (map g *** map g).

Chi
quelle
Schöne Erklärung! Nur eine Frage: Wenn Sie "für jedes g" sagen, muss g vollständig oder streng sein oder gibt es überhaupt keine Einschränkungen?
Jingjie YANG
1
@JingjieYANG Ja, es gibt einige Einschränkungen, wenn wir Haskell verwenden. Die meisten Ergebnisse wie dieses werden tatsächlich in einem reinen Typsystem erzielt, in dem jedes endet (daher ist es total). Wenn ich mich richtig erinnere, müssen wir in Haskell, da wir keine Kündigung haben, ginsgesamt verlangen . Ebenso müssen seqwir , da wir haben g, streng sein müssen. Ich bin mir über die genauen Einschränkungen nicht 100% sicher, aber ich denke, das sollte es sein. Ich kann mich jedoch nicht erinnern, wo ich darüber gelesen habe - wahrscheinlich gibt es auf der Seite mit dem kostenlosen Theoremgenerator einige Informationen.
Chi
Ist Control.Arrow (***) bei Tupeln nicht etwas aus der Mode gekommen, zugunsten von Data.Bifunctor (Bimap)? Haben Sie Einwände gegen eine Änderung, um zu letzterer zu wechseln?
Joseph Sible-Reinstate Monica
2
@ JosephSible-ReinstateMonica Ich habe keine Ahnung. Ich denke , es ist ein bisschen wie mapvs fmap. Die Leute benutzen weiter, mapda es offensichtlich ist, dass es sich um Listen handelt (und nicht um andere Funktionen). Ebenso (***)funktioniert nur bei Paaren (und nicht bei anderen Bifunktoren). Ich benutze es wahrscheinlich hauptsächlich wegen seiner Infix-Ness, da wir in der Mathematik dazu neigen, zu schreiben f \times g, um den Produkt-Bifunctor anzuwenden. Vielleicht bimapsollte es auch eine Infix-Variante geben, wie <$>es eine Variante für ist fmap.
Chi
1
Es ist zwar wahr, dass (***)es spezifischer ist, als bimapdass es nur für Paare und nicht für beliebige Bifunktoren funktioniert, aber es ist auch wahr, dass bimapes spezifischer ist, als (***)dass es nur für Funktionen und nicht für beliebige Pfeile funktioniert. Re infix, das wäre nicht ganz das gleiche für bimapund fmap, da bimap3 Parameter und fmapnur 2 benötigt.
Joseph Sible-Reinstate Monica
2

Das Gleiche wie die Antwort von @ chi mit weniger Zeremonie:

Es spielt keine Rolle, ob Sie das as bvor oder nach der Funktion in s ändern , Sie erhalten dasselbe (solange Sie ein fmapähnliches Element verwenden).

Für jedes f: a -> b,

    [[a]] -------------> [[b]]
      | (map.map) f |
      | |
     foo foo
      | |
      vv
    ([a], [a]) ---------> ([b], [b])
              bimap ff

pendelt.
luqui
quelle