Using Uniplate in two-level tree type

Question

I'm in the beginning stages of writing a parser for a C-like language in Haskell. I've got the AST data type down, and I'm playing around with it by writing some simple queries on the AST itself before I delve into the parser side of things.

My AST revolves around two types: statements (have no value, like an if/else) and expressions (have a value, like a literal or binary operation). So it looks something like this (vastly simplified, of course):

data Statement
    = Return Expession
    | If Expression Expression

data Expression
    = Literal Int
    | Variable String
    | Binary Expression Op Expression

Say I want to get the names of all variables used in an expression. With uniplate, it's easy:

varsInExpression exp = concat [s | Variable s <- universe exp]

But what if I want to find a list of variables in a statement? In each constructor of Statement, there is a nested Expression that I should apply varsInExpression to. So at the moment, it looks like I'd have to pattern-match against every Statement constructor, which is what uniplate's out to avoid. Am I just not grokking the documentation well enough, or is this a limitation of uniplate (or am I doing it wrong?)?

Answer 1

This seems like a good use-case for biplates. I'm relying on the slower Data.Data method, but it makes this code pretty trivial.

{-# LANGUAGE DeriveDataTypeable #-}
import Data.Data
import Data.Typeable
import Data.Generics.Uniplate.Data
data Statement
    = Return Expression
    | If Expression Expression
    deriving(Data, Typeable)

data Expression
    = Literal Int
    | Variable String
    | Binary Expression Int Expression
    deriving(Data, Typeable)

vars :: Statement -> [String]
vars stmt = [ s | Variable s <- universeBi stmt]

Basically biplates are a generalized notion of uniplates where the target type isn't necessarily the same as the source, eg

biplate :: from -> (Str to, Str to -> from)