他人のHaskell日記 RSSフィード

Haskell初心者が、リハビリがてらに「ふつける」と「入門Haskell」片手に、試行錯誤するサイト。

2009-01-08

Programming in Haskell Exercise  Programming in Haskell Exercise - 他人のHaskell日記 を含むブックマーク

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)

TikTik2012/07/24 03:20Good to see a talnet at work. I can't match that.

威哥王威哥王2013/10/24 10:59花痴:http://花痴.happykanpo.com
花痴:http://xn--dtyr5y.happykanpo.com
威哥王:http://www.hellokanpo.com/view/weigewang.html
巨人倍増:http://www.hellokanpo.com/view/jurenbeiceng.html
三便宝:http://www.hellokanpo.com/view/satibo-capsules.html
D10 媚薬:http://www.hellokanpo.com/view/D10-meiyao.html
淫インモラル:http://www.hellokanpo.com/view/immoral.html
インモラル:http://www.hellokanpo.com/view/immoral.html
妖姫:http://www.hellokanpo.com/view/yaoji.html
RU486:http://www.hellokanpo.com/view/beijing-ru486.html
花痴:http://www.hellokanpo.com/view/huachi.html
紅蜘蛛:http://www.hellokanpo.com/view/hongzhizhu1.html



淫インモラル:http://immoral.hellokanpo.com
インモラル:http://immoral.hellokanpo.com
媚薬 淫インモラル:http://immoral.hellokanpo.com
媚薬 インモラル:http://immoral.hellokanpo.com
妖姫:http://youhi.hellokanpo.com
媚薬 妖姫:http://youhi.hellokanpo.com
淫インモラル 販売:http://immoral.hellokanpo.com
インモラル 販売:http://immoral.hellokanpo.com
妖姫 効果:http://youhi.hellokanpo.com
妖姫 販売:http://youhi.hellokanpo.com
妖姫 通販:http://youhi.hellokanpo.com


威哥王:http://www.hellokanpo.com/view/weigewang.html
巨人倍増:http://www.hellokanpo.com/view/jurenbeiceng.html
三便宝:http://www.hellokanpo.com/view/satibo-capsules.html
花痴:http://www.hellokanpo.com/view/huachi.html
RU486:http://www.hellokanpo.com/view/beijing-ru486.html
D10媚薬:http://www.hellokanpo.com/view/D10-meiyao.html
紅蜘蛛:http://www.hellokanpo.com/view/hongzhizhu1.html
五便宝:http://www.hellokanpo.com/view/wodibo-capsules.html
催情剤:http://www.hellokanpo.com/view/D10-meiyao.html
狼1号:http://www.hellokanpo.com/view/langyihao.html
三體牛鞭:http://www.hellokanpo.com/view/santiniubian.html
韓国痩身1号:http://www.hellokanpo.com/view/hanguoshou-575.html
痩身一号:http://www.hellokanpo.com/view/hanguoshou-575.html


精力剤:http://www.hellokanpo.com/JingLiJi
媚薬:http://www.hellokanpo.com/meiyao
威哥王:http://www.hellokanpo.com/view/weigewang.html
巨人倍増:http://www.hellokanpo.com/view/jurenbeiceng.html
三便宝:http://www.hellokanpo.com/view/satibo-capsules.html
D10 媚薬:http://www.hellokanpo.com/view/D10-meiyao.html
RU486:http://www.hellokanpo.com/view/beijing-ru486.html
新一粒神:http://www.hellokanpo.com/view/xinyilishen.html
三鞭粒:http://www.hellokanpo.com/view/wei.html
男宝:http://www.hellokanpo.com/view/nanbao.html
蔵秘男宝:http://www.hellokanpo.com/view/zangmi.html
蟻力神:http://www.hellokanpo.com/view/yilishen.html
三体牛鞭:http://www.hellokanpo.com/view/santiniubian.html
狼一号:http://www.hellokanpo.com/view/langyihao.html
D10:http://www.hellokanpo.com/view/D10-meiyao.html
D10催情剤:http://www.hellokanpo.com/view/D10-meiyao.html
巨根カプセル:http://www.hellokanpo.com/view/jugen.html
魔根:http://www.hellokanpo.com/view/muogen.html
福源春カプセル:http://www.hellokanpo.com/view/fuyuanchun.html
福源春:http://www.hellokanpo.com/view/fuyuanchun.html
vigrx 効果:http://www.hellokanpo.com/view/vigrx.html
ビグレックス:http://www.hellokanpo.com/view/oil.html
魔鬼天使性欲粉:http://www.hellokanpo.com/view/mogui-tianshi.html
中華牛鞭:http://www.hellokanpo.com/view/zhonghua.html
九鞭粒:http://www.hellokanpo.com/view/jiubianli.html
Wenickman:http://www.hellokanpo.com/view/VVK-Wenickman.html
男露888:http://www.hellokanpo.com/view/nanlu888.html
蔵八宝:http://www.hellokanpo.com/view/zhangbabao.html
FLY D5:http://www.hellokanpo.com/view/fly-d5.html
D5原液:http://www.hellokanpo.com/view/FLYD5yuan.html
蒼蝿水:http://www.hellokanpo.com/view/FLY-D5.html
蒼蝿粉:http://www.hellokanpo.com/view/inverma.html


