Search code examples
haskellexpression-trees

Expression Tree to List of String

This is my project, and the continuation of my previous question.

Haskell creating new data

This is the essential parts of my code. 

data Lukasiewicz = C | I | U
    deriving (Eq,  Show, Ord)
data LExpTree a = L a
                | V [Char]
                | N (LExpTree a)
                | Q (LExpTree a)
                | S (LExpTree a)
                | K (LExpTree a)
                | A ((LExpTree a), (LExpTree a))
                | O ((LExpTree a), (LExpTree a))
                | E ((LExpTree a), (LExpTree a))
                | M ((LExpTree a), (LExpTree a))
                deriving (Show, Eq)

type Dict = [(String, Lukasiewicz)] 

type Unary a b = a -> b
type Unary2 a = a -> a
type Binary b = b -> b -> b

fold :: LExpTree a -> Unary a b -> Unary [Char] b -> Unary2 b -> Unary2 b -> Unary2 b -> Unary2 b -> Binary b -> Binary b -> Binary b -> Binary b -> b
fold (L x) l v n q s k a o e m =  l x
fold (V x) l v n q s k a o e m =  v x
fold (N x) l v n q s k a o e m =  n (fold x l v n q s k a o e m)
fold (Q x) l v n q s k a o e m =  q (fold x l v n q s k a o e m)
fold (S x) l v n q s k a o e m =  s (fold x l v n q s k a o e m)
fold (K x) l v n q s k a o e m =  k (fold x l v n q s k a o e m)
fold (A x) l v n q s k a o e m =  a (fold (left' x) l v n q s k a o e m) (fold (right' x) l v n q s k a o e m)
fold (O x) l v n q s k a o e m =  o (fold (left' x) l v n q s k a o e m) (fold (right' x) l v n q s k a o e m)
fold (E x) l v n q s k a o e m =  e (fold (left' x) l v n q s k a o e m) (fold (right' x) l v n q s k a o e m)
fold (M x) l v n q s k a o e m =  m (fold (left' x) l v n q s k a o e m) (fold (right' x) l v n q s k a o e m)

evalT :: Dict -> LExpTree Lukasiewicz -> Lukasiewicz
evalT xs x = fold x id (lk xs) negation possible sure unknown (<&>) (<|>) (<->) (-->)

The last function evalT will take a Dict and Expression Tree and will spit out the result of that expression provided that the user will give the value for all variables for V [Char] in the expression tree in Dict list.

Now I need to create a new function which will evaluate the expression tree. This time, the input won't have Dict. So, the output is not the result but the list of all variable names.

My idea is to use the same fold function and to ignore everything except V [Char]. The rest should just call the expression tree, and should not do anything else.

But I have no idea how to start.

The signature of the function should be

varList :: LExpTree Lukasiewicz -> [String]
Solution

  • The conventional way to write varList is like this:

    varList (V x) = [x]
varList (L _) = []
varList (N e) = varList e  -- same for all unary nodes, e.g. Q, S, K, ...
varList (A a b) = varList a ++ varList b
  -- same for the other binary nodes

    So compare:

    fold (N x) l v n q s k a o e m =  n (fold x l v n q s k a o e m)
varList (N x)                  =  varList x

    Convince yourself that:

    varList blah == fold blah l v n ... e m

    With this identification,

    varList x == n (fold x l v n ... e m) == n (varList x)

    and therefore n must be id, the identity function.

    Another example... determining l:

    varList (L x) == fold (L x) l ... e m
              == l (fold x  l ... e m)
              == l (varList x)
              == []

    so l (varList x) == [] which means that l must be ...?