Primitive Recursive Algebraic Types
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 -- View this message in context: http://www.nabble.com/Primitive-Recursive-Algebraic-Types-tf4207521.html#a11... Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
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#a11... Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
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@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#a11... Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (2)
-
Alexteslin -
Nicolas Frisby