Haskell Help

[scarface]

Hi people, i have some haskell problems with expressions. What i am trying to do is add two expressions together and simplify the output. I have this code


module X where

type Variable = String

data X = Const Integer
| Var Variable
| Plus X X
deriving (Eq, Show)

What i am trying to achieve is when i write for example Plus (Var "x")(Const 0) in Hugs, to get "Var x". The 0 is disregarded as it adds nothing to x (0 + x = x). If the Const is 1 again the output should be "Var x" as 1 + x = x.

Any help is appreciated

Thnx

[Twey]

What? Since when does 1 + x = x? :confused: I think the universe would explode or something if that were true. :)
-- code removed by request

[scarface]

thnx for the code i will try it later when i come back home..actually i have done a mistake..not 1+x but rather 1*x = x..i apologize for the confusion :(..

[Twey]

But you have no multiplication operator. You'd have to add one:
-- code removed by request

[scarface]

yes i was just giving example with the multiplication to make it clearer..also is there a way to add the 2 Expr together in case they are both Const? example : if we have Plus(Const 2)(Const 5) = 7. What i did was i wrote a separate function

[/CODE]add :: Expr -> Integer
add (Plus (Const x) (Const y)) = x + y[/CODE]

and it works but i was wondering if i can have this in the simplify function? It gives me an error to do with the Type. I have defined simplify to be Expr -> Expr but with the adding i want to get an integer back and thats where the error comes.

[Twey]

What we were doing before was merely normalisation; now, you're talking about evaluation. It will work something like this (rather dumb version, I'm afraid):
-- code removed by requestThe error with your original was that you were trying to return an Integer, but the function was meant to return an Expr.

[scarface]

Thanks for the code but i think i will just stick to my function. I am pretty bad at haskell and i dont completely understand the code you gave so i rather not use it (in case i get asked questions on it). I will try and do it the way i can and understand it and just keep it as simple as possible even if my program is not going to behave as it is expected.

I have another question concerning converting an expression to string. I had a look on the web and "Show" function is mentioned.I tried it with simple input but i couldnt convert it to string. Anyone could point me to something more useful?

[Twey]

You're probably confused by the on function. on is (roughly) defined thusly:
on :: (b -> b -> b) -> (a -> b)
on g f = \x y -> f x `g` f ySo,
liftConst = Const . on (fromConst . evaluate) is the same as (adding in all the points)
liftConst op a b = Const $ op (fromConst $ evaluate a) (fromConst $ evaluate b)It's just a little more elegant.

[scarface]

do u know why it doesnt let me load the data.function module?
I typed it exactly as posted and it gave me error saying i cant find the module.

[Twey]

What compiler and version are you using?

[scarface]

i am using WinHugs - haskell 98 interpreter

[Twey]

Ah, I see. GHC is the de-facto standard nowadays for real development (Yhc is used a lot for research) and it includes the Data.Function module. I guess you'll have to define it yourself:
on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
(g `on` f) x y = f x `g` f y

[scarface]

hi, its me again with a question. I have a function

multAdd :: Expr -> Integer
multAdd (Plus(Mult(Const x)(Const y))(Const z)) = (x * y) + z
which multiplies 2 integers and adds a third integer to the result.
eg multAdd (Plus(Mult(Const 2)(Const 4))(Const 5)) gives 13. What i am being asked to do is make a "better" function of type
[(Variable, Integer)]-> Expr -> Integer that does the same as my multAdd function with the only difference being i have to specify what a and b are (that comes from the [(Variable, Integer)] part) at the beginning.eg [("a", 3)("b", 4")] (Plus(Mult(Var "a")(Var "b"))(Const 1)).The part that confuses me is how can i make hugs know that Var "a" = 3 and Var "b" = 4. I guess some sort of pattern matching should be done?I am on the right track?

[Twey]

Not necessarily. I point you in the direction of the Prelude function lookup :: (Eq a) => a -> [(a, b)] -> Maybe b.

[razgriz21]

Looks like you know what your doing scarface, been reading the thread as I think your doing what I am doing lol.

[scarface]

i just cant seem to get my head round this haskell language.. i have been doing reading on internet but it is still confusing..so i am trying to get help from somewhere :)

[Twey]

I'm interested to know from whence this exercise comes. I met someone on #haskell yesterday who seemed to be doing the same exercise, but who lived on a different continent.

[razgriz21]

That might of been me, is that the haskell chat on mibbit? Im finding this really confusing scarface lol, you seem to have got the jist of it though, im still a newb lol :eek:

[Twey]

No, a Russian. The exercise was given to them by their teacher as part of a worksheet, so I'm curious as to whence it originated.

[scarface]

well this is a coursework we have been given for a functional programming module we are doing. i study in london. if some1 in russia is doing same exercise then maybe teachers have some source from where they get the coursework exercises and stuff. and i am a newbie as well when it comes to haskell razgriz21.so its not just you :)..

[Twey]

