2012-05-27 17 views
13

¿Hay alguna forma de tipo seguro para escribir una funciónvariante genérica del bi fab = (fa, fb)

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

de tal manera que sería posible utilizar de esta manera:

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 

? En ejemplos de rango-n-tipos siempre hay algo mucho más simple como

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

No lo creo. Tendría que cuantificarlo en todos los tipos de entrada, lo que requiere un resumen sobre las restricciones de clase de clase. –

+0

@LouisWasserman, hay algunas cosas nuevas (ConstraintKinds) que permiten abstraer las restricciones. – aemxdp

+0

Bien, veo eso, pero no creo que puedas cuantificar los tipos de resultados como lo harías. Si tuviera la forma 'a -> a', podría hacer' bi :: (cxt a, cxt b) => (forall x. Cxt x => x -> x) -> a -> b -> (a, b) ', pero no creo que pueda obtener automáticamente la" función de tipo "de cada entrada para su tipo de resultado. –

Respuesta

4

Sí, aunque no en Haskell. Pero la orden superior cálculo lambda polimórfica (también conocido como Sistema F-omega) es más general:

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 

Aquí, escribo f {T} para la aplicación explícita de tipos y asumir una biblioteca mecanografiado, respectivamente. Algo como \a. a es un lambda de tipo de nivel. El ejemplo x2 es más intrincado, porque también necesita tipos existenciales para "olvidar" localmente el otro fragmento de polimorfismo en los argumentos.

En realidad se puede simular esta en Haskell definiendo un newtype o tipo de datos diferente para cada m o n se ejemplariza con, y pase funciones adecuadamente envueltos f que agregar y quitar constructores en consecuencia. Pero, obviamente, eso no es divertido en absoluto.

Editar: Debo señalar que esto todavía no es una solución general totalmente. Por ejemplo, no puedo ver cómo se puede escribir

swap (x,y) = (y,x) 
x4 = bi swap (3, "hi") (True, 3.1) 

incluso en el Sistema F-omega.El problema es que la función swap es más polimórfica que bi y, a diferencia de x2, la otra dimensión polimórfica no se olvida en el resultado, por lo que el truco existencial no funciona. Parece que necesitarías un polimorfismo bueno para permitirlo (de modo que el argumento bi puede ser polimórfico en un número variable de tipos).

3

Incluso con ConstraintKinds, creo que la barrera se va a cuantificar el "tipo de función" de los argumentos de los resultados. Lo que quiere es para f para mapear a -> b y c -> d, y para tomar a -> b -> (c, d), pero no creo que haya ninguna forma de cuantificar esa relación con total generalidad.

Algunos casos especiales pueden ser factible, sin embargo:

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

pero dado que usted está tratando de cuantificar sobre funciones de tipo más o menos arbitrarias, no estoy seguro de que puede hacer ese trabajo.

+0

Parece que tienes razón sobre el caso general, gracias. – aemxdp

2

Esto es lo más cerca que se va a conseguir, creo:

{-# 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' 

usarlo como así:

{-# 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 muy torpe, pero lo más general posible.

+0

Hay varios errores en este código. Primero, una instancia de 'Fn' toma tres argumentos, que no es el caso en' Fn (Plus a) '. Segundo, el tipo de 'Plus' es' * 'así que' Plus a' no es válido. Por último, necesita 'FlexibleInstances' ya que la variable de tipo' b' aparece dos veces en la instancia 'Snd'. – is7s

+0

@ is7s ¡Solucionado, lo siento! –

+0

truco interesante, gracias. – aemxdp

6
{-# LANGUAGE TemplateHaskell #-} 

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

 

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

;)

+0

upvote por valor de la comedia: P –