Wpisany wyrażeń parser

Question

Próbuję utworzyć parser wyrażenie wyrażeń w Haskell, który działa świetnie do tej pory, ale obecnie walczę o realizację funkcji wyższego rzędu. Mam problem gotowany w dół do prostego przykładu:

{-# 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)) 

Problem wydaje się, że nie ma sposobu, aby przekonać się, że każdy typ sprawdzania LiftRes sam jest podnoszona, bo deklaracje rekurencyjne klasy są zabronione.

Moje pytanie brzmi: jak to zrobić? Czy istnieją inne przykłady parserów wyrażeń tekstowych, z których mogłem korzystać z podpowiedzi?

EDIT: Wydaje się, że this discussion about type family constraints wydaje się być bardzo podobne. Jednak nie udało mi się sprawić, aby ich rozwiązanie działało w moim przypadku, może ktoś może pomóc w tym?

Answer 1

Najprostszym sposobem na wykonanie przykładowego przykładu jest usunięcie ograniczenia z Liftable (FunArg f) z deklaracji wystąpienia. Ale sądzę, że twój przykład jest tak skondensowany, że nie pokazuje, dlaczego tak naprawdę go potrzebujesz.

Więc następnym najlepszą rzeczą jest dodanie ograniczenie Liftable (FunArg f) nadrzędnej do klasy Fun:

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

Jeśli nie jest to możliwe (czyli jeśli nie wszystkie funkcje mają podnoszona typy argumentów), to nie można spodziewaj się napisać parseFun danego typu.

Bardziej ogólna uwaga: myślę, że to, co próbujesz tutaj zrobić, jest bardzo dziwne, a może za dużo naraz. Parsowanie z niestrukturalnych łańcuchów w typ danych bez kontekstu jest już wystarczająco trudne. Dlaczego nie zrobić tego w pierwszej kolejności i napisać osobną funkcję, która przekształca "bez typu", ale ustrukturyzowaną reprezentację twojego języka na typową.

EDIT (jako reakcja na komentarze, poprawionej): Jak wskazano w the discussion on type family constraints które również związane w swoim pytaniu, można ominąć nadklasę ograniczenie cyklu za pomocą ConstraintKinds. Oto sposób na sprawienie, aby zredukowany przykład działał. Być może to będzie skalować do pełnego rozwiązania?

{-# 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))