Which university is that (if you don't mind my asking)? Lamentably few have functional programming on the curriculum.

[razgriz21]

Its called City University in London, sounds like scarface might go to the same one as me lol. What was the Russian asking Twey? I find Haskell fun once I know what am I am doing, although I dont find it easy to do.

[Twey]

They had the toString part of the exercise done, but wanted help refactoring it (theirs was a huuuuge twenty-line monster, dealing with very specific cases where simpler cases and recursion could have been used instead).

It gets easier as you go. :)

[razgriz21]

Oh crap really???

To be honest I am completely stuck :confused:, I understand that I need to simplify expressions etc, just not to sure how to go about it. I have posted the question on hpaste, re-read all my lecture notes, read the course text and asked in the #haskell channel too.

I keep getting told to bog off when really all I am after is for someone to help explain what needs to be done and maybe give me an example, myself and others found that the exercise is not totally clear. I’m not into copying, I would rather learn it myself so I fully understand it.

Here is the full exercise: http://hpaste.org/12333

Any kind of help is appreciated :)

[Twey]

Well, one at a time, then:simplify :: Expr -> Expr — this one is pretty simple. There's not much in the way of cleverness you can do here: simply specify each case where a simplification is possible, and then give a catch-all case for everything else. Example:
-- code removed by request toString :: Expr -> Expr — not too tricky — half the exercise is done for you already. The only thing to watch out for is making sure that no brackets appear at the top level. To this end, we'll actually define two functions: toString, which performs the conversion of complex operations without brackets, and toString', which performs everything else.
-- code removed by request eval :: [(Variable, Integer)] — this one's a little bit trickier, since it involves looking something up as well. Luckily, there's a built-in function for this: lookup :: (Eq a) => a -> [(a, b)] -> Maybe b. There's even a built-in to handle the conversion from Maybe Integer to Integer for us: it's called fromMaybe, and it's in the package Maybe, whence we will import it (beware: imports must go at the top of the module, just underneath the module declaration). Apart from the Var case, this is all straightforward too:
-- code removed by request For extra credit, you may also want to implement a Num instance for Expr, allowing you to write 5 * 3 + 2 instead of Mult (Const 5) (Plus (Const 3) (Const 2)):
-- this code is not part of the exercise, and can therefore stay.
instance Num Expr where
(+) = Plus
(*) = Mult
(-) = Minus
negate = Mult (-1)
fromInteger = Const
-- We can't implement these two without some more operations.
abs = error "abs not defined on Exprs"
signum = error "signum not defined on Exprs"

[Trinithis]

Heh, forgot about the Num class. I'm too tired to make simplify be 'good', so I have some filler in it for the time being. Here's what I did:

-- code removed by request

[Twey]

Careful — that's evaluation you're doing in simplify (likewise in negate).

[razgriz21]

Hey Twey you have a been a big help, thanks for explaining all that to me, makes a bit more sense now.

Just wondered what this does:
simplify (Plus x (Const 0)) = simplify x works

As I have tried:
simplify (Plus (Var "A") (Const 0)) = Var "A"

The above works for me, however just wondered how yours worked and if it returns something similar to Var "A".

[Twey]

Similar, but it matches any Expr, not just a Var "A".

[razgriz21]

Ah ok, I currently have:

simplify (Plus (Var a) (Const 0)) = Var a
simplify (Plus (Var a) (Const 1)) = Var a
simplify (Plus (Const 0) (Var b)) = Var b
simplify (Plus (Const 1) (Var b)) = Var b

However, this works for just 0 and 1, but if I get 2, 5, 100 etc its useless. Is there some way of making a simplifly case that does it all for plus? (Using plus for now instead of minus and mult).

Thanks

[Twey]

What do you mean to do? x + 1 is not equal to x.

[guvdave123]

Use precedence and associativity to reduce the number of parentheses in the string produced by toString, e.g.
toString (Mult (Plus (Var "x") (Const 1)) (Var "y"))
= "(x + 1) * y"
toString (Plus (Plus (Var "x") (Const 1)) (Var "y"))
= "x + 1 + y"
toString (Plus (Var "x") (Plus (Const 1) (Var "y")))
= "x + (1 + y)"
toString (Plus (Var "x") (Mult (Const 1) (Var "y")))
= "x + 1 * y"

i am struggling with this? the code provided does not simplify all the above? please help thanks

[Trinithis]

I jazzed up my simplification code. Perhaps it's just me (as I've never done it before), but I highly suspect that there is a much better way of coding simplifications.

-- code removed by request


Examples


*Expr> let [x, y, z] = map (Var . return) "xyz"
*Expr>
*Expr> let test = toString . simplify
*Expr>
*Expr> test $ -(-x) + x + (99 + y) * x
"(2x + (x * (99 + y)))"
*Expr>
*Expr> test $ -1 - x + 22 * x * (y + y + y) * (2 * z) + 9
"(8 - x + (132 * x * y * z))"
*Expr>
*Expr> test $ x * y * 9 * x * 0 * x
"0"
*Expr>
*Expr> test $ x - x
"0"

