Синтаксические деревья: свободная монада + Bound.Scope

Я пытаюсь определить тип абстрактного синтаксиса, используя библиотеки ekmett bound и free. У меня есть что-то работающее, что я могу разобрать до следующего минимального примера:

{-# LANGUAGE DeriveFunctor #-}

import Bound
import Control.Monad.Free

type Id = String

data TermF f α =
    AppF α α
  | BindF Id (Scope () f α)
  deriving Functor

newtype Term' α = T {unT :: Free (TermF Term) α}
type Term = Free (TermF Term')

Последние две строчки - это не то, на что я надеялся. Они делают своего рода PITA, чтобы фактически использовать открытую рекурсию для аннотаций (или чего-то еще).

Есть ли лучший способ совместного использования этих двух библиотек и/или мне просто отказаться от попыток сделать Term бесплатной монадой?


haskell abstract-syntax-tree free-monad
person Andy Morris    schedule 12.12.2014    source источник

Ответы (1)


arrow_upward
9
arrow_downward

Сделай это проще

Вы можете упростить последние две строки до.

newtype Term α = T {unT :: Free (TermF Term) α}

Это должно помочь вам последовательно использовать T и unT везде, а не только на каждом другом уровне.

Сделайте это сложным

И Free, и TermF имеют тип (*->*)->(*->*), который является своего рода преобразователем. Вы ищете фиксированную точку композиции Free и TermF. Мы можем написать состав трансформаторов в целом.

{-# LANGUAGE PolyKinds #-}

newtype ComposeT g h f a = ComposeT { unComposeT :: g (h f) a}
    deriving Functor

Мы также можем написать неподвижную точку трансформаторов в целом.

{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE UndecidableInstances #-}

newtype FixT t a = FixT { unFixT :: t (FixT t) a }

deriving instance Functor (t (FixT t)) => Functor (FixT t)

Тогда вы могли бы написать

type Term = FixT (ComposeT Free TermF)

Затем используйте FixT . ComposeT везде, где вы бы только что использовали T и unComposeT . unFixT везде, где вы бы использовали unT.

person Cirdec    schedule 12.12.2014