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

「７つの言語７つの世界」第8章、Haskell（ハスケル）言語

７つの言語７つの世界
セルフスタディ2日目
おすすめ書籍

７つの言語７つの世界

Ruby
Io
Prolog
Scala
Erlang
Cloijure
Haskell

７つの言語７つの世界

オーム社 (2011/7/22)

Amazon

楽天

セルフスタディ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 == '-'] :: DoubleCode 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.5Code 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)