haskell - reservadas - Cómo generar funciones aleatorias tipadas.

imprimir en haskell

Question

Me gustaría generar mediante programación funciones aleatorias de Haskell y evaluarlas. Me parece que la única forma de hacer esto es básicamente generar el código de Haskell mediante programación y ejecutarlo mediante la API de GHC o un proceso externo, devolver una cadena y analizarla de nuevo en un tipo de datos de Haskell. ¿Es esto cierto?

Mi razonamiento es el siguiente. Las funciones son polimórficas, así que no puedo usar Typeable. Más importante aún, incluso si escribo mi propio verificador de tipos y anoto cada función con su tipo, no puedo demostrarle al compilador de Haskell que mi verificador de tipos es correcto. Por ejemplo, cuando saco dos funciones de una colección heterogénea de funciones y aplico una a la otra, necesito proporcionar al compilador una garantía de que la función que estoy usando para elegir estas funciones solo elige funciones con los tipos correspondientes. Pero no hay manera de hacer esto, ¿verdad?

Answer 1

¡Gracias por las respuestas muy detalladas de arriba! Sin embargo, ninguna de las respuestas hizo lo que estaba buscando. Seguí la sugerencia de DarkOtter en el comentario de la pregunta y utilicé unsafeCoerce evitar el corrector de tipos. La idea básica es que creamos un GADT que empaqueta las funciones de Haskell con sus tipos; el sistema de tipos que utilizo sigue muy de cerca a Mark P. Jones en "Typing Haskell in Haskell". Siempre que quiero una colección de funciones de Haskell, primero las coacciono en Any tipo, luego hago lo que necesito hacer, uniéndolas al azar. Cuando voy a evaluar las nuevas funciones, primero las coacciono para que vuelvan al tipo que yo quería. Por supuesto, esto no es seguro; si mi verificador de tipos es incorrecto o anoto las funciones de haskell con tipos incorrectos, entonces termino con tonterías.

He pegado el código con el que he probado esto a continuación. Tenga en cuenta que se están importando dos módulos locales, Strappy.Type y Strappy.Utils . El primero es el sistema de tipos mencionado anteriormente. El segundo trae ayudantes para los programas estocásticos.

Nota: en el código a continuación estoy usando la lógica combinatoria como el lenguaje básico. Es por eso que mi lenguaje de expresión solo tiene aplicación y no tiene variables o abstracción lambda.

