2009-01-04
■ Programming in Haskell Exercise 
Chapter 1
double(double 2) =double(2+2) =(2+2)+(2+2) =(2+2)+4 =4+4 =8
- Show that sum [x] = x for any number x
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
- 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))
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)
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]
> 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
> 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
- Modify the string transmitter program to detect simple transmission errors using parity bits.That is,each eight-bit binary number produced during encoding is extended with a parity bit,set to one if the number contains an odd number of ones,and to zero otherwise.In turn,each resulting nine bit binary number consumed during decoding is checked to ensure that is parity bit is correct,with the parity bit being discarded if this is the case,and a parity error reported otherwise,
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エラーが発生するようになっている。
コメントを書く
