foild function for expressions

[Carlo Vivari]

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)


Thank you very much!!!!

[Kalman Noel-2]

Carlo Vivari wrote:
> data AlgExp a = AlgExp
> { litI  :: Int -> a,
>    litB :: Bool -> a,
>    add :: a -> a -> a,
>    and :: a -> a -> a,
>    ifte :: a -> a -> a -> a}

You're confusing sum and product types. That is, you're using a product type,
but you probably need a sum type, like this:

    data Exp1 = LitI Int
                | LitB Bool
                | Add Exp1 Exp1
                | And Exp1 Exp1
                | IfThenElse Exp1 Exp1 Exp1

But in this case, using GADTs (beware: not Haskell 98, but a very popular
extension) makes for a more elegant solution. Note the strong types, disallowing
e. g. the addition of a number to a boolean value:

    data Exp2 a where
        LitI        :: Int  -> Exp2 Int
        LitB        :: Bool -> Exp2 Bool
        Add         :: Exp2 Int  -> Exp2 Int  -> Exp2 Int
        And         :: Exp2 Bool -> Exp2 Bool -> Exp2 Bool
        IfThenElse  :: Exp2 Bool -> Exp2 a -> Exp2 a -> Exp2 a

Kalman

----------------------------------------------------------------------
Get a free email address with REAL anti-spam protection.
http://www.bluebottle.com/tag/1

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ryan Ingram]

On 12/3/07, Kalman Noel <kalman.noel@...> wrote:

You're confusing sum and product types. That is, you're using a product type,
but you probably need a sum type, like this:

 

I'm not so sure; it looks like they already have that type (Exp) and wants to use AlgExp to hold the "folding" functions used.

 

Carlo, I think you're on the right track. Think of it this way: you have some Exps and you want to get some things of type "a" to pass to the functions in alg.  How could you get those things with what you have so far?

 

  -- ryan

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Brent Yorgey]

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) = ¿¿¿???

One comment: it looks like (add exp1 exp2), (and exp1 exp2) and so on above are not correct.  The second argument of foldExp is a value of type Exp, so you are pattern-matching on the constructors of Exp, and constructors are always uppercase.  Perhaps Exp has constructors named Add, And, and so on?  Then you would want to do something like

foldExp alg (Add exp1 exp2) = ???

and so on.  For the ??? part, you want to pull out an appropriate function from your alg record and apply it to exp1 and exp2.

-Brent

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Stefan O'Rear]

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.

Stefan


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[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).

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Stefan O'Rear]

On Mon, Dec 03, 2007 at 09:27:45PM -0600, Derek Elkins wrote:

> 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).

Oh right, I misread the foldExp sketch.  I thought he was trying to go
*from* a member of his algebra *to* Exp.  Sorry.

Stefan


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Kalman Noel-2]

Ryan Ingram wrote:
> On 12/3/07, Kalman Noel <kalman.noel@...> wrote:
> > You're confusing sum and product types.
> I'm not so sure; it looks like they already have that type (Exp) and wants
> to use AlgExp to hold the "folding" functions used.

Ah, I didn't catch that on the first read.  I suppose Carlo should then
tell us what Exp exactly looks like; and it would be nice, too, to
explain to me what the function in question is supposed to achieve then.
He doesn't seem to want to reduce the expression, after all.

Kalman

----------------------------------------------------------------------
Free pop3 email with a spam filter.
http://www.bluebottle.com/tag/5

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Carlo Vivari]

Brent Yorgey wrote:

One comment: it looks like (add exp1 exp2), (and exp1 exp2) and so on above
are not correct.  The second argument of foldExp is a value of type Exp, so
you are pattern-matching on the constructors of Exp, and constructors are
always uppercase.  Perhaps Exp has constructors named Add, And, and so on?
Then you would want to do something like

Yepp, it's my fault I wasn't too precise in my explanation.
There's a declaration of the data type EXP,  which is not difficult to gess with the things I've said:

data Exp = LitI Int
               |LitB Bool
               |Add Exp Exp
               |And Exp Exp
               |If Exp Exp Exp

I'm going to read carefully all of your answer now (thanks to all!!!), and then I'll tell you. ;)

[David Menendez-2]

On Dec 3, 2007 12:18 PM, Carlo Vivari <thrakatak@...> 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) = ¿¿¿???

You'll want something like this:

foldExp alg (Add e1 e2) = add alg (foldExp alg e1) (foldExp alg e2)
 

--
Dave Menendez <dave@...>
<http://www.eyrie.org/~zednenem/>
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Carlo Vivari]

Yes,as  I said before to other of you
the exp data type was also declared in the exercise (my fault not to say it), and look as this:

data Exp = LitI Int
               |LitB Bool
               |Add Exp Exp
               |And Exp Exp
               |If Exp Exp Exp

[Pablo Nogueira-2]

I believe the exercise is about understanding folds.

There are two references that are related to the exercise:

  A tutorial on the universality and expressiveness of fold, by Graham Hutton.
  Dealing with large bananas, by Ralf Lammel, etc.

The last paper motivates well the need to gather all the function
parameters to the fold (ie, the algebra) in a separate record
structure.

I don't think being told what to write will help you understand what
is going on, which is simpler than it seems.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe