Cómo puedo abstraer un aplicativo recursiva patrón común funtor Haskell

Question

Durante el uso de los funtores aplicativos en Haskell A menudo me he encontrado con situaciones en las que terminan con código repetitivo como esto:

instance Arbitrary MyType where 
    arbitrary = MyType <$> arbitrary <*> arbitrary <*> arbitrary <*> arbitrary 

En este ejemplo me gustaría gusta decir:

instance Arbitrary MyType where 
    arbitrary = applyMany MyType 4 arbitrary 

pero no puedo encontrar la manera de hacer applyMany (o algo similar). Ni siquiera puedo averiguar cuál sería el tipo, pero tomaría un constructor de datos, un Int (n), y una función para aplicar n veces. Esto ocurre al crear instancias para QuickCheck, SmallCheck, Data.Binary, serialización Xml y otras situaciones recursivas.

Entonces, ¿cómo podría definir applyMany?

Answer 1

Creo que se puede hacer con OverlappingInstances piratear:

{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, TypeFamilies, OverlappingInstances #-} 
import Test.QuickCheck 
import Control.Applicative 


class Arbitrable a b where 
    convert :: Gen a -> Gen b 

instance (Arbitrary a, Arbitrable b c) => Arbitrable (a->b) c where 
    convert a = convert (a <*> arbitrary) 

instance (a ~ b) => Arbitrable a b where 
    convert = id 

-- Should work for any type with Arbitrary parameters 
data MyType a b c d = MyType a b c d deriving (Show, Eq) 

instance Arbitrary (MyType Char Int Double Bool) where 
    arbitrary = convert (pure MyType) 

check = quickCheck ((\s -> s == s) :: (MyType Char Int Double Bool -> Bool)) 

Answer 2

Esto no es posible con Haskell. El problema es que su función tendrá un tipo que depende del argumento numérico. Con un sistema tipo que permite tipos dependientes, eso debería ser posible, pero supongo que no en Haskell.

Lo que puedes probar es utilizar polimorfismo y tyeclasses para archivar esto, pero podría convertirse en hacky y necesitarás un gran grupo de extensiones para satisfacer al compilador.

Answer 3

Consulte derive. Cualquier otra buena genoteca también debería poder hacer esto; derivar es solo el que estoy familiarizado. Por ejemplo:

{-# LANGUAGE TemplateHaskell #-} 
import Data.DeriveTH 
import Test.QuickCheck 

$(derive makeArbitrary ''MyType) 

Para abordar la cuestión en realidad se le pide, FUZxxl es correcto, esto no es posible en la llanura de vainilla Haskell. Como usted señala, no está claro cuál debería ser su tipo. Es posible con la metaprogramación de Template Haskell (no demasiado agradable). Si vas por esa ruta, probablemente solo deberías usar una biblioteca de genéricos que ya ha hecho la investigación más difícil para ti. También creo que es posible usar tipos naturales y clases de tipos de tipo, pero desafortunadamente estas soluciones a nivel de tipo suelen ser difíciles de abstraer. Conor McBride es working on that problem.

Answer 4

Echa un vistazo liftA2 and liftA3. También, puede escribir fácilmente sus propios métodos applyTwice o applyThrice así:

applyTwice :: (a -> a -> b) -> a -> b 
applyTwice f x = f x x 

applyThrice :: (a -> a -> a -> b) -> a -> b 
applyThrice f x = f x x x 

No hay manera fácil Veo a conseguir el applyMany genérica que está pidiendo, pero escribir ayudantes triviales como estos no es ni difícil ni raro

---

[editar] Así que resulta, se podría pensar algo como esto funcionaría

liftA4 f a b c d = f <$> a <*> b <*> c <*> d 
quadraApply f x = f x x x x 

data MyType = MyType Int String Double Char 

instance Arbitrary MyType where 
    arbitrary = (liftA4 MyType) `quadraApply` arbitrary 

pero no es así. (liftA4 MyType) tiene una firma tipo de (Applicative f) => f Int -> f String -> f Double -> f Char -> f MyType. Esto es incompatible con el primer parámetro de quadraApply, que tiene una firma de tipo (a -> a -> a -> a -> b) -> a -> b. Solo funcionaría para las estructuras de datos que contienen múltiples valores del mismo tipo arbitrario.

data FourOf a = FourOf a a a a 

instance (Arbitrary a) => Arbitrary (FourOf a) where 
    arbitrary = (liftA4 FourOf) `quadraApply` arbitrary 

ghci> sample (arbitrary :: Gen (FourOf Int)) 

Por supuesto que sólo podría hacerlo si tuviera esa situación

ghci> :l +Control.Monad 
ghci> let uncurry4 f (a, b, c, d) = f a b c d 
ghci> samples <- sample (arbitrary :: Gen (Int, Int, Int, Int)) 
ghci> forM_ samples (print . uncurry4 FourOf) 

Puede haber alguna pragma lenguaje que puede meter con calzador la función de "arbitraria" en los más diversos tipos de datos. Pero eso actualmente está más allá de mi nivel de Haskell-fu.

Answer 5

Esto es lo que Me'v tiene al menos:

{-# LANGUAGE TypeFamilies, MultiParamTypeClasses, FlexibleInstances #-} 
{-# LANGUAGE FlexibleContexts #-} 

module ApplyMany where 

import Control.Applicative 
import TypeLevel.NaturalNumber -- from type-level-natural-number package 

class GetVal a where 
    getVal :: a 

class Applicative f => ApplyMany n f g where 
    type Res n g 
    app :: n -> f g -> f (Res n g) 

instance Applicative f => ApplyMany Zero f g where 
    type Res Zero g = g 
    app _ fg = fg 

instance 
    (Applicative f, GetVal (f a), ApplyMany n f g) 
    => ApplyMany (SuccessorTo n) f (a -> g) 
    where 
    type Res (SuccessorTo n) (a -> g) = Res n g 
    app n fg = app (predecessorOf n) (fg<*>getVal) 

Ejemplo de uso:

import Test.QuickCheck 

data MyType = MyType Char Int Bool deriving Show 
instance Arbitrary a => GetVal (Gen a) where getVal = arbitrary 

test3 = app n3 (pure MyType) :: Gen MyType 
test2 = app n2 (pure MyType) :: Gen (Bool -> MyType) 
test1 = app n1 (pure MyType) :: Gen (Int -> Bool -> MyType) 
test0 = app n0 (pure MyType) :: Gen (Char -> Int -> Bool -> MyType) 

Por cierto, Creo que esta solución no es muy útil en el mundo real. Especialmente sin clases de tipos locales.

Answer 6

No estoy satisfecho con mi otra respuesta, he encontrado una más impresionante.

-- arb.hs 
import Test.QuickCheck 
import Control.Monad (liftM) 

data SimpleType = SimpleType Int Char Bool String deriving(Show, Eq) 
uncurry4 f (a,b,c,d) = f a b c d 

instance Arbitrary SimpleType where 
    arbitrary = uncurry4 SimpleType `liftM` arbitrary 
    --^this line is teh pwnzors. 
    -- Note how easily it can be adapted to other "simple" data types 

---

ghci> :l arb.hs 
[1 of 1] Compiling Main    (arb.hs, interpreted) 
Ok, modules loaded: Main. 
ghci> sample (arbitrary :: Gen SimpleType) 
>>>a bunch of "Loading package" statements<<< 
SimpleType 1 'B' False "" 
SimpleType 0 '\n' True "" 
SimpleType 0 '\186' False "\208! \227" 
... 

larga explicación de cómo me di cuenta de esto

Así que aquí es como lo tengo. ?. Me preguntaba, "bien cómo es ya una instancia Arbitrary para (Int, Int, Int, Int) Estoy seguro de que nadie escribió ella, por lo que debe derivarse de alguna manera Efectivamente, encontré lo siguiente en el docs for instances of Arbitrary:

(Arbitrary a, Arbitrary b, Arbitrary c, Arbitrary d) => Arbitrary (a, b, c, d) 

Bueno, si ya tienen que definirse, entonces por qué no abusar de ella? los tipos simples que son sólo está formada por tipos de datos arbitrarios más pequeños no son muy diferentes que una tupla.

Así que ahora tengo que transformar de alguna manera el " arbitrario "método para la 4-tupla para que funcione para mi tipo. Es probable que haya deslices.

Parada. Hoogle tiempo!

(Podemos definir fácilmente nuestra propia uncurry4, por lo que asumir que ya tenemos esto para operar.)

Tengo un generador, arbitrary :: Gen (q,r,s,t) (donde q, r, s, t son todas las instancias de arbitraria). Pero digamos que es arbitrary :: Gen a. En otras palabras, a representa (q,r,s,t). Tengo una función, uncurry4, que tiene el tipo (q -> r -> s -> t -> b) -> (q,r,s,t) -> b. Obviamente vamos a aplicar uncurry4 a nuestro SimpleType constructor. Entonces, uncurry4 SimpleType tiene el tipo (q,r,s,t) -> SimpleType. Sin embargo, vamos a mantener el valor de retorno genérico, porque Hoogle no conoce nuestro SimpleType. Así que recordando nuestra definición de a, tenemos esencialmente uncurry4 SimpleType :: a -> b.

Así que tengo un Gen a y una función a -> b. Y quiero un resultado de Gen b.(Recuerde, para nuestra situación, a es (q,r,s,t) y b es SimpleType). Así que estoy buscando una función con esta firma de tipo: Gen a -> (a -> b) -> Gen b. Hoogling that, y sabiendo que Gen es una instancia de Monad, reconozco inmediatamente liftM como la solución mágico-monádica a mis problemas.

Hoogle vuelve a salvar el día. Sabía que probablemente había algún combinador de "elevación" para obtener el resultado deseado, pero honestamente no pensé usar LiftM (durrr!) Hasta que encontré la firma de tipo.