• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

收集某种类型的构造函数的参数

haskell 来源:Daniel Satanove 6次浏览

对this后续问题,假设我有两个t1和t2的某个代数数据类型的术语,并且检查到t1和t2的构造函数是相同的。也就是说,(非正式),T1 = F(S)和t2 = G(T),我已经检查了F = G。现在,我想计算收集某种类型的构造函数的参数

map f (zip S T) 

假设S和T是名单参数。这个天真的代码会要求S中的所有东西都是单一类型的,但一般情况并非如此。

在这一点上,我只是好奇,如果有办法做到这一点。看起来像构造函数的套件将是一个更简单的解决方案。我想写一个泛型类型,但我只需要它的某种特定类型。


编辑:我对这个问题的描述不太对。我使用的类型是一样的东西

data Term v = F (Term v) (Term v) 
      | G (Term v) 
      | C 
      | Var v 

对于Term v类型的零个或多个参数(如(F x y, F z w)),我想申请到他们每个人的功能,并收集结果的列表构造函数:[f (x,z), f (y,w)],我想忽略这些变量。

我假设Term v类型是Unifiable v,它有一个方法isVar,它挑选出我的类型中的哪些项是变量。但是鉴于类型可以具有任意参数的构造函数,所以我不确定我首先可以得到什么概括性。我需要类似于那里有一个特定的Var构造函数,以及所有其他构造函数的形式为F [Term v],或者这样的,我不知道我需要保证什么约束。


编辑:更具体地说,我试图定义一个函数(在假哈斯克尔)

match :: (Variable v) => Term v -> Term v -> Maybe [(v, Term v)] 
match t1 t2 = case t1 of 
    Var v -> Just (check v t2) 
    f xs -> case t2 of 
    Var v -> Just (check t1 v) 
    g ys -> if f == g then flatten(map match (zip (xs,ys))) 
       else Nothing 

当然,你不能使用的情况下那样,这种假设每个构造(除了Var)以一个列表作为它的参数。


===========解决方案如下:

下面是通用编程的one-liner库的外观。有一些样板可以封装在某个地方,也许只有一行。

zipWithA说对match'递归调用已键入forall s. Typeable s => s -> s -> ZeroA Unifier s,其中ZeroA一定适用函子的参数。理想情况下,我们希望s等于Term,但one-liner需要一个可处理泛型类型的所有字段的函数(您可以选择一个必须适用于所有字段的约束);我们使用Typeable(通过withType)过滤出无效的情况。

main.hs

{-# LANGUAGE DeriveGeneric, TypeApplications #-} 

import Data.Typeable (Typeable) 
import Generics.OneLiner (zipWithA) 
import GHC.Generics (Generic) 

import MyLibrary -- Some setup that should probably go in a library 

-- Some arbitrary syntax 
type V = Int 
data Term = Var V | C | UnOp Term | BinOp Term Term 
    deriving (Show, Generic) 

type Unifier = [(Int, Term)] 

match :: Term -> Term -> Maybe Unifier 
match t1 t2 = unZeroA (match' t1 t2) 

-- ZeroA is a wrapper around the applicative functor Const 
match' :: Term -> Term -> ZeroA Unifier Term 
match' (Var v1) t2 = write (v1, t2) 
match' t1 (Var v2) = write (v2, t1) 
match' t1 t2 = zipWithA @Typeable f t1 t2 
    where 
    f :: Typeable s => s -> s -> ZeroA Unifier s 
    f s1 s2 = withType @Term s1 (match' s1 s2) 

main = do 
    print (match (BinOp (Var 0) (UnOp (UnOp (Var 1)))) 
       (BinOp C  (UnOp (Var 4)))) 
    -- Just [(0,C),(4,UnOp (Var 1))] 
    print (match (BinOp C C) (UnOp C)) 
    -- Nothing 

MyLibrary.hs

{-# LANGUAGE AllowAmbiguousTypes, DeriveGeneric, FlexibleInstances, GADTs, RankNTypes, ScopedTypeVariables, TypeOperators #-} 

module MyLibrary where 

import Control.Applicative (Alternative(..), Const(..)) 
import Data.Typeable (Typeable, eqT, (:~:)(..)) 

-- Add an absorbing element to any Monoid b 
newtype Zero b = Zero { unZero :: Maybe b } 

nil :: Zero b 
nil = Zero Nothing 

toZero :: b -> Zero b 
toZero b = Zero (Just b) 

instance Monoid b => Monoid (Zero b) where 
    mempty = Zero (Just mempty) 
    Zero Nothing `mappend` _   = nil 
    _   `mappend` Zero Nothing = nil 
    Zero a  `mappend` Zero b  = Zero (a `mappend` b) -- reusing the Maybe Monoid. 

-- Every monoid induces an Applicative functor via Const. 
type ZeroA b = Const (Zero b) 

unZeroA :: ZeroA b a -> Maybe b 
unZeroA = unZero . getConst 

-- A writer-like action. 
write :: b -> ZeroA [b] a 
write b = Const (toZero [b]) 

-- A monoid with an absorbing element induces an Alternative functor 
instance Monoid b => Alternative (ZeroA b) where 
    empty = Const nil 
    Const (Zero Nothing) <|> y = y 
    x <|> _ = x 

-- Typeable helper 

-- withType @t x (body x): 
-- the body may assume that the type of x is equal to t. 
-- 
-- If that is actually the case, then 
-- withType @t x (body x) = body x 
-- otherwise 
-- withType @t x (body x) = empty 
withType 
    :: forall t s f a 
    . (Typeable s, Typeable t, Alternative f) 
    => s -> ((t ~ s) => f a) -> f a 
withType _ body = case eqT :: Maybe (s :~: t) of 
    Nothing -> empty 
    Just Refl -> body 

版权声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。
喜欢 (0)