键入表达式分析器

我正在尝试在Haskell中创建一个类型化的表达式解析器，它迄今为止效果很好，但我目前正在努力实现更高阶的函数。 我把问题归结为一个简单的例子：

{-# LANGUAGE TypeFamilies,GADTs,FlexibleContexts,RankNTypes #-}

-- A function has an argument type and a result type
class Fun f where
  type FunArg f
  type FunRes f

-- Expressions are either constants of function applications
data Expr a where
  Const :: a -> Expr a
  App :: Fun f => f -> FunArg f -> Expr (FunRes f)

-- A very simple function
data Plus = Plus

-- Which takes two integer expressions and returns an integer expression
instance Fun Plus where
  type FunArg Plus = (Expr Int,Expr Int)
  type FunRes Plus = Int

-- A more complicated function which lifts a function to lists (like in haskell)
data Map f r = Map f

-- For this we need the concept of lifting function arguments:
class Liftable a where
  type LiftRes a

-- A singleton argument is lifted by changing the expression type from a to [a]
instance Liftable (Expr a) where
  type LiftRes (Expr a) = Expr [a]

-- Two function arguments are lifted by lifting each argument
instance (Liftable a,Liftable b) => Liftable (a,b)  where
  type LiftRes (a,b) = (LiftRes a,LiftRes b)

-- Now we can declare a function instance for Map
instance (Fun f,Liftable (FunArg f),r ~ LiftRes (FunArg f)) => Fun (Map f r) where
  type FunArg (Map f r) = r
  type FunRes (Map f r) = [FunRes f]

-- Now a parser for functions:
parseFun :: [String] -> (forall f. Fun f => f -> a) -> a
-- The parser for the plus function is easy:
parseFun ["plus"] f = f Plus
-- But the parser for map is not possible:
parseFun ("map":sym) f 
  = parseFun sym (fun -> f (Map fun))

问题似乎是，没有办法说服类型检查器，因为递归类声明是被禁止的，因此每个LiftRes本身都是可用的。

我的问题是：我如何做这项工作？ 是否还有其他可用于提示的类型化表达式解析器的示例？

编辑：似乎这种关于类型家庭约束的讨论似乎是非常相关的。 但是，我没有对我的案例做出解决方案，也许有人可以帮助解决这个问题？

---

让您的示例工作的最简单方法是从实例声明中移除Liftable (FunArg f)约束。 但我认为你的榜样如此精炼，以至于不能说明你为什么需要它。

所以下一个最好的事情是为Fun类添加一个Liftable (FunArg f)超类约束：

class Liftable (FunArg f) => Fun f where
  ...

如果这是不可行的（即，如果不是所有的函数都有可升级的参数类型），那么你不能指望写出给定类型的parseFun 。

一个更一般的评论：我认为你在这里尝试做的事很奇怪，可能同时过多。 从非结构化字符串解析为上下文无关数据类型已经很困难了。 为什么不先做这件事，然后编写一个单独的函数来转换“无类型”，但将语言的结构化表示转换为键入的语言。

编辑 （作为对评论的反应，修改）：正如您在问题中关联的关于类型族约束的讨论中指出的那样，您可以使用ConstraintKinds绕过超类循环限制。 这是一个让你的简化例子工作的方法。 也许这将扩展到完整的解决方案？

{-# LANGUAGE RankNTypes, ScopedTypeVariables, TypeFamilies, FlexibleContexts, GADTs #-}

import Data.Constraint  -- from the constraints package
import Data.Proxy       -- from the tagged package

-- A function has an argument type and a result type
class Liftable (FunArg f) => Fun f where
  type FunArg f
  type FunRes f

-- Expr, Plus, and instance Fun Plus as before

class Liftable a where
  type LiftRes a
  get :: p a -> Dict (Liftable (LiftRes a))
    -- acquire "superclass" dictionary by calling this method and
    -- then pattern matching on the result

instance Liftable (Expr a) where
  type LiftRes (Expr a) = Expr [a]
  get _ = Dict

instance (Liftable a, Liftable b) => Liftable (a, b) where
  type LiftRes (a, b) = (LiftRes a, LiftRes b)
  get (_ :: p (a, b)) =
    case get (Proxy :: Proxy a) of -- extra code required
      Dict -> case get (Proxy :: Proxy b) of -- extra code required
        Dict -> Dict

data Map f r = Map f

instance (Fun f, Liftable r, r ~ LiftRes (FunArg f)) => Fun (Map f r) where
  type FunArg (Map f r) = r
  type FunRes (Map f r) = [FunRes f]

parseFun :: forall a. [String] -> (forall f. Fun f => f -> a) -> a
parseFun ["plus"]      f = f Plus
parseFun ("map" : sym) f = parseFun sym
  ( (fun :: g) -> case get (Proxy :: Proxy (FunArg g)) of -- extra code required
                     Dict -> f (Map fun))

链接地址: http://www.djcxy.com/p/69623.html

上一篇: Typed expression parser

下一篇: put background image in center and repeat last pixel to left and right