Mapping between GADTs

I'm relatively new to Haskell, and am using it to write a compiler, using Alex and Happy. The language I'm writing it for is whitespace sensitive: blocks are delimited by indentation, and lines are continued by an increase of two indentation levels.

Although I've been down this road with Alex's monadUserState wrapper, as someone unfamiliar with monads I found this approach quite messy. As a result, I am thinking instead of breaking the lexing process into two stages, one which scans the tokens, and a second which will replace raw whitespace with indent, dedent and continuation tokens (this approach may be less performant, but I'm not very concerned with performance at this stage).

The GADT which describes both phases of lexical analysis looks like this:

{-# Language DataKinds, GADTs, KindSignatures #-}

module Tokens where

data Phase = P0 | Pn

data Token (p :: Phase) where

  -- Phase 0
  TokenTabs :: Int -> Token 'P0

  -- Phase n
  TokenIndent :: Token 'Pn
  TokenDedent :: Token 'Pn
  TokenLineCont :: Token 'Pn

  -- Common tokens
  TokenIf :: Token p
  -- ...
  -- Many other data constructors with result Token p, that can appear in either stage
  -- ...
  TokenName :: String -> Token p

The function that performs the second lexing phase looks like this:

postLex :: [Token 'P0] -> [Token 'Pn]
postLex tokens = postLex' 0 tokens where
  postLex' :: Int -> [Token 'P0] -> [Token 'Pn]
  postLex' depth [] = replicate depth TokenDedent
  postLex' depth ((TokenTabs n) : rest)
    | n == depth = postLex' depth rest
    | n == (depth + 1) = TokenIndent : postLex' n rest
    | n >= (depth + 2) = TokenLineCont : postLex' depth rest
    | n < depth = replicate (depth - n) TokenDedent ++ postLex' n rest
  postLex' depth (t:rest) = t : postLex' depth rest

The problem I'm encountering is that after matching the tabs token, all remaining tokens can exist in either stage, but I don't know any good way of converting the result of a data constructor with signature TokenX :: Token p from Token P0 to Token Pn.

Is there a good way of performing such a conversion? If not, are there any alternative approaches that preserve type safety? I'm largely interested because I imagine a similar approach would be useful when transforming between various different stages of ASTs later in this project.

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

上一篇: Android：免费裁剪图像

下一篇: GADT之间的映射