Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. explanation (John Moore)
2. Re: explanation (Thomas Davie)
3. Re: explanation (Mihai Maruseac)
4. Re: explanation (Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Wed, 1 Dec 2010 19:34:31 +0000
From: John Moore <[email protected]>
Subject: [Haskell-beginners] explanation
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Hi ,
Havent used haskell in a while can someone explain just whats happening
here. I know what it does, I just can't workout how it does it. Only need to
explain how the red area works and I can work out the rest myself
Regards
John
module Rollback where
data Expression = Val Double
| Add Expression Expression
| Subtract Expression Expression
| Multiply Expression Expression
| Divide Expression Expression
deriving Show
demo1 = (Add(Multiply(Divide(Subtract(Val 25)(Val 5))(Val 10))(Val 7))(Val
30))
evalStep :: Expression -> Expression
evalStep (Val x)= (Val x)
evalStep (Add x y)
= case x of
(Val a) -> case y of
(Val b) -> Val (a+b)
left -> Add x (evalStep y)
right -> Add (evalStep x)y
evalStep (Subtract x y)
= case x of
(Val a) -> case y of
(Val b) -> Val (a-b)
left -> Subtract x (evalStep y)
right -> Subtract (evalStep x)y
evalStep (Multiply x y)
= case x of
(Val a) -> case y of
(Val b) -> Val (a*b)
left -> Multiply x (evalStep y)
right -> Multiply (evalStep x)y
evalStep (Divide x y)
= case x of
(Val a) -> case y of
(Val b) -> Val (a/b)
left -> Divide x (evalStep y)
right -> Divide (evalStep x)y
type Stack = [Expression]
evaluate :: Expression -> IO ()
evaluate exp = do
stk <- evalWithStack exp [exp]
putStrLn "End of Equation"
evalWithStack :: Expression -> Stack -> IO Stack
-- Base case
evalWithStack (Val a) stk = return stk
-- Recursive case
evalWithStack e stk = do
putStrLn "Evaluating one more step"
let e' = (evalStep e)
putStrLn ("Result is "++(show e'))
putStrLn "Do another step (y/n) or rollback (r)? :"
c <- getLine
case c of
"y" -> evalWithStack e' (e':stk)
"r" -> let (a,stk') = stackBack stk in evalWithStack a stk'
"n" -> do { putStrLn ("Ok you said :" ++ show c
++ "so that's it "
++ "You went as deep as " ++ show
(getCount stk) ++" levels")
; return (e': stk)
}
stackBack :: Stack -> (Expression,Stack)
stackBack [a] = (a,[a])
stackBack (a:as) = (a,as)
stackBack [] = error "Nothing there"
getCount :: Stack -> Int
getCount stk = length stk
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20101201/d6acc8c2/attachment-0001.htm>
------------------------------
Message: 2
Date: Wed, 1 Dec 2010 20:19:29 +0000
From: Thomas Davie <[email protected]>
Subject: Re: [Haskell-beginners] explanation
To: John Moore <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On 1 Dec 2010, at 19:34, John Moore wrote:
> Hi ,
> Havent used haskell in a while can someone explain just whats happening
> here. I know what it does, I just can't workout how it does it. Only need to
> explain how the red area works and I can work out the rest myself
The red block says... in order to figure out the value of two expressions added
together, you must find out if you have values either side of the add sign...
If you do, simply add them together. If you do not, evaluate one side or the
other.
It's a bit odd to use small-step semantics here though, the code could be much
much neater if it used a denotational aproach:
eval :: Expression -> Double
eval (Val x) = x
eval (Add x y) = (eval x) + (eval y)
eval (Subtract x y) = (eval x) - (eval y)
eval (Multiply x y) = (eval x) * (eval y)
eval (Divide x y) = (eval x) / (eval y)
Bob
------------------------------
Message: 3
Date: Wed, 1 Dec 2010 22:20:36 +0200
From: Mihai Maruseac <[email protected]>
Subject: Re: [Haskell-beginners] explanation
To: John Moore <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Hi,
See inline comments
On Wed, Dec 1, 2010 at 9:34 PM, John Moore <[email protected]> wrote:
>
> <snip>
>
> data Expression = Val Double
> ?????????????? | Add Expression Expression
> ?????????????? | Subtract Expression Expression
> ?????????????? | Multiply Expression Expression
> ?????????????? | Divide Expression Expression
> ??????? deriving Show
> evalStep :: Expression ->? Expression
> evalStep (Val x)=? (Val x)
We can pattern match to a constructor. Val is a constructor for
Expression, our evalStep receives an Expression as input and produces
another one, presumably the evaluated input.
In the above case, we know that if we try to evaluate a value (that's
what Val stands for) we obtain the exact same value back.
> evalStep (Add x y)
> ? = case x of
> ????? (Val a) -> case y of
> ?????????????????? (Val b) -> Val (a+b)
> ?????????????????? left -> Add x (evalStep y)
> ????? right -> Add (evalStep x)y
> <snip>
This case is a little more complicated. We want to do a single step of
evaluation for expressions like 2+3 and 2+3+4 (expressed in our
format, they would be Add (Double 2) (Double 3) and Add (Double 2)
(Add (Double 3) (Double 4)) or Add (Add (Double 2) (Double 3)) (Double
4)). because the later case in ambiguous, we have two imbricated cases
instead of only one. Each of the cases must look to see if we can
narrow down x or y to (Val something) because this will make the
evaluation progress.
Hope it's useful,
--
MM
------------------------------
Message: 4
Date: Wed, 1 Dec 2010 21:33:42 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] explanation
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
On Wednesday 01 December 2010 20:34:31, John Moore wrote:
> Hi ,
> Havent used haskell in a while can someone explain just whats
> happening here. I know what it does, I just can't workout how it does
> it. Only need to explain how the red area works and I can work out the
> rest myself
>
> Regards
>
> John
>
>
> module Rollback where
>
>
> data Expression = Val Double
>
> | Add Expression Expression
> | Subtract Expression Expression
> | Multiply Expression Expression
> | Divide Expression Expression
>
> deriving Show
> demo1 = (Add(Multiply(Divide(Subtract(Val 25)(Val 5))(Val 10))(Val
> 7))(Val 30))
evalStep reduces the Expression one step unless it's a Val, which is
irreducible.
> evalStep :: Expression -> Expression
> evalStep (Val x)= (Val x)
Can't reduce a Val, so leave it as is.
> evalStep (Add x y)
For a non-atomic Expression (here Add), look at the first component/left
branch (an Expression is a binary tree with Vals at the leaves and
arithmetic operations at the branch nodes).
> = case x of
> (Val a) -> case y of
If the left branch is irreducible, look at the right
> (Val b) -> Val (a+b)
If that is also irreducible, add the values and return the irreducible
Expression
> left -> Add x (evalStep y)
otherwise reduce the right branch one step (recur).
> right -> Add (evalStep x)y
If the left branch is reducible, reduce it one step (recur), leaving the
right unchanged.
> evalStep (Subtract x y)
> = case x of
> (Val a) -> case y of
> (Val b) -> Val (a-b)
> left -> Subtract x (evalStep y)
> right -> Subtract (evalStep x)y
> evalStep (Multiply x y)
> = case x of
> (Val a) -> case y of
> (Val b) -> Val (a*b)
> left -> Multiply x (evalStep y)
> right -> Multiply (evalStep x)y
>
> evalStep (Divide x y)
> = case x of
> (Val a) -> case y of
> (Val b) -> Val (a/b)
> left -> Divide x (evalStep y)
> right -> Divide (evalStep x)y
> type Stack = [Expression]
> evaluate :: Expression -> IO ()
> evaluate exp = do
> stk <- evalWithStack exp [exp]
> putStrLn "End of Equation"
>
>
> evalWithStack :: Expression -> Stack -> IO Stack
> -- Base case
> evalWithStack (Val a) stk = return stk
> -- Recursive case
> evalWithStack e stk = do
> putStrLn "Evaluating one more step"
> let e' = (evalStep e)
> putStrLn ("Result is "++(show e'))
> putStrLn "Do another step (y/n) or rollback (r)? :"
> c <- getLine
> case c of
> "y" -> evalWithStack e' (e':stk)
> "r" -> let (a,stk') = stackBack stk in evalWithStack a stk'
> "n" -> do { putStrLn ("Ok you said :" ++ show c
> ++ "so that's it "
> ++ "You went as deep as " ++
> show (getCount stk) ++" levels")
> ; return (e': stk)
> }
>
> stackBack :: Stack -> (Expression,Stack)
> stackBack [a] = (a,[a])
> stackBack (a:as) = (a,as)
> stackBack [] = error "Nothing there"
>
> getCount :: Stack -> Int
> getCount stk = length stk
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 30, Issue 2
****************************************
