# [Haskell-cafe] Primitive Recursive Algebraic Types

Nicolas Frisby nicolas.frisby at gmail.com
Thu Aug 2 17:16:28 EDT 2007

```It seems you are confusing the notion of counting the number of
operators in the expression with actually evaluating the expression.
Your evalLength function does both.

It may help to consider counting the number of operators in the
expression to be the same as calculating the height of the syntax tree
representing the expression. This is why when we are counting the
operators in the expression, there is no need to distinguish Add and
Sub; they are both just operators for this analysis and their
different semantics are not yet a concern. The "countOperators"
function need not distinguish between Add and Sub since we're not yet
evaluating.

Similarly, a literal is not an operator; the integer it contains is a
value, not an operator. In this case the type Int is being used for
two different reasons; you'll need to be able recognize it when this
happens.

Here's the correct version; you were quite close! In terms of types
and recursive structure, you had it correct. By separating "counting
operators" from evaluation, I think you'll clearly see the reasons for
the definition.

countOperators :: Expr -> Int
countOperators = heightOfTree

heightOfTree (Lit n) = 0
heightOfTree (Add e1 e2) = 1 + (heightOfTree e1) + (heightOfTree e2)
heightOfTree (Sub e1 e2) = 1 + (heightOfTree e1) + (heightOfTree e2)

On 8/2/07, Alexteslin <alexteslin at yahoo.co.uk> wrote:
>
>
>
> Alexteslin wrote:
> >
> > Hi, I am doing some simple exercises about recursive algebraic types and
> > this particular exercise asks to define a function which counts the number
> > of operators in an expression.  I defined the function below, but i am not
> > sure if on the second line changing from "evalLength (Lit n) = n" to "(Lit
> > n) = 0" is the right solution.  although the function produces correct
> > result.
> >
> > data Expr = Lit Int | Add Expr Expr |
> >               Sub Expr Expr
> >               deriving (Eq, Show)
> >
> > evalLength :: Expr -> Int
> > evalLength (Lit n) = 0
> > evalLength (Add e1 e2) = 1 + (evalLength e1) + (evalLength e2)
> > evalLength (Sub e1 e2) = 1 + (evalLength e1) - (evalLength e2)
> >
> >
> > Thank you
> >
>
>
> It actually doesn't work.  Initially i tested on Add operator only.  But
> whith Sub operator it produces wrong result.
> --
> View this message in context: http://www.nabble.com/Primitive-Recursive-Algebraic-Types-tf4207521.html#a11969804
> Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
>
> _______________________________________________
> Haskell-Cafe mailing list