% Generic Operations on Lazy Non-Deterministic Data % Sebastian Fischer (sebf@informatik.uni-kiel.de) This module provides generic operations on the datatypes used internally for constraint functional-logic programming. We cannot use the `Data.Data` class, because we also want to handle functions. `Typeable` or `DrIFT` may be applicable, however, to derive some of the instances for classes defined in this module. > {-# LANGUAGE TypeFamilies #-} > > module CFLP.Data.Generic ( > > Generic(..), GenericOps, generic, primitive, consLabels, > > ApplyCons(..), Decons, (!), cons > > ) where > > import Data.Maybe > > import CFLP.Data.Types Here is a record with generic operations: > data GenericOps a = GenericOps { The operation `gen` converts a value of type `a` into the generic normal-form representation. > gen :: a -> Maybe NormalForm , The operation `prim` converts a normal form into a primitive Haskell value of type `a`. > prim :: NormalForm -> Maybe a , The field `labels` stores a list of `ConsLabels` corresponding to the constructors of a datatype. > labels :: [ConsLabel] } The generic operations `gen` and `prim` return optional results. However, failure is only used internally and there are wrapper functions that always succeed: > generic :: Generic a => a -> NormalForm > generic = fromJust . gen genericOps > > primitive :: Generic a => NormalForm -> a > primitive = fromJust . prim genericOps The operation `consLabels` yields the list of constructors corresponding to a datatype `a`. > consLabels :: Generic a => a -> [ConsLabel] > consLabels x = labels (genericOps `forTypeOf` x) > > forTypeOf :: GenericOps a -> a -> GenericOps a > forTypeOf = const The operation `genericOps` is defined in the type class `Generic`: > class Generic a > where > genericOps :: GenericOps a > genericOps = constr 0 > > constr :: Int -> GenericOps a > constr _ = error "Generic.constr: not implemented" Primitive Haskell types that should be convertible to be used in constraint functional-logic programs need to be instances of `Generic`. The operation `genericOps` has a default implementation in terms of `constr` to simplify the definition of instances for *data*types. The instance for function types defines `genericOps` directly: > instance (Generic a, Generic b) => Generic (a -> b) > where > genericOps = GenericOps { > gen = \ f -> Just (Fun (generic . f . primitive)) , > prim = \ (Fun f) -> Just (primitive . f . generic ) , > labels = [] } Defining Instances ================== We provide combinators to simplify the definition of `Generic` instances for datatypes. For example, the instance for booleans looks like this: > instance Generic Bool > where > constr = cons "False" False dFalse ! cons "True" True dTrue The arguments `dFalse` and `dTrue` are deconstructors for the corresponding constructors: > type Decons a = ([NormalForm] -> NormalForm) -> Result a -> Maybe NormalForm The type `Result a` used in the type of deconstructors is associated to the type class `ApplyCons`. > class ApplyCons a > where > type Result a > applyCons :: a -> [NormalForm] -> Result a We can use `applyCons` to apply constructors of arbitrary arity: > instance (Generic a, ApplyCons b) => ApplyCons (a -> b) > where > type Result (a -> b) = Result b > > applyCons c (x:xs) = applyCons (c (primitive x)) xs > applyCons _ _ = error "applyCons: insufficient arguments" We need an instance of `ApplyCons` for booleans in order to define the `Generic` instance using our combinators. Instantiating `ApplyCons` is easy, however. The definitions are always the same: `Result a = a` and `applyCons = const`. > instance ApplyCons Bool > where > type Result Bool = Bool > applyCons = const Deconstructors are also defined mechanically: > dFalse, dTrue :: Decons Bool > dFalse c False = Just (c []) > dFalse _ _ = Nothing > dTrue c True = Just (c []) > dTrue _ _ = Nothing We can even define an instance of integers: > instance ApplyCons Int where type Result Int = Int; applyCons = const > instance Generic Int > where constr = foldr1 (!) . map intCons $ interleaved [0..] [-1,-2..] > > interleaved :: [a] -> [a] -> [a] > interleaved [] ys = ys > interleaved (x:xs) ys = x : interleaved ys xs > > intCons :: Int -> Int -> GenericOps Int > intCons n = cons (show n) n (\c m -> if n==m then Just (c []) else Nothing) Combinators ----------- The combinator `(!)` used to enumerate the constructors of a datatype combines records with generic operations. The integer argument is used to label the different constructors. > infixr 0 ! > (!) :: (Int -> GenericOps a) -> (Int -> GenericOps a) -> Int -> GenericOps a > (c1!c2) n = > GenericOps { > gen = \x -> maybe (gen genOps2 x) Just (gen genOps1 x) , > prim = \x -> maybe (prim genOps2 x) Just (prim genOps1 x) , > labels = labels genOps1 ++ labels genOps2 } > where genOps1 = c1 n; genOps2 = c2 (n+1) We rely on `(!)` to be right associative: if `(!)` takes the result of a different call to `(!)` as left argument then the distributed numbers won't be distinct! Finally, we define the `cons` combinator that takes constructors and corresponding destructors. > cons :: ApplyCons a => String -> a -> Decons a -> Int -> GenericOps (Result a) > cons s c d n = > GenericOps { > gen = d (Data (ConsLabel n s)), > prim = \ (Data l xs) -> > if n == index l then Just (applyCons c xs) else Nothing, > labels = [ConsLabel n s] > } In order to convert a value to the generic normal-form representation we can use the destructor function. To convert in the other direction we check whether the label of the constructor equals the label of the converter and, if it does, we use `applyCons` to apply the corresponding constructor.