7つの言語7つの世界 Haskell セルフスタディ2日目

「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)
*Main> myQSort [3, 1, 2] [1,2,3]

次に選択ソートを書いてみました。最小要素を取り出して、残りのリストを選択ソートします。

["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)
*Main> mySelectionSort ["C", "A", "B"] ["A","B","C"]

比較関数を受け取って、リストをソート

• リストと, 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)
*Main> mySort ascendSimple [2020, 7, 2] [2,7,2020] *Main> mySort descendSimple [2020, 7, 2] [2020,7,2]

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)
*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"]

a <= b で比較するときに、大文字で比較する ascendToUpperを作りました。

ascendToUpper a b = (map toUpper a) <= (map toUpper b) descendToUpper a b = not (ascendToUpper a b)
*Main> mySort ascendSimple ["a", "B", "c"] ["B","a","c"] *Main> mySort ascendToUpper ["a", "B", "c"] ["a","B","c"]

比較する前の評価を追加するたびに、ascendXXX、descendXXX を作ることになります。もう少しがんばって、ascned、descend関数に、評価関数と a b を渡すようにしてみます。

ascend eval a b = (eval a) <= (eval b) descend eval a b = not (ascend eval a b)
*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"]

文字列を数値に変換

• 文字列を数値に変換する Haskell の関数を書け.文字列の形式は $2,345,678.99とし,先頭に 0 がくる可能性もあるものとする.

Haskellのread関数やisNumber関数を使ったバージョン。

parseDoller s = read [c | c <-s, isNumber(c) || c == '-'] :: Double
*Main Data.Char> parseDoller "$2,345,678.99" 2.34567899e8

read関数を使わずにやってみたら?

1文字づつ見ながら計算するバージョン。小数点の左側用の計算、右側用の計算を分けました。

afterDecimalPointdivisorsumch戻り値
False10'2'(False, 1, 2)
False12'3'(False, 1, 2 * 10 + 3)
False123'4'(False, 1, 23 * 10 + 4)
False1234'5'(False, 1, 234 * 10 + 5)
False12345'6'(False, 1, 2345 * 10 + 6)
False123456'7'(False, 1, 23456 * 10 + 7)
False1234567'8'(False, 1, 234567 * 10 + 8)
False12345678'.'(True, 10, 2345678)
True102345678'9'(True, 100, 2345678 + 9/10)
True1002345678.9'9'(True, 1000, 2345678.9 + 9/100)
True10002345678.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')
*Main> parseDoller2 "$2,345,678.9" 2345678.9 *Main> parseDoller2 "$2,345,678.99" 2345678.9899999998

小数点以下が、.99 でなくなってるよ

コンソールで、2345678 + 9 / 10 + 9 / 100 を計算すると、同じように 2345678.9899999998 になりました。浮動小数点計算の誤差が蓄積されるのでしかたがありません。

しかし、234567899 / 100 を計算すると、2345678.99 になりました。これをふまえて改良したバージョン。

afterDecimalPointdivisorsumch戻り値
False10'2'(False, 1, 2)
False12'3'(False, 1, 2 * 10 + 3)
False123'4'(False, 1, 23 * 10 + 4)
False1234'5'(False, 1, 234 * 10 + 5)
False12345'6'(False, 1, 2345 * 10 + 6)
False123456'7'(False, 1, 23456 * 10 + 7)
False1234567'8'(False, 1, 234567 * 10 + 8)
False12345678'.'(True, 1, 2345678)
True12345678'9'(True, 10, 2345678 * 10 + 9)
True1023456789'9'(True, 100, 23456789 * 10 + 9)
True100234567899234567899 / 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')
*Main> parseDoller3 "$2,345,678.9" 2345678.9 *Main> parseDoller3 "$2,345,678.99" 2345678.99

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]

部分適用関数

• 部分適用関数を用いて,ある数値の 2 分の 1 を返す関数を定義せよ.

まったく見当がつかないよ。
検索して先輩たちの解答例を見たよ。

答えは、(/ 2) でした。その上で書籍を見直すと、p250〜251に部分適用関数(* 2)(* 5)の説明がありました。

half = (/ 2)
*Main Data.Char> half 5 2.5

2 * 4 は、(2 *) 4 とも (* 4) 2 とも書けるけど、
どうもピンとこないよ。

(* 2) . (* 4) は、(2 *) . (4 *) とは書けないのね

• 部分適用関数を用いて,文字列の末尾に \n を追加する関数を定義せよ.

「部分適用関数」ですから、次の定義ではないんですね。

addNewLine s = s ++ "\n"

まったく見当がつかないよ。
検索して先輩たちの解答例を見たよ。

答えは、(++ "\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 ‘/’

最大公約数

• 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)
*Main Data.Char> myGcd 1071 1029 21 *Main Data.Char> myGcd 3 3 3 *Main Data.Char> myGcd 12 4 4

数の遅延シーケンス

• 素数の遅延シーケンスを作成せよ.

試し割りで素数判定をします。
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)]
*Main> take 20 generatePrimes [1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67]

長い文字列を複数行に分割する

• 長い文字列を適切な単語境界で複数の行に分割せよ.

"Every expression in Haskell has a type which is determined at compile time."

を1行20文字以内になるように、スペースで分割して、次のようなリストにします。

["Every expression in", "Haskell has a type", "which is determined", "at compile time."]
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])
*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]

分割した行に行番号

• 上の問題で,分割した行に行番号を付けよ.

[(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]
*Main> lineNum (wrap 20 s) ["1: Every expression in","2: Haskell has a type","3: which is determined","4: at compile time."]

左寄せ、右寄せ、中央寄せ

• 上記の各問題で,テキストをスペースで左寄せ,右寄せ,中央寄せ(左右の余白を揃える)にする関数を追加せよ.

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
*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]

おすすめ書籍

Grahaum Hutton (著) ラムダノート 2019

タイトルとURLをコピーしました