Geek Answers Handbook

Type Juggling with Existentials in Runtime

I play with existences and GADT in Haskell, and I am trying to define DSL for combinators (e.g. SKI). GADT works for me, as well as a reduction function, which works fine (and has nothing to do with the issue)

{-# LANGUAGE GADTs, ExistentialQuantification #-}

import Control.Applicative
import Data.Monoid
import Control.Monad

data Comb t where
    S :: Comb ((a -> b -> c) -> (a -> b) -> a -> c)
    K :: Comb (a -> b -> a)
    I :: Comb (a -> a)
    B :: Comb ((b -> c) -> (a -> b) -> a -> c)
    C :: Comb ((b -> a -> c) -> a -> b -> c)
    W :: Comb ((a -> a -> b) -> a -> b)
    (:$) :: Comb (a -> b) -> Comb a -> Comb b

What I'm trying to do now is to determine how to read combinator strings from the user at runtime. Obviously, for this I need an existential type, since GADT type information must be hidden.

data CombBox = forall a. CombBox { unCombBox :: Comb a }

($$) :: CombBox -> CombBox -> Maybe CombBox
x $$ y = undefined -- ???

I would like the function to ($$)somehow look into the existence CombBoxat runtime, and if you can combine two combinators with :$and get a well-typed result, I would like the result to be like this. Otherwise I want to Nothing. For example,

CombBox S $$ CombBox K ==> Just (CombBox (S :$ K))
CombBox W $$ CombBox I ==> Nothing

, W 2- , I . , , Haskell (+ GHC).

+4
2

!

, .

-, Haskell , .

infixr 0 :->
data Type = Unit | Type :-> Type

, , .

Comb, .

data Comb a where
    S :: Comb ((a :-> b :-> c) :-> (a :-> b) :-> a :-> c)
    K :: Comb (a :-> b :-> a)
    (:$) :: Comb (a :-> b) -> Comb a -> Comb b

i = S :$ K :$ i
b = (S :$ (K :$ S)) :$ K
c = S :$ (S :$ (K :$ (S :$ (K :$ S) :$ K)) :$ S) :$ (K :$ K)
w = S :$ S :$ (S :$ K)

. , , , , .

data Ex f = forall a. Ex (f a)

: , ? a Comb , , Comb. .

data (f :*: g) i = f i :*: g i

( .) :*: , , . Ex -: , . , f GADT, - , f g.

type Sg f g = Ex (f :*: g)
pattern Sg x y = Ex (x :*: y)

: GADT, .

data Typey t where
    Unity :: Typey Unit
    Arry :: Typey a -> Typey b -> Typey (a :-> b)

Typey . t Typey t. , Typey t, , t.

. Typey Type; Type . , .

- . AComb a Comb . Comb; , .

type AComb = Sg Typey Comb

($$), AComb AComb? Typey, , . , , .

, GADT, . Refl, GHC, a b . , Refl, GHC a ~ b .

data a :~: b where
    Refl :: a :~: a
withEq :: a :~: b -> (a ~ b => r) -> r
withEq Refl x = x

:->.

arrEq :: (a :~: c) -> (b :~: d) -> (a :-> b) :~: (c :-> d)
arrEq Refl Refl = Refl

, , , Type. singleton Typey s, , . , , .

tyEq :: Typey t -> Typey u -> Maybe (t :~: u)
tyEq Unity Unity = Just Refl
tyEq (Arry a b) (Arry c d) = liftA2 arrEq (tyEq a c) (tyEq b d)
tyEq _ _ = Nothing

withTyEq :: Typey t -> Typey u -> (t ~ u => a) -> Maybe a
withTyEq t u x = fmap (\p -> withEq p x) (tyEq t u)

, $$. :

f : a -> b    y : a
------------------- App
      f y : b

, $$ , , . , ( withTyEq) , .

($$) :: AComb -> AComb -> Maybe AComb
Sg (Arry a b) x $$ Sg t y = withTyEq a t $ Sg b (x :$ y)
_ $$ _ = Nothing

Typey . , parse :: String -> AComb , . .

, , , .

data Expr = S | K | Expr :$ Expr
parse :: String -> Parser Expr
typeCheck :: Expr -> Maybe AComb

( ) typeCheck, , , -:

data Void : Set where
Not : Set -> Set
Not a = a -> Void

data TypeError : Expr -> Set where
    notArr : Not (IsFunction f) -> TypeError (f :$ x)
    mismatch : Not (domain f :~: type x) -> TypeError (f :$ x)
    inFunc : TypeError f -> TypeError (f :$ x)
    inArg : TypeError x -> TypeError (f :$ x)

typeCheck : (e : Expr) -> Either (TypeError e) AComb

typeCheck , , , ( ).

. , -.

+6

, .

, . Haskell Typeable:

deriving instance Typeable Comb

data CombBox = forall a. Typeable a => CombBox { unCombBox :: Comb a }

,

castApply1 :: (Typeable a, Typeable b, Typeable ab) => Comb ab -> Comb a -> Maybe (Comb b)
castApply1 f x = (:$ x) <$> cast f


($$) :: CombBox -> CombBox -> Maybe CombBox
CombBox f $$ CombBox x = CombBox <$> castApply f x


Could not deduce (Typeable a0) arising from a use of `CombBox' …
    from the context (Typeable a)
    or from (Typeable a1)
    The type variable `a0' is ambiguous

, b castApply1, CombBox castApply f x, b , , .

b, Proxy b :

castApply2 :: (Typeable a, Typeable b, Typeable ab) => Proxy b -> Comb ab -> Comb a -> Maybe (Comb b)
castApply2 p = castApply1

CombBox:

castApply3 :: (Typeable a, Typeable b, Typeable ab) => Proxy b -> Comb ab -> Comb a -> Maybe CombBox
castApply3 p f x = CombBox <$> castApply2 p f x

, , , , b:

data SomeTypeable = forall a. Typeable a => SomeTypeable (Proxy a)

castApply4 :: (Typeable a, Typeable ab) => SomeTypeable -> Comb ab -> Comb a -> Maybe CombBox
castApply4 (SomeTypeable p) = castApply3 p


typeRepToSomeTypeable :: TypeRep -> SomeTypeable


castApply :: (Typeable a, Typeable ab) => TypeRep -> Comb ab -> Comb a -> Maybe CombBox
castApply t = castApply4 (typeRepToSomeTypeable t)

($$) :: CombBox -> CombBox -> Maybe CombBox
CombBox f $$ CombBox x = funResultTy (typeRep f) (typeRep x) >>= \t -> castApply t f x

funResultTy - Data.Typeable, , .

typeRepToSomeTypeable? , . , Data.Typeable, Singletons.

+2

More articles:


All Articles