絶對高潮カプセル:http://www.hellokanpo.com/view/jueduigaochao.html
絶對高潮:http://www.hellokanpo.com/view/jueduigaochao.html
法国性奴:http://www.hellokanpo.com/view/faguo.html
西班牙蒼蝿水:http://www.hellokanpo.com/view/cangyingshui1.html
性霸2000:http://www.hellokanpo.com/view/xingba2000.html
花之欲:http://www.hellokanpo.com/view/huazhiyu.html
美人豹:http://www.hellokanpo.com/view/meirenbao.html
蟻王:http://www.hellokanpo.com/view/antking.html
アリ王:http://www.hellokanpo.com/view/antking.html
媚薬蟻王:http://www.hellokanpo.com/view/antking.html
西班牙昆虫粉:http://www.hellokanpo.com/view/kunchong-fen.html
VOV催情液:http://www.hellokanpo.com/view/VOVcuiqingye.html
小情人:http://www.hellokanpo.com/view/sex-drops5.html
中絶薬:http://www.hellokanpo.com/view/beijing-ru486.html
御秀堂:http://www.hellokanpo.com/view/yuxiutang.html
韓国痩身一号:http://www.hellokanpo.com/view/hanguoshou-575.html
痩身1号:http://www.hellokanpo.com/view/hanguoshou-575.html
催情:http://www.hellokanpo.com/view/D10-meiyao.html
催情水:http://www.hellokanpo.com/view/Foot.html
催情丹:http://www.hellokanpo.com/view/cuiqingdan.html
女性催情剤:http://www.hellokanpo.com/view/d10-meiyao.html
催情粉:http://www.hellokanpo.com/view/hongzhizhu1.html
催情薬:http://www.hellokanpo.com/view/xby.html
催淫カプセル:http://www.hellokanpo.com/view/jueduigaochao.html
妻之友:http://www.hellokanpo.com/view/qizhi.html
野生虫草王:http://www.hellokanpo.com/view/yesheng.html
東方神龍生精:http://www.hellokanpo.com/view/dongfuangshenlong.html
大印象ダイエット茶:http://www.hellokanpo.com/view/dayinxiang.html
立挺90度:http://www.hellokanpo.com/view/liting90.html
VOV催情粉:http://www.hellokanpo.com/view/vovcuiqing.html
力多精:http://www.hellokanpo.com/view/lid-jing.html

イカオウ:http://www.hellokanpo.com/view/wei.html
ウェイカワ:http://www.hellokanpo.com/view/weigewang.html
ハナチ:http://www.hellokanpo.com/view/huachi.html
キョジンバイゾウ:http://www.hellokanpo.com/view/jurenbeiceng.html
三便宝カプセル:http://www.hellokanpo.com/view/satibo-capsules.html
さんべんぼう:http://www.hellokanpo.com/view/satibo-capsules.html
イーリーシン:http://www.hellokanpo.com/view/yilishen.html
しんいちつぶしん:http://www.hellokanpo.com/view/xinyilishen.html
消渇丸:http://www.hellokanpo.com/view/xiaokewan.html
五便宝カプセル:http://www.hellokanpo.com/view/wodibo-capsules.html
ベニクモ:http://www.hellokanpo.com/view/hong-zhi-zhu.html
紅蜘蛛液体:http://www.hellokanpo.com/view/hong-zhi-zhu.html
紅蜘蛛 激安:http://www.hellokanpo.com/view/hong-zhi-zhu-meiyao.html
威哥王:http://www.hellokanpo.com/view/weigewang.html
威哥王:http://www.hellokanpo.com/view/weigewang.html
威哥王:http://www.hellokanpo.com/view/weigewang.html
巨人倍増:http://www.hellokanpo.com/view/jurenbeiceng.html
巨人倍増:http://www.hellokanpo.com/view/jurenbeiceng.html
巨人倍増:http://www.hellokanpo.com/view/jurenbeiceng.html