[Twey]

Ahh, lists! I should have thought of that. :)

I'm still uncertain whether doing actual calculation is against the rules or not. I suspect it might be, but then perhaps 'evaluation' only means the variable lookup and interpretation. That does seem to be the focus of the eval function.

Note to you non-GHC folks:
import Data.Function (on)
import Data.Maybe (fromMaybe)
import Data.List (sort, partition, intercalate)should be
import Maybe (fromMaybe)
import List (sort, partition, intercalate)

(g `on` f) x y = f x `g` f y

[guvdave123]

toString :: Expr -> Expr — not too tricky — half the exercise is done for you already. The only thing to watch out for is making sure that no brackets appear at the top level. To this end, we'll actually define two functions: toString, which performs the conversion of complex operations without brackets, and toString', which performs everything else.
-- code removed by request


could you add to the above so when i put the below expressions in i get the results shown?

need to keep this simple. thanks

Use precedence and associativity to reduce the number of parentheses in the string produced by toString, e.g.

toString (Mult (Plus (Var "x") (Const 1)) (Var "y"))
= "(x + 1) * y"
toString (Plus (Plus (Var "x") (Const 1)) (Var "y"))
= "x + 1 + y"
toString (Plus (Var "x") (Plus (Const 1) (Var "y")))
= "x + (1 + y)"
toString (Plus (Var "x") (Mult (Const 1) (Var "y")))
= "x + 1 * y"

[razgriz21]

Sorry for not replying, been pretty hectic this week. Ignore my last post too, got confused on something.

Ok I think I am done for my simplify and toString operations (:confused: !!!), and I am going to leave them for the time being.

I am now working on my eval operation, however in your example Twey, what does the env do? Was slightly confused on that.


eval :: [(Variable, Integer)][/icode] — this one's a little bit trickier, since it involves looking something up as well. Luckily, there's a built-in function for this: lookup :: (Eq a) => a -> [(a, b)] -> Maybe b. There's even a built-in to handle the conversion from Maybe Integer to Integer for us: it's called fromMaybe, and it's in the package Maybe, whence we will import it (beware: imports must go at the top of the module, just underneath the module declaration). Apart from the Var case, this is all straightforward too:
-- code removed by request

Thanks m8 :cool:

[Twey]

fromMaybe :: a -> Maybe a -> a takes two parameters, a value to provide in the Nothing case and a Maybe, and returns either the value of the Just or the provided value. That is to say:
fromMaybe _ (Just x) = x
fromMaybe x Nothing = xThis is handy, because lookup :: a -> [(a, b)] -> Maybe b returns a Maybe b, with Nothing representing the case where no appropriate pair can be found; that is to say,
lookup _ [] = Nothing
lookup x ((a, b) : xs)
| x == a = Just b
| otherwise = lookup x xsSo, we pair these two up (eval env (Var x) = fromMaybe 0 (lookup x env)) and get a function that looks up the variable in the environment and, if it doesn't exist, returns 0.

[Twey]

Nicely found. Yes, I will remove the complete code (but leave the suggestions and explanations).

I wonder if you would enlighten me as to the original source of this exercise? I must say, I've amassed a fair amount of curiosity about it by now. :)

[Trinithis]

If only my school (Berkeley) taught functional programming with Haskell instead of Scheme, I would be soo happy.

As a side note, I think I have a better idea for simplification. Instead of transforming to a list, transform it to a graph, where edges represent either addition or multiplication between entities. I'm going to try it out when I have time.

[Twey]

Well, Scheme's simple syntax does make a lot of sense for a teaching language. There's much less to get in the way. Think yourself lucky you get taught functional programming at all :p It's disturbingly rare.

[razgriz21]

Just like to say thanks for all the help guys, the explanations and advice was really good and its helped me understand it more, I couldnt do some parts as they looked too much like yours, so hence I left them out as I didnt want to be accused of cheating. Thanks again :)

[Twey]

So long as you actually understand it and can write your own version, rather than just copying and pasting someone else's code, I think that you should probably still get the credit. That's the point of write-ups, no? :)

[razgriz21]

The parts I understand I have managed to code ok, its a bit long to be honest but I understand what and why Ive done it like that. The eval part I finally understood but I couldnt write up a different way of doing it so I left it out.

No point in copying yours and submitting it as its not my work and dont derserve the credit. Hopefully mine should be enough to get an ok grade in this part and Ill have to do better in the exam :rolleyes:

Its not easy but I understand it alot more now :)

[manmeet29]

Hii...i am completely new to Haskell...i tried a lot to understand the thing but failed....can anybody help me with the following problem ASAP..

I need to produce an infinite list of all of the rational numbers between zero and one. Each value should occur exactly once in the list but can be in any order.

and print the following results:

1. The list of the first 20 rational numbers in your list. These values will depend on the order you choose for the rationals.
2. The number of rational numbers the exist in the list of all rational numbers before the value 4%17

Thanks in advance
Manmeet