{-# Language GADTs, ScopedTypeVariables #-}
import Prelude hiding (flip)
import qualified Data.List as List
import Unsafe.Coerce (unsafeCoerce)
import GHC.Prim
import Control.Monad
import Control.Monad.State
import Control.Monad.Trans
import Control.Monad.Identity
import Control.Monad.Random
import Strappy.Type
import Strappy.Utils (flip)
-- | Helper for turning a Haskell type to Any.
mkAny :: a -> Any
mkAny x = unsafeCoerce x
-- | Main data type. Holds primitive functions (Term), their
-- application (App) and annotations.
data Expr a where
Term :: {eName :: String,
eType :: Type,
eThing :: a} -> Expr a
App :: {eLeft :: (Expr (b -> a)),
eRight :: (Expr b),
eType :: Type} -> Expr a
-- | smart constructor for applications
a <> b = App a b (fst . runIdentity . runTI $ typeOfApp a b)
instance Show (Expr a) where
show Term{eName=s} = s
show App{eLeft=el, eRight=er} = "(" ++ show el ++ " " ++ show er ++ ")"
-- | Return the resulting type of an application. Run''s type
-- unification.
typeOfApp :: Monad m => Expr a -> Expr b -> TypeInference m Type
typeOfApp e_left e_right
= do t <- newTVar Star
case mgu (eType e_left) (eType e_right ->- t) of
(Just sub) -> return $ toType (apply sub (eType e_left))
Nothing -> error $ "typeOfApp: cannot unify " ++
show e_left ++ ":: " ++ show (eType e_left)
++ " with " ++
show e_right ++ ":: " ++ show (eType e_right ->- t)
eval :: Expr a -> a
eval Term{eThing=f} = f
eval App{eLeft=el, eRight=er} = (eval el) (eval er)
filterExprsByType :: [Any] -> Type -> TypeInference [] Any
filterExprsByType (e:es) t
= do et <- freshInst (eType (unsafeCoerce e :: Expr a))
let e'' = unsafeCoerce e :: Expr a
case mgu et t of
Just sub -> do let eOut = unsafeCoerce e''{eType = apply sub et} :: Any
return eOut `mplus` rest
Nothing -> rest
where rest = filterExprsByType es t
filterExprsByType [] t = lift []
----------------------------------------------------------------------
-- Library of functions
data Library = Library { probOfApp :: Double, -- ^ probability of an expansion
libFunctions :: [Any] }
cInt2Expr :: Int -> Expr Int
-- | Convert numbers to expressions.
cInt2Expr i = Term (show i) tInt i
-- Some basic library entires.
t = mkTVar 0
t1 = mkTVar 1
t2 = mkTVar 2
t3 = mkTVar 3
cI = Term "I" (t ->- t) id
cS = Term "S" (((t2 ->- t1 ->- t) ->- (t2 ->- t1) ->- t2 ->- t)) $ /f g x -> (f x) (g x)
cB = Term "B" ((t1 ->- t) ->- (t2 ->- t1) ->- t2 ->- t) $ /f g x -> f (g x)
cC = Term "C" ((t2 ->- t1 ->- t2 ->- t) ->- t1 ->- t2 ->- t) $ /f g x -> (f x) g x
cTimes :: Expr (Int -> Int -> Int)
cTimes = Term "*" (tInt ->- tInt ->- tInt) (*)
cPlus :: Expr (Int -> Int -> Int)
cPlus = Term "+" (tInt ->- tInt ->- tInt) (+)
cCons = Term ":" (t ->- TAp tList t ->- TAp tList t) (:)
cAppend = Term "++" (TAp tList t ->- TAp tList t ->- TAp tList t) (++)
cHead = Term "head" (TAp tList t ->- t) head
cMap = Term "map" ((t ->- t1) ->- TAp tList t ->- TAp tList t1) map
cEmpty = Term "[]" (TAp tList t) []
cSingle = Term "single" (t ->- TAp tList t) $ /x -> [x]
cRep = Term "rep" (tInt ->- t ->- TAp tList t) $ /n x -> take n (repeat x)
cFoldl = Term "foldl" ((t ->- t1 ->- t) ->- t ->- (TAp tList t1) ->- t) $ List.foldl''
cNums = [cInt2Expr i | i <- [1..10]]
-- A basic library
exprs :: [Any]
exprs = [mkAny cI,
mkAny cS,
mkAny cB,
mkAny cC,
mkAny cTimes,
mkAny cCons,
mkAny cEmpty,
mkAny cAppend,
-- mkAny cHead,
mkAny cMap,
mkAny cFoldl,
mkAny cSingle,
mkAny cRep
]
++ map mkAny cNums
library = Library 0.3 exprs
-- | Initializing a TypeInference monad with a Library. We need to
-- grab all type variables in the library and make sure that the type
-- variable counter in the state of the TypeInference monad is greater
-- that that counter.
initializeTI :: Monad m => Library -> TypeInference m ()
initializeTI Library{libFunctions=es} = do put (i + 1)
return ()
where go n (expr:rest) = let tvs = getTVars (unsafeCoerce expr :: Expr a)
getTVars expr = tv . eType $ expr
m = maximum $ map (readId . tyVarId) tvs
in if null tvs then 0 else go (max n m) rest
go n [] = n
i = go 0 es
----------------------------------------------------------------------
----------------------------------------------------------------------
-- Main functions.
sampleFromExprs :: (MonadPlus m, MonadRandom m) =>
Library -> Type -> TypeInference m (Expr a)
-- | Samples a combinator of type t from a stochastic grammar G.
sampleFromExprs lib@Library{probOfApp=prApp, libFunctions=exprs} tp
= do initializeTI lib
tp'' <- freshInst tp
sample tp''
where sample tp = do
shouldExpand <- flip prApp
case shouldExpand of
True -> do t <- newTVar Star
(e_left :: Expr (b -> a)) <- unsafeCoerce $ sample (t ->- tp)
(e_right :: Expr b) <- unsafeCoerce $ sample (fromType (eType e_left))
return $ e_left <> e_right -- return application
False -> do let cs = map fst . runTI $ filterExprsByType exprs tp
guard (not . null $ cs)
i <- getRandomR (0, length cs - 1)
return $ unsafeCoerce (cs !! i)
----------------------------------------------------------------------
----------------------------------------------------------------------
main = replicateM 100 $
do let out = runTI $ do sampleFromExprs library (TAp tList tInt)
x <- catch (liftM (Just . fst) out)
(/_ -> putStrLn "error" >> return Nothing)
case x of
Just y -> putStrLn $ show x ++ " " ++ show (unsafeCoerce (eval y) :: [Int])
Nothing -> putStrLn ""

Answer 2

¿Algo en esta línea satisfaría sus necesidades?

import Control.Monad.Random
randomFunction :: (RandomGen r, Random a, Num a, Floating a) => Rand r (a -> a)
randomFunction = do
(a:b:c:d:_) <- getRandoms
fromList [(/x -> a + b*x, 1), (/x -> a - c*x, 1), (/x -> sin (a*x), 1)]
-- Add more functions as needed
main = do
let f = evalRand randomFunction (mkStdGen 1) :: Double -> Double
putStrLn . show $ f 7.3

EDITAR: Basándonos en esa idea, podríamos incorporar funciones que tengan diferentes números y tipos de parámetros ... siempre que los apliquemos parcialmente para que todos tengan el mismo tipo de resultado.

import Control.Monad.Random
type Value = (Int, Double, String) -- add more as needed
type Function = Value -> String -- or whatever the result type is
f1 :: Int -> Int -> (Int, a, b) -> Int
f1 a b (x, _, _) = a*x + b
f2 :: String -> (a, b, String) -> String
f2 s (_, _, t) = s ++ t
f3 :: Double -> (a, Double, b) -> Double
f3 a (_, x, _) = sin (a*x)
randomFunction :: RandomGen r => Rand r Function
randomFunction = do
(a:b:c:d:_) <- getRandoms -- some integers
(w:x:y:z:_) <- getRandoms -- some floats
n <- getRandomR (0,100)
cs <- getRandoms -- some characters
let s = take n cs
fromList [(show . f1 a b, 1), (show . f2 s, 1), (show . f3 w, 1)]
-- Add more functions as needed
main = do
f <- evalRandIO randomFunction :: IO Function
g <- evalRandIO randomFunction :: IO Function
h <- evalRandIO randomFunction :: IO Function
putStrLn . show $ f (3, 7.3, "hello")
putStrLn . show $ g (3, 7.3, "hello")
putStrLn . show $ h (3, 7.3, "hello")

Answer 3

El comentario de DarkOtter menciona las clases Arbitrary y Arbitrary de QuickCheck, que ciertamente son lo primero que debe intentar. QuickCheck tiene esta instancia:

instance (CoArbitrary a, Arbitrary b) => Arbitrary (a -> b) where ...

Como sucedió, ayer estaba leyendo el código de QuickCheck para entender cómo funciona esto, así que puedo compartir lo que aprendí mientras estoy fresco en mi mente. QuickCheck se basa en un tipo que se ve así (y no será exactamente el mismo):

type Size = Int
-- | A generator for random values of type @a@.
newtype Gen a =
MkGen { -- | Generate a random @a@ using the given randomness source and
-- size.
unGen :: StdGen -> Size -> a
}
class Arbitrary a where
arbitrary :: a -> Gen a

El primer truco es que QuickCheck tiene una función que funciona así (y no entendí exactamente cómo se implementó):

-- | Use the given ''Int'' to /"perturb/" the generator, i.e., to make a new
-- generator that produces different pseudorandom results than the original.
variant :: Int -> Gen a -> Gen a

Luego lo usan para implementar varias instancias de esta clase CoArbitrary :

class CoArbitrary a where
-- | Use the given `a` to perturb some generator.
coarbitrary :: a -> Gen b -> Gen b
-- Example instance: we just treat each ''Bool'' value as an ''Int'' to perturb with.
instance CoArbitrary Bool where
coarbitrary False = variant 0
coarbitrary True = variant 1

Ahora con estas piezas en su lugar, queremos esto:

instance (Coarbitrary a, Arbitrary b) => Arbitrary (a -> b) where
arbitrary = ...

No escribiré la implementación, pero la idea es esta:

1. Usando la instancia CoArbitrary de a y la instancia Arbitrary de b podemos hacer que la función /a -> coarbitrary a arbitrary , que tiene el tipo a -> Gen b .
2. Recuerde que Gen b es un newtype para StdGen -> Size -> b , por lo que el tipo a -> Gen b es isomorfo a a -> StdGen -> Size -> b .
3. Podemos escribir de forma trivial una función que toma cualquier función de este último tipo y cambia el orden de los argumentos para devolver una función de tipo StdGen -> Size -> a -> b .
4. Este tipo reordenado es isomorfo a Gen (a -> b) , así que voilà, empaquetamos la función reordenada en un Gen , ¡y obtuvimos nuestro generador de funciones aleatorias!

Te recomendaría que leas la fuente de QuickCheck para ver esto por ti mismo. Cuando aborde eso, solo se encontrará con dos detalles adicionales que podrían ralentizarlo. Primero, la clase Haskell RandomGen tiene este método:

-- | The split operation allows one to obtain two distinct random generators.
split :: RandomGen g => g -> (g, g)

Esta operación se utiliza en la instancia de Monad para Gen , y es bastante importante. Uno de los trucos aquí es que el StdGen es un generador de números pseudoaleatorios puro; la forma en que Gen (a -> b) funciona es que para cada valor posible de a perturbamos un generador b , usamos ese generador perturbado para generar el resultado b , pero nunca avanzamos el estado del generador perturbado ; básicamente, la función a -> b generada es un cierre sobre una semilla pseudoaleatoria, y cada vez que la llamamos con alguna a , usamos esa a específica para crear deterministicamente una nueva semilla, y luego la usamos para generar de manera determinística una b que depende en a y la semilla oculta.

El tipo abreviado Seed -> a -> b más o menos resume lo que está sucediendo: una función pseudoaleatoria es una regla para generar una b partir de una semilla pseudoaleatoria y una a . Esto no funcionará con generadores de números aleatorios de estado imperativo.

Segundo: en lugar de tener directamente una función (a -> StdGen -> Size -> b) -> StdGen -> Size -> a -> b como describí anteriormente, el código QuickCheck tiene promote :: Monad m => m (Gen a) -> Gen (ma) , que es la generalización de eso a cualquier Monad . Cuando m es la instancia de función de Monad , la promote coincide con (a -> Gen b) -> Gen (a -> b) , por lo que realmente es lo mismo que dibujé anteriormente.