他人のHaskell日記 RSSフィード

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

2009-10-05

Dragging problem  Dragging problem  - 他人のHaskell日記 を含むブックマーク

Haskell:The Craft of Functinal Programming(P 424)より

exam3 = [1..n] ++ [last [1..n]]

exam4 = list ++ [last list]
        where
        list=[1..n]

前者だと空間計算量がO(1)だけど後者だと空間計算量がO(n)になる。

このように巨大な構造の一部が必要なときに、その全体まで保持されてしまう特徴をDragging Problemと言う

ZiarreZiarre2012/01/08 12:12That's 2 clveer by half and 2x2 clever 4 me. Thanks!

upbjatcnwhzupbjatcnwhz2012/01/10 21:198vnKvt <a href="http://eohmielyepxv.com/">eohmielyepxv</a>

zmxjgarizmxjgari2012/01/14 03:49cJARhn , [url=http://bizvszwzmrku.com/]bizvszwzmrku[/url], [link=http://pwjkxaittkqm.com/]pwjkxaittkqm[/link], http://padxxqgiwnuk.com/

gqhbchxocbgqhbchxocb2013/08/02 21:51bqvboibtlfmm, <a href="http://www.lgingxkjph.com/">kaijezxdhr</a> , [url=http://www.rjzryejoxx.com/]gxyoiiclcb[/url], http://www.klvsvmveji.com/ kaijezxdhr

2009-01-09

Haskellで自分の足を撃つ方法(抜粋/意訳) Haskellで自分の足を撃つ方法(抜粋/意訳) - 他人のHaskell日記 を含むブックマーク

(http://www.haskell.org/haskellwiki/Shooting_your_self_in_the_foot)

  • あなたは銃を発射した。しかし銃弾はIOモナドにからめとられた。
  • プログラムをコンパイルしようとしたら、コンパイラが型エラーを発生させ、それはカーネルバッファをオーバーフローするほど長かったために、トリガーコントロールレジスタを上書きし、足を撃つことになった。
  • 型エラーという暗号を解読しようとして、あなたの頭は爆発した。
  • 足を撃ったが、何も起きなかった。Haskellの世界では副作用は起きないのだ。
  • 足を撃とうとしたが、Gunというdatatypeが無かったため、変わりにArrowを使った。
  • 足を撃ったが完全に元気だ。足を評価するまでは。
  • 足を撃った。しかしSTM(Software Transactional Memory)モナドのなかにいるので、やりたいことがみつかるまでいつだってやりなおせる。

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

Chapter 11

  • Redefine the combination function choices using a list comprehension rather than the library functions concat and map.
choices' xs                   =  [perms x|x <- subs xs]
  • Define a recursive function isChoice::Eq a=>[a]->[a]->Bool that decides if one list is chosen from another,without using the combinatorial functions perms and subs,Hint:start by defining a function that removes the first occurrence of a value from a list.
isChoice []     ys = True
isChoice (x:xs) ys = elem x ys && isChoice xs (deleteFirst x ys)

deleteFirst x []     = error $ (show x)++" does not exsist."
deleteFirst x (y:ys) 
  |x == y            = ys
  |otherwise         = y:deleteFirst x ys 
  • What effect would generalizing the function split to also return pairs containing the empty list have on the behavior of solutions?

意味がわからず。solutions以前にexprsの評価において、要素を減らさずに再帰するので、無限ループになると思われる。

  • Using choices,exprs,and eval,verify that there are 33,665,406 possible expressions over the numbers 1,3,7,10,25,50,and that only 4,672,540 of these expressions evaluate successfully.
*Main> length $ [y|xs<-choices [1,3,7,10,25,50],y<-exprs xs]
33665406
*Main> length $ [z|xs<-choices [1,3,7,10,25,50],y<-exprs xs,z<-eval y]
4672540
  • Similarly,verify that the number of expressions that evaluate successfully increases to 10,839,369 if the numeric domain is generalised to arbitrary integers.Hint:modify the definition of valid.
Main> length $ [z|xs<-choices [1,3,7,10,25,50],y<-exprs xs,z<-eval y]
10839369
  • Modify the final program to:
    • allow the use of exponentiation in expressions:
    • produced the nearest solutions if no exact solution is possible
    • order the solutions using a suitable measure of simplicity

import Data.List
import Data.Ord

data Op                       =  Add | Sub | Mul | Div | Exp deriving Enum

apply                         :: Op -> Int -> Int -> Int
apply Add x y                 =  x + y
apply Sub x y                 =  x - y
apply Mul x y                 =  x * y
apply Div x y                 =  x `div` y
apply Exp x y                 =  x ^ y

data Expr                     =  Val Int | App Op Expr Expr

values                        :: Expr -> [Int]
values (Val n)                =  [n]
values (App _ l r)            =  values l ++ values r
 
subs                          :: [a] -> [[a]]
subs []                       =  [[]]
subs (x:xs)                   =  yss ++ map (x:) yss
                                 where yss = subs xs

interleave                    :: a -> [a] -> [[a]]
interleave x []               =  [[x]]
interleave x (y:ys)           =  (x:y:ys) : map (y:) (interleave x ys)
 
perms                         :: [a] -> [[a]]
perms []                      =  [[]]
perms (x:xs)                  =  concat (map (interleave x) (perms xs))

choices                       :: [a] -> [[a]]
choices xs                    =  concat (map perms (subs xs))

split                         :: [a] -> [([a],[a])]
split []                      =  []
split [_]                     =  []
split (x:xs)                  =  ([x],xs) : [(x:ls,rs) | (ls,rs) <- split xs]

valid                        :: Op -> Int -> Int -> Bool
valid Add x y                =  x <= y
valid Sub x y                =  x > y
valid Mul x y                =  x /= 1 && y /= 1 && x <= y
valid Div x y                =  y /= 1 && x `mod` y == 0
valid Exp x y                =  x /= 1 && y /= 1 

type Result                   =  (Expr,Int)
results                      :: [Int] -> [Result]
results []                   =  []
results [n]                  =  [(Val n,n) | n > 0]
results ns                   =  [res | (ls,rs)  <- split ns
                                      , lx      <- results ls
                                      , ry      <- results rs
                                      , res     <- combine lx ry]
 
combine                     :: Result -> Result -> [Result]
combine (l,x) (r,y)         =  [(App o l r, apply o x y) | o <- [(Add)..(Exp)]
                                                         , valid o x y]

solutions                   :: [Int] -> Int -> [Expr]
solutions ns n              =  let evals = evaluations ns n 
                                   correct =  sortBy (comparing values) $ map fst $ filter (\x->snd x==0) evals
                                   nearest = fst $ minimumBy (comparing snd) evals
                               in if null correct then [nearest] else correct
 
evaluations                   :: [Int] -> Int -> [Result]
evaluations ns n              =  [(e,abs(m-n))| ns'   <- choices ns
                                               ,(e,m) <- results ns']
                                      

Chapter 12

=Identify the redexes inthe following expressions,and determine whether each redex is inner most,outer most,neigher,or both.

    • 1+(2*3)
1+(2*3):outermost
(2*3):innermost
    • (1+2)*(2+3)
(1+2)*(2+3):outermost
(1+2):innermost
(2+3):innermost
    • fst (1+2,2+3)
fst (1+2,2+3):outermost
(1+2):innermost
(2+3):innermost
    • (\x->1+x)(2*3)
(\x->1+x)(2*3):outermost
(2*3):innermost
  • Show why outermost evaluation is preferable to innermost for thepurposes of evaluating the expression fst (1+2,2+3).
innermost evaluationの場合

fst(1+2,2+3)
->fst(3,2+3)
->fst(3,5)
->3

outermost evaluationの場合
fst(1+2,2+3)
->1+2
->3

となり簡約のステップが減る。
  • Given the definiton mult = \x->(\y-> x* y),show how the evaluation of mult 3 4 can be broken dwon into four separate steps
mult 3 4
->(\x->(\y-> x* y)) 3 4
->(\y-> 3 * y) 4
->3 * 4
->12
  • Using a list comprehension,define an expression fibs::[Integer] that generates the infinite sequences of Fibonacchi numbers 0,1,1,2,3,5,8,13,21,34... using the following simple procedure:(Hint:make use of library functions zip and tail.Note that numbers in the Fibonacci sequence quickly large,hence the use of the type Integer of arbitrary-precision integers above.
    • the first two numbers are 0 and 1
    • the next is the sum of the previous two;
    • return to the second step.

よくわからず。

題意を満たしてないがとりあえず。

fibs  = 0:1:zipWith(+)fibs (tail fibs)

もしかして

fibs  = 0:1:[f+s|(f,s)<-zip fibs (tail fibs)]

これでいいんだろうか。

  • Using fibs,defina a function fib::Int->Integer that returns the nth Fibonacchi number(counting from zero),and an expression that calculates the first Fibonacchi number greater than one thousand.
fib n = fibs !! n

head $ dropWhile (<=1000) fibs
  • Define appropriate version of the library functions
repeat::a -> [a]
repeat x = xs where xs = x :xs

take::Int->[a]->[a]
take 0     _ = []
take (n+1) [] = []
take (n+1) (x:xs) = x : take n xs

replicate::Int->a->[a]
replicate n = take n . repeat

for the following type of binary trees

data Tree a = Leaf|Node (Tree a) a (Tree a)
repeatTree x = Node (repeatTree x) x (repeatTree x)

takeTree 0  _                 = Leaf
takeTree _  []                = Leaf
takeTree n (Node left x right)= Node (takeTree (n-1) left) x (takeTree (n-1) right)

replicateTree n = takeTree n.repeatTree

Chapter 13

  • Give an example of a function from the standard library in appendix A that is defined using overlapping patterns.
last [x] = x
last (_:xs) = last xs

前者の定義がなければ、シングルトンリストは後者にもマッチしうる。

  • Show that add n (Succ m) = Succ (add n m) by induction on n.
add Zero m     = m
add (Succ n) m = Succ(add n m)
n = Zeroのとき

左辺=add Zero (Succ m)={applying add} Succ m
右辺=Succ(add Zero m) ={applying add} Succ m
よって成り立つ

n = kのとき、つまり
add k (Succ m) = Succ (add k m)が成りたつとすると、
add (Succ k) (Succ m) = Succ (add (Succ k) m)が成りたつことを証明する。

左辺=add (Succ k) (Succ m)={applying add}Succ (add k (Succ m)
右辺=Succ (add (Succ k) m)={applying add}Succ (Succ (add k m)
ここで、add k (Succ m) = Succ (add k m)なので成りたつ。 q.e.d
  • Using this property,together with add n Zero = n,show the addition is communtative,add n m = add m n,by induction on n
仮定:
add Zero m     = m                 -- (1)
add (Succ n) m = Succ(add n m)     -- (2)
add n (Succ m)= Succ(add n m)      -- (3)
add n Zero = n                     -- (4)
結論:
add n m = add m n
証明:
*base case
add Zero m = add m Zeroを証明する。

左辺=add Zero m ={using 1} m
右辺=add m Zero ={using 4} m

*inductive case
add k m = add m k                 -- (ih) Induction Hypothesis
を使って
add (Succ k) m =  add m (Succ k)を証明する.

左辺=add (Succ k) m ={using 2} Succ (add k m) = {using ih} Succ (add m k)
右辺=add m (Succ k) ={using 3} Succ (add m k)

q.e.d.
  • Using the following definition for the library function that decides if all elements of a list satisfy a predicate,complete the proof of the correctness of replicate by showing that it produces a list with identical elements,all(==x)(replicate n x),by induction on n >= .Hint:show that the property is always True.
 all p []     = True
 all p (x:xs) = p x && all p xs
仮定:
 replicate 0      _  = []               -- (1)
 replicate (n+1)  x  = x:replicate n x  -- (2)
 all p []     = True                    -- (3)
 all p (x:xs) = p x && all p xs         -- (4)
結論:
all(==x) (replicate n x) は常にTrue
証明:
*base case
all(==x) (replicate 0 x) ={using 1} all (==x) [] ={using 3} True

*inductive case
「all(==x) (replicate k x) は常にTrue」-- (ih)
を使ってall(==x) (replicate (k+1) x)は常にTrueを証明する。
 
                    all (==x) (replicate (k+1) x)
={using 2}          all (==x) (x:replicate k x) 
={using 4}          (==x) x && all (==x) replicate k x 
=(applying (==x)}   True && all (==x) replicate k x
={appying &&}       all (==x)replicate k x
={using ih}         True

q.e.d

  • Using the definition
[] ++ ys  = ys                                   -- (1)
(x:xs) ++ ys = x :(xs++ys)                       -- (2)

verify the following two properties,by induction on xs:

xs ++ [] = xs
xs ++ (ys ++ zs) = (xs ++ ys) ++ zs
xs ++ [] = xsを証明する
*base case
[] ++ []  = []
*inductive case
(x:xs)++ [] ={using 1} x:(xs++[])={using ih} x:xs
q.e.d.

xs ++ (ys ++ zs) = (xs++ ys) ++ zsを証明する。
*base case
[] ++ (ys ++ zs) ={using 1} ys ++ zs
([]++ ys )++ zs  ={using 1} ys ++ zs
*inductive case
(x:xs)++(ys++zs)    ={using 2} x:(xs++(ys++zs))    = {using ih} x:((xs++ys)++zs)
((x:xs)++ ys) ++ zs ={using 2} (x:(xs++ys)) ++ zs  = {using 2}  x:((xs++ys)++zs)
q.e.d.
  • The equation reverse(reverse xs) = xs can also be probed using a single auxiliary result,result reverse (xs ++[x])=x:reverse xs,which can itself be verified by induction on xs.Why might the proof using three auxiliary results as in this chapter be viewed as preferable?

よくわからないので、とりあえず証明してみる。

仮定
reverse []              = []                --(1)
reverse (x:xs)          = reverse xs++[x]   --(2)
reverse (xs ++[x])      = x:reverse xs      --(3)

証明
*base caseは省略
*inductive case
               reverse (reverse (x:xs))
={using 2}     reverse (reverse xs ++ [x])
={using 3}     x:reverse(reverse (xs))
={using ih}    x:xs

次にreverse (xs ++[x])      = x:reverse xs  を証明する。

仮定
reverse []              = []                --(1)
reverse (x:xs)          = reverse xs++[x]   --(2)
[]     ++ ys            = ys                --(4)
(x:xs) ++ ys            = x:(xs++ys)        --(5)

*base case

reverse ([] ++ [x]) 
={using 4} reverse [x] 
={using 2} reverse [] ++ [x] 
={using 1} [] ++ [x] 
={using 4} [x]

x:reverse [] 
={using 1}      x:[] 
={syntax sugar} [x]

*inductive case
            reverse ((x:xs)++[y])
={using 5}  reverse(x:(xs++[y])
={using 2}  reverse (xs++[y]) ++ [x] 
={using ih} y:reverse xs ++ [x]

                y:reverse(x:xs) 
={using 2}      y:(reverse xs++[x])
={unapplying 5} y:(reverse xs) ++[x]

証明はできた。結局理由はわからない。

  • Using the definitoons
map f []     = []                    -- (1)
map f (x:xs) = f x:map f xs          -- (2)
(f.g) x = f (g x)                    -- (3)

show that map f (map g xs) = map (f.g) xs by induction on xs.

*base case 
           map f (map g []) 
={using 1} map f [] 
={using 1} []

          map (f.g) []                
={using 1 []

*inductive case
             map f(map g (x:xs)) 
={using 2}   map f (g x:map g xs)
={using 2}   f (g x):map f (map g xs) 

             map (f.g) (x:xs) 
={using 2}   (f.g) x:map (f.g) xs 
={using 3}   f (g x):map (f.g) xs 
={using ih}  f (g x):map f (map g xs)
  • Using the definition for ++ given above,together with
take 0      _    =[]
take (n+1) []    =[]
take (n+1) (x:xs)=x:take n xs

drop 0 xs        =xs
drop (n+1) []    =[]
drop (n+1) (_:xs)=drop n xs


show that take n xs ++ drop n xs == xs,by simultaneous induction on the integeer n>= 0 and the list xs. Hint:there are three cases,one for each pattern of arguments in the definition of take and drop

仮定
take 0      _    =[]                  --(1)
take (n+1) []    =[]                  --(2)
take (n+1) (x:xs)=x:take n xs         --(3)
drop 0 xs        =xs                  --(4)
drop (n+1) []    =[]                  --(5)
drop (n+1) (_:xs)=drop n xs           --(6)
[]     ++ ys     = ys                 --(7)
(x:xs) ++ ys     = x:(xs++ys)         --(8)

*base case
n = 0のとき
take 0 xs ++ drop 0 xs ={using 1}[] ++ drop 0 xs={using 4} [] ++ xs ={using 7}xs
xs = []のとき
take n [] ++ drop n [] ={using 2} [] ++drop n []={using 5} [] ++ [] ={using 7} []
*inductive case
take k xs ++ drop k xs == xsのとき      --(ih)
take (k+1) (x:xs)++drop (k+1) (x:xs) 
={using 3} (x:take k xs)++drop (k+1) (x:xs) 
={using 6} (x:take k xs)++drop k xs
={using 8} x:(take k xs ++ drop k xs)
={using ih} x:xs

自然数nと要素数m個のリストについて、
n>mならば (n-m,m-m)=(n-m,0)がbase caseとなり
n<=mならば(n-n,m-n)=(0,m-n)がbase caseとなるので、常に成立する。
  • Given the type declaration "data Tree = Leaf Int|Node Tree Tree" show that the number of leaves in such a tree is always one greater than the numbe rof nodes,by induction on trees.Hint:start by defining functions that count the number of leaves and nodes in a tree.
data Tree = Leaf Int|Node Tree Tree deriving Show

t1 =  Node (Leaf 3) (Node (Leaf 5) (Leaf 6))
t2 =  Leaf 3
t3 = Node (Node (Node (Leaf 4) (Leaf 8)) (Leaf 3)) (Node (Leaf 4) (Leaf 2))

countLeaves::Tree->Int
countLeaves (Leaf _)         = 1
countLeaves (Node left right)= countLeaves left + countLeaves right

countNodes::Tree->Int
countNodes (Leaf _)          = 0
countNodes (Node left right) = 1 + countNodes left + countNodes right

実行結果

*Main> countLeaves t1
3
*Main> countLeaves t2
1
*Main> countLeaves t3
5
*Main> countNodes t1
2
*Main> countNodes t2
0
*Main> countNodes t3
4

証明する

仮定:
countLeaves (Leaf _)         = 1                                        --(1)
countLeaves (Node left right)= countLeaves left + countLeaves right     --(2)
countNodes (Leaf _)          = 0                                        --(3)
countNodes (Node left right) = 1 + countNodes left + countNodes right   --(4)
結論:
countLeaves tree = countNodes tree + 1
証明:
*base case
countLeaves (Leaf leaf) = 1 
countNodes  (Leaf leaf) = 0 
*inductive case
countLeaves left = countNodes left + 1                                   --(ih-1)
countLeaves right= countNodes right+ 1                                   --(ih-1)
を仮定する。

countLeaves (Node left right)
={using 2)countLeaves left + countLeaves right
={using ih-1,ih-2}countNodes left + 1 + countNodes right + 1

countNodes (Node left right)
={using 4}1 + countNodes left + countNodes right                                


  • Given the equation comp' e c = comp e ++ c,show how to construct the recursive definition for comp',by induction on e.
comp (Val n) = [PUSH n]
comp (Add x y) = comp x ++ comp y ++ [ADD]

comp' (Val n) c
=comp (Val n) ++ c
=[PUSH n]++c
=PUSH n:c

comp' (Add x y) c 
=comp (Add x y) ++ c
=comp x ++ comp y ++ [ADD] ++ c
=comp x ++ (comp y ++ ([ADD] ++ c))
=comp' x (comp y ++ ([ADD] ++ c))
=comp' x (comp' y ([ADD] ++ c))
=comp' x (comp' y (ADD:c))

comp' (Val n) c   = PUSH n:c
comp' (Add x y) c = comp' x (comp' y (ADD:c))

PatiencePatience2012/01/08 13:13This is the perfcet way to break down this information.

hyetlrtkhyetlrtk2012/01/09 03:03T76K7x <a href="http://gndgrqeiuiyj.com/">gndgrqeiuiyj</a>

hhpdahdhhpdahd2012/01/09 20:46UlfWue , [url=http://vyqauabetkei.com/]vyqauabetkei[/url], [link=http://irtuwgunyrnf.com/]irtuwgunyrnf[/link], http://fuejlwudquxd.com/

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

2009-01-04

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

Chapter 1

  • Give another possible calculation for the result of double(double 2)
double(double 2)
=double(2+2)
=(2+2)+(2+2)
=(2+2)+4
=4+4
=8
sum[x]=sum(x:[])=x+sum[]=x+0=x
  • Define a function product that produces the product of a list of numbers,and show using your definition that product[2,3,4]
product [] = 1
product (x:xs) = x * product xs
product[2,3,4]=product(2:[3,4])=2*product[3,4]=2*product(3:[4])=2*3*product[4]=2*3*prodocut(4:[])
=2*3*4*product[]=2*3*4*1=24
  • How should the definition f the function qsort be modified so that it produces a reverse sorted version of a list?
qsort[]=[]
qsort(x:xs)=qsort larger ++ [x]++ qsort smaller
            where
             smaller = [a|a<-xs,a <=x]
             larger  = [b|b<-xs,b>x]
  • What would be the effect of replacing <= by < in the definiton of qsort? Hint:consider the example qsort[2,2,3,1]

改変されたqsortをqsort'だと仮定する

qsort[2,2,3,1]=qsort [2,1] ++[2]++qsort [3]=(qsort[1]++[2]++qsort[])++[2]++(qsort[]++[3]++qsort[])
=((qsort[]++[1]++qsort[])++[2]++[])++[2]++([]++[3]++[])
=[]+[1]+[]+[2]+[]+[]+[2]+[]+[3]+[]=[1,2,2,3]
qsort'[2,2,3,1]=qsort [1] ++ [2] ++ qsort[3]=qsort[]++[1]++qsort[]++[2]++qsort[]++[3]++qsort[]
=[]++[1]++[]++[2]++[]++[3]++[]

つまり、同じ値が複数あるときは、ひとつを残して消えてしまう。


Chapter 2  Chapter 2  - 他人のHaskell日記 を含むブックマーク

  • Parentheses the following arithmetic expressions
2^3*4->(2^3)*4
2*3+4*5->(2*3)+(4*5)
2+3*4^5->2+(3*(4^5))
  • Work through the examples from this chapter using Hugs.

pass.

  • The script below contains three syntactic errors.Correct these errors and then check that your script works properly using Hugs.
N = a 'div' length xs
    where 
       a = 10
      xs = [1,2,3,4,5]

answer:

n = a `div` length xs
    where 
      a = 10
      xs = [1,2,3,4,5]
  • Show how the library function last that selects the last element of a non empty list could be defined in terms of the library functions introduced in this chapter.Can you think of another possible definition?
last1 = head.reverse
last2 xs = xs !! length xs -1
  • Show how the library function init that removes the last element from a non-empty list could similarly be defined in two different ways.
init1 = reverse.tail.reverse
init2 xs = take (length xs - 1) xs

Chapter 3

  • What are the types of the following values?
['a','b','c'] => String
('a','b','c') => (Char,Char,Char)
[(False,'0'),(True,'1')] =>[(Bool,Char)]
([False,True],['0','1']) => ([Bool],String)
[tail,init,reverse] =>[[a]->[a]]
  • What are the types of the following functions?(Hint:take care to include the necessary class constraints if the functions are defined using overloaded operators)
second :: [a]->a
second xs = head (tail xs)

swap:: (a,b)->(b,a)
swap(x,y)=(y,x)

pair ::a->b->(a,b)
pair x y = (x,y)

double :: Num a => a -> a
double x = x * 2

palindrome :: Eq a => [a]->Bool
palindrome xs = reverse xs == xs

twice:: (a->a)->a->a
twice f x = f (f x)
  • Check your answers to the preceding two questions using Hugs.

pass.

  • Why is it not feasible in general for function types to be instances of the Eq class?When is it feasible?(Hint:two functions of the same type are equal if they always return equal results for equal arguments.)

うーん……

入力値が有限(例えば列挙型)ならば、二つの関数に、すべての場合について入力値を放りこんで値を比較することで関数の等価性を証明できるが、一般にはそうではないから?

chapter 4

  • Using library functions,define a function halve::[a]->([a],[a]) that splits an even-lengthed list into two halves.For example.
halve xs = splitAt (div (length xs) 2) xs
  • Consider a function safetail::[a]->[a] that behaves the library function tail,except that safetail maps the empty list to itself,whereas tail produces an error in this case.Define safetail using(a)a conditional expression,(b)guarded equations,(c)pattern matching.
(a)
safetail xs = if null xs then [] else drop 1 xs
(b)
safetail xs
  |null xs   = []
  |otherwise = drop 1 xs
(c)
safetail []     = []
safetail (x:xs) = xs
  • In a similar way to (&&),show how the logical disjunction operator (||) can be defined in four different ways using pattern matching,
1)
True || True  = True
True || False = True
False|| True  = True
False|| False = False
2)
False || False = False
_     || _     = True
3)
False  || b     = b
True   || _     = True
(4)
b|| c |b == c    =  b
      |otherwise = True
  • Redefine the following version of conjunction operator using conditional expressions rather than pattern matching
True && True = True
_    && _    = False
a && b = if a == True 
           then if b == True 
                   then True
                   else False
           else false  
  • Do the same for the following version and note the differentce in the number of conditional expressions required.
True  && b = b
False && _ = False
a && b = if a == True then b else False

必要な条件式が一つ減っている。

  • Show how the curried function definition mult x y z = x * y * z can be understood in terms of lambda expressions.
mult =(\x->(\y->(\z-> x*y*z)))

Chapter 5

  • Using a list comprehension,give an expression that calculate the sum 1^2+2^2+..+100^2 of the first one hundred integer squares;.
sum [x^2|x<-[1..100]]
  • In a similar way to the function length,show how the library function replicate::Int->a->[a] that produces a list of identical elements can be defind using a list comprehension.For example:
>replicate 3 True
[True,True,True]
replicate n a = [a|_<-[1..n]]
  • A triple(x,y,z) of positive integers is Pythagorean if x^2+y^2=z^2.Using a list comprehension,define a function pyths::Int->[(Int,Int,Int)] that returns the list of all Pythagorean triples whose components are at most a given limit.For example:
>pyths 10
[(3,4,5),(4,3,5),(6,8,10),(8,6,10)]
pyths limit = [(x,y,z)|x<-[1..limit],y<-[1..limit],z<-[1..limit],x^2+y^2==z^2]
  • A positive integer is perfect if it equals the sum of its factors,excluding the number itself.Using a list comprehension andn the function factors,define a function perfects::Int->[Int] that returns the list of all perfect numbers up to a given limit.For example:
> perfects 500
[6,8,496]
perfects limit = [x|x <-[1..limit],(sum.factors) x == 2* x] 
  • Show how the single comprehension [(x,y)|x<-[1,2,3],y<-[4,5,6with two generators can be re-expressed using two comprehensions with single generators.Hint make use of the library function concat and nest one comprehension with the other.
concat [(\x->[(x,y)|y<-[4,5,6]])n| n <-[1,2,3]]

ごにょごにょ弄ってたら、こんな関数が出きて題意は見たしているけど、恐らく求められている解答とは違うだろう。


concat [[(x,y)|y<-[4,5,6]]|x<-[1,2,3]]

こうか。意外に難問だった。

  • Redefine the function positions using the function find.
positions x xs = [i|(x',i)<-zip xs[0..n],x==x']
                  where n = length xs - 1
find k t = [v|(k'v) <-t,k==k']
positions x xs = find x (zip xs [0..])
  • The scalar product of two lists of integer xs and ys of length n is given by the sum of the products of corresponding integers:In a similar manner to the function chisqr,show how a list comprehension can be used to define a function scalarproduct::[Int]->[Int]->Int that returns the scalar product of two lists.For example
>scalarproduct [1,2,3][4,5,6]
32
--scalarproduct xs ys  = sum $ zipWith (*) xs ys
--scalarproduct = curry $ sum.uncurry (zipWith (*)) --短かくならなかった。 
scalarproduct xs ys  = sum [x*y|(x,y)<-zip xs ys]
  • Modify the Caesar cipher program to also handle upper-case letters
> import Char

Encoding and decoding
---------------------

> low2int                       :: Char -> Int
> low2int c                     =  ord c - ord 'a'
> 
> int2low                       :: Int -> Char
> int2low n                     =  chr (ord 'a' + n)
>                                  
> upp2int                       :: Char -> Int
> upp2int c                     =  ord c - ord 'A'
> 
> int2upp                       :: Int -> Char
> int2upp n                     =  chr (ord 'A' + n)
> 
> shift                         :: Int -> Char -> Char
> shift n c | isLower c         =  int2low ((low2int c + n) `mod` 26)
>           | isUpper c         =  int2upp ((upp2int c + n) `mod` 26)
>           | otherwise         =  c
> 
> encode                        :: Int -> String -> String
> encode n xs                   =  [shift n x | x <- xs]

Frequency analysis
------------------

> table                         :: [Float]
> table                         =  [8.2, 1.5, 2.8, 4.3, 12.7, 2.2, 2.0,
>                                   6.1, 7.0, 0.2, 0.8,  4.0, 2.4, 6.7,
>                                   7.5, 1.9, 0.1, 6.0,  6.3, 9.1, 2.8,
>                                   1.0, 2.4, 0.2, 2.0,  0.1]
> 
> alphabets                        :: String -> Int
> alphabets xs                     =  length [x | x <- xs, isLower x || isUpper x]
>
> count                         :: Char -> String -> Int
> count x xs                    =  length [x' | x' <- xs, x == x']
>
> percent                       :: Int -> Int -> Float
> percent n m                   =  (fromIntegral n / fromIntegral m) * 100
>
> freqs                         :: String -> [Float]
> freqs xs                      =  [percent (count x (map toLower xs)) n | x <- ['a'..'z']]
>                                  where n = alphabets xs
>
> chisqr                        :: [Float] -> [Float] -> Float
> chisqr os es                  =  sum [((o - e) ^ 2) / e | (o,e) <- zip os es]
> 
> rotate                        :: Int -> [a] -> [a]
> rotate n xs                   =  drop n xs ++ take n xs
> 
> positions                     :: Eq a => a -> [a] -> [Int]
> positions x xs                =  [i | (x',i) <- zip xs [0..], x == x']
> 
> crack                         :: String -> String
> crack xs                      =  encode (-factor) xs
>                                  where
>                                     factor = head (positions (minimum chitab) chitab)
>                                     chitab = [chisqr (rotate n table') table | n <- [0..25]]
>                                     table' = freqs xs

実行結果は

*Main> encode 4 "Good morning,every one.This is a pen.Can you speak English?"
"Kssh qsvrmrk,izivc sri.Xlmw mw e tir.Ger csy wtieo Irkpmwl?"
*Main> crack it
"Good morning,every one.This is a pen.Can you speak English?"
*Main> 

Chapter 6

  • Define the exponentiation operater ^ for non-negative integers using the same pattern of recursion as the multiplication operator *,and sho how 2 ^ 3 is evaluated using your definition.
n ^ 0 = 1
n ^ k = n * (n ^ (k-1))


2 ^ 3 = 2 * (2 ^ 2)=2 * 2 * (2 ^ 1)= 2 * 2 * 2 * (2 ^ 0)= 2 * 2 * 2 * 1 = 8 
  • Using the definition given in this chapter,show how length [1,2,3],drop 3 [1,2,3,4,5],and init[1,2,3] are evaluated.
length[1,2,3]=1+length[2,3]=1+1+length[3]=1+1+1+length[]=1+1+1+0=3
drop 3 [1,2,3,4,5] = drop 2 [2,3,4,5] = drop 1 [3,4,5] = drop 0 [4,5] = [4,5]
init [1,2,3]=1:init[2,3]=1:2:init[3]=1:2:[]=[1,2]
  • Without looking at the definition from the standard prelude,define the following library functions using recursion.

Note:most of these functions are in fact defined in the prelude using other library functions,rather than using explicit recursion.

--Decide if all logical values in a list are True
and:: [Bool]->Bool
and []  = True
and (x:xs)  = x && (and xs)

--Concatenate a list of lists
concat :: [[a]]->[a]
concat [] = []
concat (x:xs) = x ++ concat xs 

--Produce a list with n identical elements
replicate::Int->a->[a]
replicate 0 _ = []
replicate n x = x:replicate (n-1) x

--Select the nth elemenet of a list
(!!)::[a]->Int->a
[]     !! _ = error "the index is too large."
(x:xs) !! 0 = x
(x:xs) !! i = xs !! (i-1)

--Decide if a value is an element of a list
elem::Eq a => a ->[a]->Bool
elem x []     = False
elem x (y:ys) = x == y || elem x ys 
    • Define a recursive function merge:Ord a =>[a]->[a]->[a] that merges two sorted lists to give a single sorted list.For example:
> merge [2,5,6] [1,3,4]
[1,2,3,4,5,6]

Note:your definition should not use other functions on sorted list such an insert or isort,but should be defined using explicit recursion.


merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
  | x < y            = x:merge xs (y:ys)
  | otherwise        = y:merge (x:xs) ys
  • Using merge,define a recursive function msort::Ord a=>[a]->[a] that implements merge sort,in which the empty list and singleton lists are already sorted,and any other list is sorted by merging together the two lists that result from sorting the two halves of the list separately.

Hint:first define a function halve::[a]->([a],[a]) that splits a list into two halves whose lengths differ by at most one.

halve xs = halve' xs ([],[])
halve' []     a_b   = a_b
halve' (x:xs) (a,b) = halve' xs (x:b,a)

msort [] = []
msort [x] = [x]
msort xs = let (first,second) = halve xs
           merge (msort first) (msort second)
  • Using the five-step process,define the library functions that calculate the sum of a list of numbers,take a given number of elements from the start of a list,and select the last element of a non-empty list.
--Sum
1.Define the type

sum::Num a=>[a]->a

2.Enumerate the cases

sum []     =
sum (x:xs) =

3.define the simple cases

sum []    = 0

4.define the other cases

sum (x:xs) = x + sum xs

5.Generalize and simplify

sum::Num a=>[a]->a
sum = foldl1 (+) 0
--take
1,define the type
take::Int->[a]->[a]

2,Enumerate the cases

take 0 []      = 
take 0 (x:xs)  =
take n []      =
take n (x:xs)  =

3,Define the simple cases

take 0 []      = []
take 0 (x:xs)  = []
take n []      = []

4,Define the other cases

take n (x:xs)  = x:take (n-1) xs

5,Generize and simplify

take::Int->[a]->[a]
take 0  _ = []
take _ [] = []
take n (x:xs) = x:take (n-1) xs

--last
1,Define the type
last::[a]->a
2,Enumerate cases

last []     = 
last [x]    =
last (x:xs) =

3,Define the simple cases

last []  = error "empty-list"
last [x] = x

4,Define the other cases
last (x:xs) = last xs

5,Generize and Simplify

last::[a]->a
last []  = error "empty-list"
last [x] = x
last (x:xs) = last xs

Chapter 7

  • Show how the list comprehension [f x|x<-xs,p x]can be re-expressed using the higher-order functions map and filter.
(map f.filter p) xs
  • Without looking at the definition from the standard prelude define the higher-order functions all,any,takeWhile,and dropWhile

all f []     = True
all f (x:xs) = f x && all f xs

any f []     = False
any f (x:xs) = f x || any x xs

takeWhile f []      = []
takeWhile f (x:xs)  
  | f x             = x:takeWhile f xs
  |otherwise        = []

dropWhile f []     = []
dropWhile f (x:xs) 
  |f  x             = dropWhile f xs
  |otherwise        = x:xs
  • Redefine the function map f and filter p using foldr
map' f = foldr (\x y-> f x:y) []
filter' p = foldr (\x y-> if p x then x:y else y) []
  • Using foldl,define a function dec2int::[Int]->Int that convers a decimal number into an integer.For example
> dec 2 int [2,3,4,5]
2346

(((0*10+2)*10+3)*10+4)*10+5

dec2int = foldl (\x y-> x*10+y) 0 
  • Explain why the following definition is Invalid
compose ::[a->a]->(a->a)
compose = foldr (.) id
sumsqreven =  compose [sum,map(^2),filter even] 
sum::Num a=>[a]->a 
map(^2)::Num a=>[a]->[a]
filter even::Integral a=>[a]->[a]

リストに含まれる型は全て同じでなければならないのに、そうなっていない。
  • Without looking at the standard prelude,define the higher-order library function curry that converts a function on pairs tinto a curried function,and conversely,the function uncurry that converts a curried function with two arguments into a function on pairs.Hint:first write down the types of the two function
curry::((a,b)->c)->a->b->c
curry f a b = f(a,b)
uncurry::(a->b->c)->(a,b)->c
uncurry f (a,b) = f a b
  • A higher-order function unfold that encapsulates a simplte patten of recursion for producing a list can be defined as follows
unfold p h t x| p x      = []
              |otherwise = h x:unfold p h t (t x)

That is,the function unfold p h t produces the empty list if the predicate p is true of the arugment,and other wise produces a non-empty list by applying the function h to give the head,and the function t to generate another argument that is recursively processed in the same way to produce the tail of the list.For example,the function int2bin can be rewritten more compactly using unfold as follows:

int2bin = unfold (==0)(`mod` 2)(`div` 2)

Redefine the function chop8,map f and iterate f using unfold.


chop8 = unfold null (take 8) (drop 8)

map f = unfold null (f.head) tail

iterate f = unfold (const True) id f

Hint:the library function error::String->a terminates evaluation and displays the given string an error message.

> import Char

Base conversion
---------------

> type Bit                      =  Int
> 
> bin2int                       :: [Bit] -> Int
> bin2int                       =  foldr (\x y -> x + 2*y) 0
> 
> int2bin                       :: Int -> [Bit]
> int2bin 0                     =  []
> int2bin n                     =  n `mod` 2 : int2bin (n `div` 2)

Transmission
------------

> make8                         :: [Bit] -> [Bit]
> make8 bits                    =  take 8 (bits ++ repeat 0)
> 
> encode                        :: String -> [Bit]
> encode                        =  concat . map (setParity . make8 . int2bin . ord)
> 
> chop9                         :: [Bit] -> [[Bit]]
> chop9 []                      =  []
> chop9 bits                    =  take 9 bits : chop9 (drop 9 bits)
> 
> decode                        :: [Bit] -> String
> decode                        =  map (chr . bin2int.checkParity) . chop9
> 
> transmit                      :: String -> String
> transmit                      =  decode . channel . encode
> 
> channel                       :: [Bit] -> [Bit]
> channel                       =  id
>                                
> setParity                     :: [Bit] -> [Bit]
> setParity bits                =  parityBit bits:bits
> 
> parityBit                     :: [Bit] -> Bit 
> parityBit bits |odd $ length $ filter (==1) bits = 1
>                |otherwise                        = 0
> checkParity                   :: [Bit] -> [Bit]
> checkParity (parity:bits) |even $ length $ filter (==1) (parity:bits) = bits
>                           |otherwise                                  = error "parity error."

  • Test your new string transmitter program from the previous exercise using a faulty communication channnel taht forgets the first bit,which can be modelled using the tail function on lists of bits.

テストのために追加したコード

> faultyChannel                 :: [Bit] -> [Bit]
> faultyChannel                 = tail
>
> faultyTransmit                :: String->String
> faultyTransmit                = decode.faultyChannel.encode

実行結果

*Main> transmit "hoge"
"hoge"
*Main> faultyTransmit "hoge"
"*** Exception: parity error.

通常の通信路では正しく送受信され、ひどい通信路ではparityエラーが発生するようになっている。

ewerunakakuzewerunakakuz2017/02/11 08:19http://dapoxetine-onlinepriligy.net/ - dapoxetine-onlinepriligy.net.ankor <a href="http://ventolinsalbutamol-buy.org/">ventolinsalbutamol-buy.org.ankor</a> http://ventolinsalbutamolbuy.org/

eamerzofzueamerzofzu2017/02/11 08:27http://dapoxetine-onlinepriligy.net/ - dapoxetine-onlinepriligy.net.ankor <a href="http://ventolinsalbutamol-buy.org/">ventolinsalbutamol-buy.org.ankor</a> http://ventolinsalbutamolbuy.org/

abiriwiyewiabiriwiyewi2017/02/11 08:39http://dapoxetine-onlinepriligy.net/ - dapoxetine-onlinepriligy.net.ankor <a href="http://ventolinsalbutamol-buy.org/">ventolinsalbutamol-buy.org.ankor</a> http://ventolinsalbutamolbuy.org/

gohupisgohupis2017/02/11 08:46http://dapoxetine-onlinepriligy.net/ - dapoxetine-onlinepriligy.net.ankor <a href="http://ventolinsalbutamol-buy.org/">ventolinsalbutamol-buy.org.ankor</a> http://ventolinsalbutamolbuy.org/

ewpoxobuewpoxobu2017/02/12 05:43http://dapoxetine-onlinepriligy.net/ - dapoxetine-onlinepriligy.net.ankor <a href="http://ventolinsalbutamol-buy.org/">ventolinsalbutamol-buy.org.ankor</a> http://ventolinsalbutamolbuy.org/

ukoyumuukoyumu2017/02/12 06:02http://dapoxetine-onlinepriligy.net/ - dapoxetine-onlinepriligy.net.ankor <a href="http://ventolinsalbutamol-buy.org/">ventolinsalbutamol-buy.org.ankor</a> http://ventolinsalbutamolbuy.org/

iviusewokagiviusewokag2017/02/13 00:58http://dapoxetine-onlinepriligy.net/ - dapoxetine-onlinepriligy.net.ankor <a href="http://ventolinsalbutamol-buy.org/">ventolinsalbutamol-buy.org.ankor</a> http://ventolinsalbutamolbuy.org/

evatovofutaevatovofuta2017/02/13 01:16http://dapoxetine-onlinepriligy.net/ - dapoxetine-onlinepriligy.net.ankor <a href="http://ventolinsalbutamol-buy.org/">ventolinsalbutamol-buy.org.ankor</a> http://ventolinsalbutamolbuy.org/

agxabahuaagxabahua2017/02/13 22:43http://dapoxetine-onlinepriligy.net/ - dapoxetine-onlinepriligy.net.ankor <a href="http://ventolinsalbutamol-buy.org/">ventolinsalbutamol-buy.org.ankor</a> http://ventolinsalbutamolbuy.org/

ojifokoxeojifokoxe2017/02/14 15:55http://dapoxetine-onlinepriligy.net/ - dapoxetine-onlinepriligy.net.ankor <a href="http://ventolinsalbutamol-buy.org/">ventolinsalbutamol-buy.org.ankor</a> http://ventolinsalbutamolbuy.org/

ecejizosuvalecejizosuval2017/02/14 16:12http://dapoxetine-onlinepriligy.net/ - dapoxetine-onlinepriligy.net.ankor <a href="http://ventolinsalbutamol-buy.org/">ventolinsalbutamol-buy.org.ankor</a> http://ventolinsalbutamolbuy.org/

usazujehnexehusazujehnexeh2017/02/15 07:24http://without-prescription-buyretin-a.net/ - without-prescription-buyretin-a.net.ankor <a href="http://doxycycline100mgbuy.com/">doxycycline100mgbuy.com.ankor</a> http://cialistadalafillowest-price.net/

ivijefisivijefis2017/02/15 07:42http://without-prescription-buyretin-a.net/ - without-prescription-buyretin-a.net.ankor <a href="http://doxycycline100mgbuy.com/">doxycycline100mgbuy.com.ankor</a> http://cialistadalafillowest-price.net/

kipoufbuevovakipoufbuevova2017/02/15 23:16http://without-prescription-buyretin-a.net/ - without-prescription-buyretin-a.net.ankor <a href="http://doxycycline100mgbuy.com/">doxycycline100mgbuy.com.ankor</a> http://cialistadalafillowest-price.net/

oqitetyacoioqitetyacoi2017/02/15 23:33http://without-prescription-buyretin-a.net/ - without-prescription-buyretin-a.net.ankor <a href="http://doxycycline100mgbuy.com/">doxycycline100mgbuy.com.ankor</a> http://cialistadalafillowest-price.net/

ubajufobediubajufobedi2017/02/16 15:10http://without-prescription-buyretin-a.net/ - without-prescription-buyretin-a.net.ankor <a href="http://doxycycline100mgbuy.com/">doxycycline100mgbuy.com.ankor</a> http://cialistadalafillowest-price.net/

izeyupbizeyupb2017/02/17 08:38http://without-prescription-buyretin-a.net/ - without-prescription-buyretin-a.net.ankor <a href="http://doxycycline100mgbuy.com/">doxycycline100mgbuy.com.ankor</a> http://cialistadalafillowest-price.net/

ovebuyuovebuyu2017/02/17 08:57http://without-prescription-buyretin-a.net/ - without-prescription-buyretin-a.net.ankor <a href="http://doxycycline100mgbuy.com/">doxycycline100mgbuy.com.ankor</a> http://cialistadalafillowest-price.net/

ifuzororipoifuzororipo2017/02/18 02:31http://without-prescription-buyretin-a.net/ - without-prescription-buyretin-a.net.ankor <a href="http://doxycycline100mgbuy.com/">doxycycline100mgbuy.com.ankor</a> http://cialistadalafillowest-price.net/

ogufihealeigogufihealeig2017/02/18 21:21http://without-prescription-buyretin-a.net/ - without-prescription-buyretin-a.net.ankor <a href="http://doxycycline100mgbuy.com/">doxycycline100mgbuy.com.ankor</a> http://cialistadalafillowest-price.net/

ubujihiduduhubujihiduduh2017/02/18 21:21http://without-prescription-buyretin-a.net/ - without-prescription-buyretin-a.net.ankor <a href="http://doxycycline100mgbuy.com/">doxycycline100mgbuy.com.ankor</a> http://cialistadalafillowest-price.net/

ejahaafcucejahaafcuc2017/02/18 21:38http://without-prescription-buyretin-a.net/ - without-prescription-buyretin-a.net.ankor <a href="http://doxycycline100mgbuy.com/">doxycycline100mgbuy.com.ankor</a> http://cialistadalafillowest-price.net/

ugesexamugesexam2017/02/18 21:38http://without-prescription-buyretin-a.net/ - without-prescription-buyretin-a.net.ankor <a href="http://doxycycline100mgbuy.com/">doxycycline100mgbuy.com.ankor</a> http://cialistadalafillowest-price.net/

2009-01-02

HCFP-Chapter 11 プログラム開発  HCFP-Chapter 11 プログラム開発 - 他人のHaskell日記 を含むブックマーク

問題を理解する

最初にしなければならない事は、いまから解こうとしている問題を理解することだ

  • 問題への入力と出力は何か?入力や出力に特別な条件はあるか?
  • 問題を明白にするには例を見るのが役立つ
  • 問題は解けるか?仕様は完全か?明らかにせねばならぬ側面があるか?
  • 複数の理解の仕方があるならば、仕様者に、何を意図しているのか聞け
  • 問題は構造を持っているか?問題は分割できるか?図が問題の著述に役立つか?

ソリューションを設計する

プログラムを書くまえに、どのようにやるのか計画する必要がある。

  • 似たような問題を見たことがあるか?そうなら、それをガイドに使える
  • より単純だが関連した問題を考えられるか?それを解けるなら、それを使うか、改造できる。
  • 問題を一般化できるか?元の問題よりも簡潔になるかもしれない。
  • 問題のアーキテクチャーは何か?(比較的)独立に解決できるような部分に分解できるか?部品それぞれについてと同様、部品を組み合わせる方法についても考えなければならない。
  • ボトムアップアプローチ:入力から出力まで、どういけばいいか?中間のデータをガイドに使え。
  • トップダウンアプローチ:どのようなリソースがあれば、問題が解決できるかを考えろ。
  • 計画の時点ですら、使えるリソースが何かを知っておくことは重要だ。プログラミング言語やライブラリが何を提供しているのかをチェックしておけ。他の重要なリソースには、過去に書いたあなた自身のプログラムも含まれる。
  • 変化を念頭に入れて設計せよ。プログラムが便利なら、そのライフタイムにおいて何度も変更されるだろう。

プログラムを書く

プログラムを書くには、言語が提供するリソースについて知っておく必要がある。非公式な設計や計画に従う必要もある。

  • Haskellに存在する、リストに対する多くのライブラリ関数がプログラミングをサポートする。これらのいくつかは一般的な多相型高階関数であり、いろいろな状況で使える。もし可能なら使ってみよう。
  • 他のデータタイプに似たような一般的な関数が定義できることに気がつくだろう。これらの関数を使うのは、ソリューションをいちから書くより簡単だ。
  • 特定の関数を抽象化することで、一般的な関数を定義することができる。特定の関数(例えば2倍するといった)は、mapのような一般的な関数のパラメータにすることができる。
  • 多くの言語で、異なる場合への定義ができる。Haskellパターンマッチングも提供しており、それは場合を区別するだけでなく、オブジェクトの一部を選択できる。
  • 再帰はリストや数値のようなデータタイプに対してプログラムを設計する一般的な戦略である。再帰関数fを引数xについて定義するとき「f .. があればどう定義できるか」と考えてみよう。
  • リスト内包表記はリストに対する表現力の高い記法を提供する。
  • 関数を定義しようとすると、更に他の関数を定義する必要がでてくる。それはwhere節かtop-levelにおける。
  • 必要な関数が定義できない場合、単純なものを定義してみよう。それは欲している関数のモデルになるかもしれないし、最終的な関数の定義で使えるかもしれない。

反省

やったことをふりかえることはプログラム、設計、そのプログラム自身の仕様に影響を与えるだろう

  • ソリューションをテストできるか?特別な場合について熱心に見るだけでなく、似たような振舞いを見せるべきプログラムのテストグループを考える必要がある。
  • テストがerrorやバグを暴いたら、その源を探そう。エラーは偶然の失敗のせいなのか、Haskell言語がどう動くのか理解してなかったせいなのか、問題を解決する手段を勘違いしていたからなのか?問題そのものを勘違いしていたのか?それとも他の理由なのか?
  • 犯した誤ちから学ぶことができる。全ての誤ちを、理由とともに記録せよ。そうすれば、誤ちを繰り返さずに済む。
  • プログラムが正しく振る舞うことを証明できるか?そうでなければ、なぜそうなのか?それは、プログラムや設計での誤ちに面しているのか?
  • 同じプログラムを書けと言われたら、どのように違った書き方が出来るだろうか?
  • プログラムを拡張や変更しろといわれたら、それは簡単だろうか?難しいとしたら、どのように設計し、ソリューションを書いていたなら、もっと簡単に変更できただろうか?
  • プログラムは十分な速度で動くだろうか?そうでなければ、どこにボトルネックがあるかわかるだろうか?どのように変更をしてパフォーマンスを向上させることができるかわかるだろうか?

メモ:Haskell再帰  メモ:Haskellの再帰 - 他人のHaskell日記 を含むブックマーク

Haskell再帰をどうやってやっているのだろう

(中略)

一時はYコンビネータ使おうとまで思ったけど、Yコンビネータはハイブロウすぎる。そんな言語だれも使ってくれないだろう。巧妙に隠蔽する方法も無い訳では無いけど。

http://homepage3.nifty.com/mogami/diary/d0608.html#04t2

Haskell 98 レポートを見ると

変換:

(中略)

let p = e1 in e0 = let p = fix ( \ ~p -> e1) in e0

ここで fix は最小不動点演算子である。

http://www.sampou.org/haskell/report-revised-j/exps.html

と書いてあるので、まさに不動点演算子を使いながら、それを巧妙に隠蔽しているように思う。

ちなみにモナドの場合は、構文拡張オプションを指定しない限り、mfixという不動点演算子を使わなければならないようである。(理解していないが、haskell-jpのメーリングリストのログにそういう話題があった。)

DorieDorie2012/01/06 06:29You're a real deep thinker. Thanks for sahring.

ifziveezifziveez2012/01/06 19:43jOfl5V <a href="http://onmqlcypjcnm.com/">onmqlcypjcnm</a>

gwsvahhnagwsvahhna2012/01/07 22:45WhcWgD , [url=http://izepljmcpetj.com/]izepljmcpetj[/url], [link=http://zcxvehkfzeta.com/]zcxvehkfzeta[/link], http://rtlvbxcoojif.com/

qmjwodzrvkbqmjwodzrvkb2012/01/08 20:40z3GSDB <a href="http://lncfwqptnxpk.com/">lncfwqptnxpk</a>

ojfeehozjojfeehozj2012/01/11 03:21Xt1caF , [url=http://udkkewqodmtx.com/]udkkewqodmtx[/url], [link=http://rptwageqyyzu.com/]rptwageqyyzu[/link], http://vfihdnhksmdr.com/