「7つの言語 7つの世界」第8章、Haskell(ハスケル)言語
7つの言語 7つの世界
- Ruby
- Io
- Prolog
- Scala
- Erlang
- Cloijure
- Haskell
セルフスタディ2日目
for文を使わずに考えるのが難しいよ
リストのソート
• リストを受け取り,ソートされたリストを返すソートプログラムを書け.
クイックソートは、リストの中央位置の要素の値を基準にして、小さいものを左側に、大きいものを右側に移動します。左側、右側それぞれをクイックソートします。
今回は、リストの先頭要素を基準に、tailから先頭要素より以下を選択して、左側に。tailから先頭要素より大きいものを選択して、右側に。
myQSort [] = []
myQSort (h:t) = do
let left = myQSort [x | x <- t, x <= h]
let right = myQSort [x | x <- t, h < x]
left ++ (h : right)
Code language: Haskell (haskell)
*Main> myQSort [3, 1, 2]
[1,2,3]
Code language: Haskell (haskell)
次に選択ソートを書いてみました。最小要素を取り出して、残りのリストを選択ソートします。
["C", "A", "B"] の最小要素は、"A"
"A"の位置は、[1]
["C", "A", "B"]を位置1で分割して、(["C"], ["A", "B"])
残りのリストは、["C", "B"]
import Data.List
mySelectionSort [] = []
mySelectionSort list = do
let min = minimum list
let (pos:_) = elemIndices min list
let (a, (_:t)) = splitAt pos list
[min] ++ mySelectionSort (a ++ t)
Code language: Haskell (haskell)
*Main> mySelectionSort ["C", "A", "B"]
["A","B","C"]
Code language: Haskell (haskell)
比較関数を受け取って、リストをソート
• リストと, 2 つの引数を比較する関数を受け取り,ソートされたリストを返すソートプログラムを書け.
さきほどのクイックソートmyQSortのx <= h や h < x を 外部から渡すようにします。le は、lessThanOrEqualsの略で、<= の意味です。
比較関数は、昇順の ascend、降順の desend を作りました。
mySort le [] = []
mySort le (h:t) = do
let left = mySort le [x | x <- t, le x h]
let right = mySort le [x | x <- t, not (le x h)]
left ++ (h : right)
ascendSimple a b =
a <= b
descendSimple a b =
not (ascendSimple a b)
Code language: Haskell (haskell)
*Main> mySort ascendSimple [2020, 7, 2]
[2,7,2020]
*Main> mySort descendSimple [2020, 7, 2]
[2020,7,2]
Code language: Haskell (haskell)
a <= b で比較するときに、絶対値で比較する ascendAbsを作りました。
myAbs a = if a < 0 then (-a) else a
ascendAbs a b =
(myAbs a) <= (myAbs b)
descendAbs a b =
not (ascendAbs a b)
Code language: Haskell (haskell)
*Main> mySort ascendSimple [-2020, 7, 2]
[-2020,2,7]
*Main> mySort ascendAbs) [-2020, 7, 2]
[2,7,-2020]
*Main> mySort ascendSimple ["a", "B", "c"]
["B","a","c"]
*Main> mySort (ascend (map toUpper)) ["a", "B", "c"]
["a","B","c"]
Code language: Haskell (haskell)
a <= b で比較するときに、大文字で比較する ascendToUpperを作りました。
ascendToUpper a b =
(map toUpper a) <= (map toUpper b)
descendToUpper a b =
not (ascendToUpper a b)
Code language: Haskell (haskell)
*Main> mySort ascendSimple ["a", "B", "c"]
["B","a","c"]
*Main> mySort ascendToUpper ["a", "B", "c"]
["a","B","c"]
Code language: Haskell (haskell)
比較する前の評価を追加するたびに、ascendXXX、descendXXX を作ることになります。もう少しがんばって、ascned、descend関数に、評価関数と a b を渡すようにしてみます。
ascend eval a b =
(eval a) <= (eval b)
descend eval a b =
not (ascend eval a b)
Code language: Haskell (haskell)
*Main> mySort ascendSimple [-2020, 7, 2]
[-2020,2,7]
*Main> mySort (ascend myAbs) [-2020, 7, 2]
[2,7,-2020]
*Main> mySort ascendSimple ["a", "B", "c"]
["B","a","c"]
*Main> mySort (ascend (map toUpper)) ["a", "B", "c"]
["a","B","c"]
Code language: Haskell (haskell)
文字列を数値に変換
• 文字列を数値に変換する Haskell の関数を書け.文字列の形式は $2,345,678.99とし,先頭に 0 がくる可能性もあるものとする.
Haskellのread
関数やisNumber
関数を使ったバージョン。
parseDoller s = read [c | c <-s, isNumber(c) || c == '-'] :: Double
Code language: Haskell (haskell)
*Main Data.Char> parseDoller "$2,345,678.99"
2.34567899e8
Code language: JavaScript (javascript)
read関数を使わずにやってみたら?
1文字づつ見ながら計算するバージョン。小数点の左側用の計算、右側用の計算を分けました。
afterDecimalPoint | divisor | sum | ch | 戻り値 |
---|---|---|---|---|
False | 1 | 0 | '2' | (False, 1, 2) |
False | 1 | 2 | '3' | (False, 1, 2 * 10 + 3) |
False | 1 | 23 | '4' | (False, 1, 23 * 10 + 4) |
False | 1 | 234 | '5' | (False, 1, 234 * 10 + 5) |
False | 1 | 2345 | '6' | (False, 1, 2345 * 10 + 6) |
False | 1 | 23456 | '7' | (False, 1, 23456 * 10 + 7) |
False | 1 | 234567 | '8' | (False, 1, 234567 * 10 + 8) |
False | 1 | 2345678 | '.' | (True, 10, 2345678) |
True | 10 | 2345678 | '9' | (True, 100, 2345678 + 9/10) |
True | 100 | 2345678.9 | '9' | (True, 1000, 2345678.9 + 9/100) |
True | 1000 | 2345678.99 |
parseDoller2 s = do
let (afterDecimalPoint, divisor, sum) = foldl myFunc (False, 1, 0) s
sum
myFunc :: (Bool, Int, Double) -> Char -> (Bool, Int, Double)
myFunc (False, _, sum) '.' = (True, 10, sum)
myFunc (False, divisor, sum) ch
| '0' <= ch && ch <= '9' =
do
let digit = toDigit ch
let sum2 = sum * 10 + realToFrac(digit)
(False, 1, sum2)
| otherwise =
(False, 1, sum)
myFunc(True, divisor, sum) ch
| '0' <= ch && ch <= '9' =
do
let digit = toDigit ch
let sum2 = sum + realToFrac(digit) / realToFrac(divisor)
(True, divisor * 10, sum2)
| otherwise =
(True, divisor, sum)
toDigit ch = (ord ch) - (ord '0')
Code language: Haskell (haskell)
*Main> parseDoller2 "$2,345,678.9"
2345678.9
*Main> parseDoller2 "$2,345,678.99"
2345678.9899999998
Code language: JavaScript (javascript)
小数点以下が、.99 でなくなってるよ
コンソールで、2345678 + 9 / 10 + 9 / 100 を計算すると、同じように 2345678.9899999998 になりました。浮動小数点計算の誤差が蓄積されるのでしかたがありません。
しかし、234567899 / 100 を計算すると、2345678.99 になりました。これをふまえて改良したバージョン。
afterDecimalPoint | divisor | sum | ch | 戻り値 |
---|---|---|---|---|
False | 1 | 0 | '2' | (False, 1, 2) |
False | 1 | 2 | '3' | (False, 1, 2 * 10 + 3) |
False | 1 | 23 | '4' | (False, 1, 23 * 10 + 4) |
False | 1 | 234 | '5' | (False, 1, 234 * 10 + 5) |
False | 1 | 2345 | '6' | (False, 1, 2345 * 10 + 6) |
False | 1 | 23456 | '7' | (False, 1, 23456 * 10 + 7) |
False | 1 | 234567 | '8' | (False, 1, 234567 * 10 + 8) |
False | 1 | 2345678 | '.' | (True, 1, 2345678) |
True | 1 | 2345678 | '9' | (True, 10, 2345678 * 10 + 9) |
True | 10 | 23456789 | '9' | (True, 100, 23456789 * 10 + 9) |
True | 100 | 234567899 | 234567899 / 100 が結果 |
parseDoller3 s = do
let (afterDecimalPoint, divisor, sum) = foldl myFunc3 (False, 1, 0) s
(fromIntegral sum) / (fromIntegral divisor)
myFunc3 :: (Bool, Int, Int) -> Char -> (Bool, Int, Int)
myFunc3 (False, _, sum) '.' = (True, 1, sum)
myFunc3 (afterDecimalPoint, divisor, sum) ch
| '0' <= ch && ch <= '9' =
do
let digit = toDigit ch
let sum2 = sum * 10 + digit
let divisor2 = if afterDecimalPoint then (divisor * 10) else divisor
(afterDecimalPoint, divisor2, sum2)
| otherwise =
(afterDecimalPoint, divisor, sum)
toDigit ch = (ord ch) - (ord '0')
Code language: Haskell (haskell)
*Main> parseDoller3 "$2,345,678.9"
2345678.9
*Main> parseDoller3 "$2,345,678.99"
2345678.99
Code language: JavaScript (javascript)
2つ飛びの数列、4つ飛びの数列、8つ飛びの数列
• x を引数にとり,遅延シーケンスとして, x で始まる 2 つ飛びの数列を返す関数を書け.次に, y を引数にとり, y で始まる 4 つ飛びの数列を含む関数を書け.これらの関数をリストの作成構文で組み合わせて, x + y で始まる 8 つ飛びの数列を返す関数を作成せよ.
2 つ飛びの数列と4 つ飛びの数列はわかるけど
「リストの作成構文で組み合わせて」は
具体的に何をすればいいのかな?
リスト内包表記で、2 つ飛びの数列と4 つ飛びの数列をzipするのね
(シーケンスを生成するHaskell関数ではなく)シーケンスのi番目と値を関数で表すと、
f(i) = a + 2i
g(i) = b + 4i
h(i) = a + b + 8i
この h(i)と同等の関数を f(i)、g(i) で定義すると、h2(i) = 2 * f(i) - a + g(i) です。
f x = [x, x + 2 ..]
g y = [y, y + 4 ..]
h x y = [x + y, x + y + 8 ..]
h2 x y =[2 * fx - x + gy | (fx, gy) <- zip (f x) (g y)]
*Main Data.Char> take 5 (f 1)
[1,3,5,7,9]
*Main Data.Char> take 5 (g 2)
[2,6,10,14,18]
*Main Data.Char> take 5 (h 1 2)
[3,11,19,27,35]
*Main Data.Char> take 5 (h2 1 2)
[3,11,19,27,35]
Code language: CSS (css)
部分適用関数
• 部分適用関数を用いて,ある数値の 2 分の 1 を返す関数を定義せよ.
まったく見当がつかないよ。
検索して先輩たちの解答例を見たよ。
答えは、(/ 2)
でした。その上で書籍を見直すと、p250〜251に部分適用関数(* 2)
や(* 5)
の説明がありました。
half = (/ 2)
*Main Data.Char> half 5
2.5
Code language: CSS (css)
2 * 4
は、(2 *) 4
とも (* 4) 2
とも書けるけど、
どうもピンとこないよ。
(* 2) . (* 4)
は、(2 *) . (4 *)
とは書けないのね
• 部分適用関数を用いて,文字列の末尾に \n を追加する関数を定義せよ.
「部分適用関数」ですから、次の定義ではないんですね。
addNewLine s = s ++ "\n"
Code language: JavaScript (javascript)
まったく見当がつかないよ。
検索して先輩たちの解答例を見たよ。
答えは、(++ "\n")
でした。
10 / 2
、"abc" ++ "\n"
のような、左右に項目がある演算子は、(10 /)
も (/ 2)
どちらも部分適用関数になるんですね。
*Main> 10 / 2
5.0
*Main> (10 /) 2
5.0
*Main> (/ 2) 10
5.0
カッコで囲んだ (/)
は、また違う結果になりました。
*Main> (/) 10 2
5.0
*Main> ((/) 10) 2
5.0
/ 10 2
はパースエラーでした。
*Main> / 10 2
<interactive>:762:1: error: parse error on input ‘/’
*Main> / 2 10
<interactive>:763:1: error: parse error on input ‘/’
Code language: HTML, XML (xml)
最大公約数
• 2 つの整数の最大公約数を求める関数を書け.
ユークリッドの互除法で計算します。
(問題) 1071 と 1029 の最大公約数を求める。
ユークリッドの互除法
1071 を 1029 で割った余りは 42
1029 を 42 で割った余りは 21
42 を 21 で割った余りは 0
よって、最大公約数は21である。
myGcd a b
| (a == b) =
a
| (a < b) =
myGcd b a
| ((mod a b) == 0) =
b
| otherwise =
myGcd b (mod a b)
Code language: HTML, XML (xml)
*Main Data.Char> myGcd 1071 1029
21
*Main Data.Char> myGcd 3 3
3
*Main Data.Char> myGcd 12 4
4
Code language: CSS (css)
数の遅延シーケンス
• 素数の遅延シーケンスを作成せよ.
試し割りで素数判定をします。
https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A
isPrime n
| n <= 1 =
True
| n == 2 =
True
| (mod n 2) == 0 =
False
| otherwise = do
let x = fromIntegral (n::Int)::Double
let y = ceiling(sqrt x)
length [i | i <- [3, 5 .. y], (mod n i) == 0] == 0
generatePrimes = [n | n <- [1 ..], isPrime(n)]
Code language: PHP (php)
*Main> take 20 generatePrimes
[1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67]
Code language: CSS (css)
長い文字列を複数行に分割する
• 長い文字列を適切な単語境界で複数の行に分割せよ.
"Every expression in Haskell has a type which is determined at compile time."
Code language: plaintext (plaintext)
を1行20文字以内になるように、スペースで分割して、次のようなリストにします。
["Every expression in",
"Haskell has a type",
"which is determined",
"at compile time."]
Code language: plaintext (plaintext)
wrap lenPerLine str = do
let (_, buf, list) = foldl wrapHelper (lenPerLine, "", []) (words str)
if buf == "" then
list
else
list ++ [buf]
wrapHelper (lenPerLine, buf, list) word
| buf == "" && (length word) <= lenPerLine =
(lenPerLine, word, list)
| buf == "" && (length word) > lenPerLine =
(lenPerLine, "", list ++ [word])
| buf /= "" && (length (buf ++ " " ++ word)) <= lenPerLine =
(lenPerLine, (buf ++ " " ++ word), list)
| buf /= "" && (length (buf ++ " " ++ word)) > lenPerLine =
(lenPerLine, word, list ++ [buf])
Code language: Haskell (haskell)
*Main> let s = "Every expression in Haskell has a type which is determined at compile time."
*Main> wrap 20 s
["Every expression in","Haskell has a type","which is determined","at compile time."]
*Main> map length (wrap 20 s)
[19,18,19,16]
Code language: Haskell (haskell)
分割した行に行番号
• 上の問題で,分割した行に行番号を付けよ.
[(1, "Every expression in"),
(2, "Haskell has a type"),
(3, "which is determined"),
(4, "at compile time.") ]
というリストを作ってから、表示します。
lineNum list = do
[(show num) ++ ": " ++ line | (num, line) <- zip [1 .. (length list)] list]
Code language: Haskell (haskell)
*Main> lineNum (wrap 20 s)
["1: Every expression in","2: Haskell has a type","3: which is determined","4: at compile time."]
Code language: Haskell (haskell)
左寄せ、右寄せ、中央寄せ
• 上記の各問題で,テキストをスペースで左寄せ,右寄せ,中央寄せ(左右の余白を揃える)にする関数を追加せよ.
alignLeft lenPerLine str = do
let padLen = lenPerLine - (length str)
if padLen <= 0 then
str
else
str ++ (take padLen (repeat ' '))
alignCenter lenPerLine str = do
let padLen = lenPerLine - (length str)
if padLen <= 0 then
str
else do
let llen = div padLen 2
let rlen = padLen - llen
(take llen (repeat ' ')) ++ str ++ (take rlen (repeat ' '))
alignRight lenPerLine str = do
let padLen = lenPerLine - (length str)
if padLen <= 0 then
str
else
(take padLen (repeat ' ')) ++ str
Code language: Haskell (haskell)
*Main> map (alignCenter 20) (wrap 20 s)
["Every expression in "," Haskell has a type ","which is determined "," at compile time. "]
*Main> map (length . alignCenter 20) (wrap 20 s)
[20,20,20,20]
*Main> map (alignLeft 20) (wrap 20 s)
["Every expression in ","Haskell has a type ","which is determined ","at compile time. "]
*Main> map (length . alignLeft 20) (wrap 20 s)
[20,20,20,20]
*Main> map (alignRight 20) (wrap 20 s)
[" Every expression in"," Haskell has a type"," which is determined"," at compile time."]
*Main> map (length . alignRight 20) (wrap 20 s)
[20,20,20,20]
Code language: Haskell (haskell)