型付き式パーサー

Question

私は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自体が昇降可能である型チェッカーを説得する方法がないということのようです。

私の質問は次のとおりです。この作業を行うにはどうすればよいですか？私はヒントを取ることができる型付き式パーサの他の例がありますか？

編集：this discussion about type family constraintsは非常に関連しているようです。しかし、私のソリューションは、私の場合にはうまくいかず、誰かがそれを手伝ってくれるかもしれません。

Answer 1

インスタンスの宣言からLiftable (FunArg f)という制約を削除するのが最も簡単な例です。しかし、私はあなたの例がちょうど凝縮されているので、実際にそれが必要な理由を示していないと思います。

だから次善の策はFunクラスにLiftable (FunArg f)スーパー制約を追加することです：これが不可能な場合

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

を（すべてではない、あなたの関数が昇降引数の型を持っている場合）、あなたがすることはできません指定されたタイプのparseFunを書き込むことを期待してください。

もっと一般的な発言：あなたがここでやろうとしていることは、非常に奇妙で、おそらくあまりにも多すぎると思います。構造化されていない文字列から文脈自由なデータ型への解析は、すでに難しいです。最初にそれをしないで、あなたの言語の「型指定されていない」構造化された表現をタイプされた表現に変換する別の関数を書いてみてください。

EDIT（コメントへの反応として、改訂）：あなたはまた、あなたの質問にリンクされているthe discussion on type family constraintsで指摘したように、あなたが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))