Implementazione di una lingua in Haskell: liste omogenee

Question

Sto cercando di creare un interprete per un linguaggio funzionale in haskell (sono nuovo nella lingua). Sto creando quello che probabilmente è un mix strano di minimalismo e convenienza - nessun tipo di dati astratti, ma voglio fornire la possibilità di creare liste omogenee.

Quindi le mie variabili di base sono data Datum = DatInt Int | DatDbl Double | DatBool Bool e mi sono reso conto che non sono affatto sicuro di come rappresentare elenchi omogenei. L'aggiunta di un costruttore List Datum o qualcosa dell'ordinamento renderebbe un elenco eterogeneo e fare un elenco separato per ciascun tipo, ovvero ListInt [Int] | ListDbl [Double] impedirebbe l'elenco di elenchi.

Quale sarebbe il modo migliore per rappresentare un elenco omogeneo?

Answer 1

Una nozione utile (che si tratti di tipi sexy o no) è quella di un tag di tipo. La versione non sexy è molto più facile da gestire.

data Tag = IntTag 
     | DoubleTag 
     | BoolTag 
     | ListTag Tag 
    deriving (Eq, Show) 

Ora i tuoi tipi sono rappresentati da questi vari tag. Un Int è rappresentato da IntTag. Un elenco di Int è rappresentato da ListTag IntTag.

Ora si può rappresentare tipo annotato espressioni qualcosa di simile:

data Expr = IntLit Int 
      | DoubleLit Double 
      | BoolLit Bool 
      | ListLit Tag [Expr] 

-- Check that an expression is validly annotated 
typeCheck :: Expr -> Maybe Tag 
typeCheck IntLit{} = Just IntTag 
... 
typeCheck (ListLit tag els) 
    | all good els = Just (ListTag tag) 
    | otherwise = Nothing 
    where 
    good el = case typeCheck el of 
       Nothing -> False 
       Just res = res == tag