2009-01-08
■ Programming in Haskell Exercise 
Chapter 8
- The library files also defines a parser int::Parser Int for ann integer.Without looking at this definition,define int.Hint:an integer is eigher a minus symbol follow by a natural number or a natural number.
int::Parser int int = negativeInt +++ positiveInt negativeInt::Parser Int negativeInt = do symbol "-" n <- natural return (- natural) positiveInt::Parser Int positiveInt = natural
- Define a parser comment::Parser() for ordinary Haskell comments that begin with the symbol and extend to the end of the current line,.which is represented by the control character '\n'
comment::Parser() comment = do symbol "--" many (sat /= '\n') char '\n' return ()
- Using our second grammar for arithmetic expressions,draw the two possible parse trees for the expression 2+3+4
expr ->expr->expr ->term -> factor->nat-> 2
-> +
->expr ->term -> factor->nat-> 3
->+
->expr ->term -> factor->nat-> 4
expr ->expr->term -> factor->nat-> 2
-> +
->expr->expr ->term -> factor->nat-> 3
->+
->expr ->term -> factor->nat-> 4
- Using our third grammer for arithmetic expression,draw the parse trees for the expressions 2+3,2*3*4,and(2+3)+4
2+3
expr->term->factor->nat->2
->+
->expr->term->factor->nat->3
2*3*4
expr->term->factor->nat->2
->*
->term->factor->nat->3
->*
->term->facotr->nat->4
(2+3)+4
expr->term->factor->(
->expr->term->factor->nat->2
->+
->expr->term->factor->nat->3
->)
->+
->expr->term->facotr-nat->4
- Explain why the final simplicfication of the grammer for arithmetic expression has a dramactic effect on the efficiency of the resulting parser.Hint:bygin by condidering how an expression comprising a single number would be parsed if this step had not been made.
expr ::== term + expr | term
term ::== factor * term | factor
ではexprの|の右の項目がマッチするにはterm+exprが失敗した後に、termの文法にあっているか調べなければならない。しかし、すでに、|の左の項目であるterm+exprの文法を調べたときに既に行っていることであり無駄である。同じ事がtermにも言える。
- Extend the parer for arithmetic expression to support subtraction and division,based upon the following extension to the grammer.
expr = do t <- term do symbol "+" e <- expr return (t+e) +++ do symbol "-" e <- expr return (t-e) +++ return t term = do f <- factor do symbol "*" t <- term return (f*t) +++ do symbol "/" t <- term return (div f t) +++ return f
- Further extend the grammer and paser for arithmetic expressions to support exponentiatio,which is assumed to associate to the right and have higher piriority than multiplication and division,but lower priority than parentheses and numbers.For example,2^3*4 means (2^3)*4.Hint:the new level or priority requires a new rule in the grammer.
新しい文法
expr ::== term (+ expr|-expr|e) term ::== expo (* term|/term|e) expo ::== factor(^expo|e) factor ::==(expr)|nat nat ::==0|1|2|..
コード
expr = do t <- term do symbol "+" e <- expr return (t+e) +++ do symbol "-" e <- expr return (t-e) +++ return t term = do e <- expo do symbol "*" t <- term return (e*t) +++ do symbol "/" t <- term return (div e t) +++ return e expo = do f <- factor do symbol "^" e <- expo return (f^e) +++ return f factor = do symbol "(" e <- expr symbol ")" return e +++ natural
- Consider expressions built up from natural numbers using a subtraction operator that is assumed to associate tot the left.
- Define a natural grammer for such expressions.
expr ::== expr - natural | natural
- Translate this grammer into a parser expr::Parser Int.
expr = do e <- expr symbol "-" n <- natural return (e - n) +++ natural
- What is the problem with this parser?
exprを評価しようとすると無限ループになる。
- Show how it can be fiexd. Hint:rewrite the parser using the repetition primitive many and the library function foldl.
expr = do n <- natural ns <- many do symbol "-" natural return (n - foldl (+) 0 ns)
Chapter 9
サンプルコードが動かず。linux向けなのかな。ということで仕方無くパス。
Chapter 10
- Using recursion and the function add,define a multiplication function mult:Nat->Nat->nat for natural numbers.
mult Zero n = Zero mult (Succ m) n = add n (mult m n)
- Although not included in appedix A,the standard library defines
data Ordering = LT|EQ|GT
together with a function
compare::Ord a=>a->a->Ordering
that decides if one value in an ordered type is less than (LT)equal to(EQ),or greater than(GT) another such value.Using this function,redefine the function occurs::Int->Tree->Bool for search trees.Why is this new definition more efficient than the original version?
occurs m (Leaf n) = m == n occurs m (Node l n r) = case compare m n of EQ -> True LT -> occurs m l GT -> occurs m r
比較回数が最大で一回になるため効率的になる。
- Consider the following type of binary trees:type Tree = Leaf Int|Node Tree Tree.Let us say that such a tree is balanced if the number of leaves in the left and right subtree of every node differs by at most one,wich leaves themselves being trivially balanced.Define a function balanced::Tree->Bool that decides if at tree is balanced or not.Hint:first define a function that returns the number of leaves in a tree.
numLeaves (Leaf _) = 1 numLeaves (Node left right) =numLeaves left + numLeaves right balanced (Leaf _) = True balanced (Node left right) = (abs(numLeaves left - numLeaves right) <= 1 ) && balanced left && balanced right
- Define a function balance [Int]->Tree that converts a non-empty list of integers into a balanced tree,Hint:first define a function that splits a lsit into two halves whose length differs by a most one.
halves::[Int]->([Int],[Int]) halves xs = splitAt (div (length xs) 2) xs balance [x] = Leaf x balance xs = let (left,right) = halves xs in Node (balance left) (balance right)
- Extend tautology checker to suppoert the use of logical disjunction(V) and equivalance(<=>) in propositions.
data Prop = Const Bool |Var Char |Not Prop |And Prop Prop |Or Prop Prop |Imply Prop Prop |Equiv Prop Prop eval _ (Const b)= b eval s (Var x)=find x s eval s (Not p)= not(eval s p) eval s (And p q)= eval s p && eval s q eval s (Or p q) = eval s p || eval s q eval s (Imply p q)=eval s p <= eval s q eval s (Equiv p q)=eval s p == eval s q vars (Const _) = [] vars (Var x) = [x] vars (Not p) = vars p vars (And p q) = vars p ++ vars q vars (Or p q) = vars p ++ vars q vars (Imply p q) = vars p ++ vars q vars (Equiv p q) = vars p ++ vars q
- Using the function isTaut together with the parsing and interaction libraries from the previous two chapters,define an interactive tautology checker that allows propositions to be entereed from the keyboard in a user-friendly syntax. Hint:build a parser for propositioons by modifyin the parser for arithmetic expressions given in chapter 8.
interactionライブラリが動かないのでパス
- Extend the abstract machine to support the use of multiplication
Abstract Machineをいまいち呑み込めてないのであれだけど、
コードを見る限り、次のように変更すれば掛算に対応すると思う。
> data Expr = Val Int | Add Expr Expr | Mul Expr Expr > > type Cont = [Op] > > data Op = AEVAL Expr | MEVAL Expr | ADD Int | MUL Int > > eval :: Expr -> Cont -> Int > eval (Val n) c = exec c n > eval (Add x y) c = eval x (AEVAL y : c) > eval (Mul x y) c = eval x (MEVAL y : c) > > exec :: Cont -> Int -> Int > exec [] n = n > exec (AEVAL y : c) n = eval y (ADD n : c) > exec (MEVAL y : c) n = eval y (MUL n : c) > exec (ADD n : c) m = exec c (n+m) > exec (MUL n : c) m = exec c (n*m) > > value :: Expr -> Int > value e = eval e []
- Complete the following instnace declarations:
instance Monad Maybe where ... instance Monad [] where ...
In this contexts,[] denotes the list type [a] without its parameter.Hint:first write down the types of rreturn and >>= for each insntace.
instance Monad Maybe where return:: a -> Maybe a return a = Just a (>>=):: Maybe a->(a->Maybe b)->Maybe b f >>= g = case f of Just a -> g a Nothing -> Nothing instance Monad [] where return::a->[a] return a = [a] (>>=)::[a]->(a->[b])->[b] f >>= g = concat(map g f)
コメントを書く
