[Haskell-cafe] foild function for expressions

[Derek Elkins]

On Mon, 2007-12-03 at 19:13 -0800, Stefan O'Rear wrote:
> On Mon, Dec 03, 2007 at 09:18:18AM -0800, Carlo Vivari wrote:
> > 
> > Hi! I'm a begginer in haskell and I have a problem with an exercise, I expect
> > someone could help me:
> > 
> > In one hand I have a declaration of an algebra data, like this:
> > 
> > data AlgExp a = AlgExp
> > { litI  :: Int -> a,
> >    litB :: Bool -> a,
> >    add :: a -> a -> a,
> >    and :: a -> a -> a,
> >    ifte :: a -> a -> a -> a}
> > 
> > (being ifte an 'ifthenelse' expresion...)
> > 
> > What I want to do is to write a fold function for expressions, something
> > like this:
> > 
> > foldExp :: AlgExp a -> Exp -> a
> > foldExp alg (LitI i) = litI alg i
> > foldExp alg (LitB i) = litB alg i
> > foldExp alg (add exp1 exp2) = ¿¿¿???
> > foldExp alg (and exp1 exp2) = ¿¿¿???
> > foldExp alg (ifte exp1 exp2 exp3) = ¿¿¿???
> > 
> > ..ETC
> > 
> > 
> > the fact is that I have no idea of what to do with the other expresions
> > (add, and, and ifte)... I really don' t understand how to do this... It's
> > clear that a fold function should colapse in one valour, but how can I
> > espress it in the terms of the exercise?
> > 
> > For further information about the problem after this,  it's suposed that I
> > have to rewrite some functions for expresions but in terms of foldexp (the
> > one I should write before)
> 
> The problem is that AlgExp defines an arbitrary algebra, but in order to
> fold you need a universal algebra.  So it makes the most sense to add
> foldExp to the reccord.

This is an unusually poor post for you.  Presuming you mean "initial" or
"free" or "term" for "universal" then it does (presumably) have it with
Exp.  Assuming Exp is the expected thing (an AST) it is (combined with
the constructors) the initial algebra.  foldExp should quite definitely
be the type it is and not be part of the record and the its
implementation is so far correct (modulo syntactical errors that are
potentially indicative of a deeper confusion).