Allgemein Variante bi fab = (fa, fb)

Question

Gibt es eine typsichere Art und Weise eine Funktion

bi f a b = (f a, f b) 

, so dass sie es zu benutzen, wie dies möglich wäre, zu schreiben:

x1 :: (Integer, Char) 
x1 = bi head [2,3] "45" 

x2 :: (Integer, Char) 
x2 = bi fst (2,'3') ('4',5) 

x3 :: (Integer, Double) 
x3 = bi (1+) 2 3.45 

? In rank-n-Typen Beispiele gibt es etwas viel einfacher wie

g :: (forall a. a -> a) -> a -> a -> (a, a) 
g f a b = (f a, f b) 

Answer 1

Ja, wenn auch nicht in Haskell. Aber je höher Ordnung polymorphe Lambda-Kalkül (auch bekannt als System F-Omega) ist allgemeiner:

bi : forall m n a b. (forall a. m a -> n a) -> m a -> m b -> (n a, n b) 
bi {m} {n} {a} {b} f x y = (f {a} x, f {b} y) 

x1 : (Integer, Char) 
x1 = bi {\a. List a} {\a. a} {Integer} {Char} head [2,3] "45" 

x2 : (Integer, Char) 
x2 = bi {\a . exists b. (a, b)} {\a. a} {Integer} {Char} (\{a}. \p. unpack<b,x>=p in fst {a} {b} x) (pack<Char, (2,'3')>) (pack<Integer, ('4',5)>) 

x3 : (Integer, Double) 
x3 = bi {\a. a} {\a. a} {Integer} {Double} (1+) 2 3.45 

Hier schreibe ich f {T} für explizite Art Anwendung und übernehmen jeweils eine Bibliothek eingegeben haben. Etwas wie \a. a ist ein Lambda auf Typpegel. Das x2 Beispiel ist komplizierter, weil es auch existentielle Typen benötigt, um das andere Bit des Polymorphismus in den Argumenten lokal zu "vergessen".

Sie können dies tatsächlich simulieren in Haskell einen newtype oder Datentyp für jedes unterschiedliche m durch die Definition oder n Sie instanziiert mit und entsprechend eingewickelt Funktionen f übergeben, die hinzufügen und Konstrukteuren entsprechend entfernen. Aber das macht natürlich keinen Spaß.

bearbeiten: Ich sollte, dass dies immer noch darauf hinweisen, ist kein voll allgemeine Lösung. Zum Beispiel kann ich nicht sehen, wie Sie selbst in System F-Omega

eingeben können.Das Problem ist, dass die swap Funktion polymorpher ist als bi ermöglicht, und im Gegensatz zu x2, wird die andere polymorphe Dimension nicht im Ergebnis vergessen, so dass der existenzielle Trick nicht funktioniert. Es scheint, dass Sie einen guten Polymorphismus benötigen würden, um diesen zuzulassen (so dass das Argument zu bi über eine variierende Anzahl von Typen polymorph sein kann).

Answer 2

Auch immer mit ConstraintKinds, ich denke, die Barriere auf die Ergebnisse über die „Art-Funktion“ von den Argumenten der Quantifizierung werden wird. Was Sie wollen ist für f zu Karte a -> b und c -> d, und nehmen a -> b -> (c, d), aber ich glaube nicht, gibt es eine Möglichkeit, über diese Beziehung mit voller Allgemeinheit zu quantifizieren.

Einige Sonderfälle könnte machbar sein, aber:

(forall x . cxt x => x -> f x) -> a -> b -> (f a, f b) 
-- e.g. return 

(forall x . cxt x => f x -> x) -> f a -> f b -> (a, b) 
-- e.g. snd 
(forall x . cxt x => x -> x) -> a -> b -> (a, b) 
-- e.g. (+1) 

aber wenn man bedenkt, dass Sie versuchen, beliebige Art Funktionen mehr oder weniger zu quantifizieren über, ich bin nicht sicher, dass Sie diese Arbeit machen kann.

Answer 3

Das ist etwa so nah wie Sie bekommen werden, denke ich:

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-} 
module Data.Function.Bi (bi, Fn(..)) 

bi :: (Fn i a a', Fn i b b') => i -> a -> b -> (a', b') 
bi i a b = (fn i a, fn i b) 

class Fn i x x' | i x -> x' where 
     fn :: i -> x -> x' 

Verwenden Sie es wie folgt:

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, RankNTypes, 
      FlexibleInstances, UndecidableInstances #-} 
import Data.Function.Bi 

data Snd = Snd 

instance Fn Snd (a, b) b where 
     fn Snd = snd 

myExpr1 :: (Int, String) 
myExpr1 = bi Snd (1, 2) ("a", "b") 
-- myExpr == (2, "b") 

data Plus = Plus (forall a. (Num a) => a) 

instance (Num a) => Fn Plus a a where 
     fn (Plus n) = (+n) 

myExpr2 :: (Int, Double) 
myExpr2 = bi (Plus 1) (1, 2) (1.3, 5.7) 
-- myExpr2 == (3, 6.7) 

Es ist sehr klobig, aber so allgemein wie möglich.

Answer 4

{-# LANGUAGE TemplateHaskell #-} 

bi f = [| \a b -> ($f a, $f b)|] 

 

ghci> :set -XTemplateHaskell 
ghci> $(bi [|head|]) [2,3] "45" 
(2,'4') 

;)