【解答例】Haskellで学ぶF#入門

Haskellで学ぶF#入門の解答例です。

フィボナッチ数

パターンマッチ

【問1】任意のn番目のフィボナッチ数を計算する関数fibをパターンマッチで実装してください。

初期値0, 1を基底部とします。

基底部

let rec fib = function
| 0 -> 0
| 1 -> 1

0, 1, 1, 2, 3, 5, ...よりfib 5について考えます。

具体例

fib 5 = 2 + 3 = fib 3 + fib 4

これをnで一般化すれば再帰部となります。

再帰部

| n -> fib (n - 2) + fib (n - 1)

テストを追加して解答とします。

解答

let rec fib = function
| 0 -> 0
| 1 -> 1
| n -> fib (n - 2) + fib (n - 1)

printfn "%d" <| fib 6

実行結果

8

ガード

【問2】問1で実装した関数に、無限ループを防ぐためのガードを追加してください。

let rec fib = function
| 0 -> 0
| 1 -> 1
| n when n > 1 -> fib (n - 2) + fib (n - 1)
| _ -> failwith "< 0"

printfn "%d" <| fib 6

実行結果

8

match

【問3】問2で実装した関数をmatchで書き直してください。

let rec fib n =
    match n with
    | 0 -> 0
    | 1 -> 1
    | _ when n > 1 -> fib (n - 2) + fib (n - 1)
    | _ -> failwith "< 0"

printfn "%d" <| fib 6

実行結果

8

再実装

【問4】sum, revと同じ機能の関数を再実装してください。sumの掛け算版productも実装してください。

let rec sum = function
| []    -> 0
| x::xs -> x + sum xs

let rec rev = function
| []    -> []
| x::xs -> rev xs @ [x]

let rec product = function
| []    -> 1
| x::xs -> x * product xs

printfn "%d" <| sum [1..5]
printfn "%A" <| rev [1..5]
printfn "%d" <| product [1..5]

実行結果

15
[5; 4; 3; 2; 1]
120

• リストが空になるまで順番にたどるため、基底部として[]を定義します。

別解

※ 勉強会で出た意見を反映した項目です。

@を避けた実装です。本文では説明していませんが末尾再帰です。

let rec rev xs =
    let rec f ys = function
    | []    -> ys
    | x::xs -> f (x::ys) xs
    f [] xs

階乗

【問5】productを使ってfact（階乗）を実装してください。

let rec product = function
| []    -> 1
| x::xs -> x * product xs

let fact n = product [1..n]

printfn "%d" <| fact 5

実行結果

120

垂線の交点

【問6】点 $(p, q)$ から直線 $ax + by = c$ に下した垂線の交点を求める関数perpPointを作成してください。aとbが両方ゼロになると解なしですが、チェックせずに無視してください。

ax + by = c \cdots (1)

(1)への垂線は

bx - ay = d \cdots (2)

(2)に $(p,q)$ を代入します。

d = bp - aq \cdots (3)

(1)と(2)の連立方程式を解いて(3)を代入すれば交点が求まります。

x=\frac{ac+bd}{a^2+b^2}, y=\frac{bc-ad}{a^2+b^2}

これをコード化します。

解答

let perpPoint (p, q) (a, b, c) =
    let d = b * p - a * q
    let x = (a * c + b * d) / (a * a + b * b)
    let y = (b * c - a * d) / (a * a + b * b)
    (x, y)

printfn "%A" <| perpPoint (0., 2.) (1., -1., 0.)

実行結果

(1.0, 1.0)

ROT13

【問7】ROT13を実装してください。

let rot13ch = function
| ch when 'A' <= ch && ch <= 'M'
       || 'a' <= ch && ch <= 'm' -> char <| int ch + 13
| ch when 'N' <= ch && ch <= 'Z'
       || 'n' <= ch && ch <= 'z' -> char <| int ch - 13
| ch -> ch

let rot13 s =
    let rec f = function
    | []    -> []
    | x::xs -> rot13ch x :: f xs
    List.ofSeq s |> f |> Array.ofList |> System.String.Concat

let hello13 = rot13 "Hello, World!"
printfn "%s" hello13
printfn "%s" <| rot13 hello13

実行結果

Uryyb, Jbeyq!
Hello, World!

バブルソート

【問8】バブルソートを実装してください。

⇒ 詳細説明

let rec bswap = function
| [ ] -> [ ]
| [x] -> [x]
| x::xs ->
    match bswap xs with
    | [] -> [x]
    | y::ys ->
        if x > y then y::x::ys
                 else x::y::ys

let rec bsort xs =
    match bswap xs with
    | []    -> []
    | y::ys -> y :: bsort ys

printfn "%A" <| bswap [4; 3; 1; 5; 2]
printfn "%A" <| bsort [4; 3; 1; 5; 2]
printfn "%A" <| bsort [5; 4; 3; 2; 1]
printfn "%A" <| bsort [4; 6; 9; 8; 3; 5; 1; 7; 2]

実行結果

[1; 4; 3; 2; 5]
[1; 2; 3; 4; 5]
[1; 2; 3; 4; 5]
[1; 2; 3; 4; 5; 6; 7; 8; 9]

マージソート

【問9】マージソートを実装してください。

• ソートしながら2つのリストをマージする関数mergeを作ります。
• リストを分割する関数splitを作ります。ソート前のリストは順番を保持することに意味がないため、実装しやすさを優先します。
• 往路で分割、復路でマージを再帰関数で表現します。

let rec merge = function
| xs, [] -> xs
| [], ys -> ys
| x::xs, y::ys ->
    if x < y then x :: merge (xs, y::ys)
             else y :: merge (x::xs, ys)

let rec split = function
| [ ] -> ([ ], [])
| [x] -> ([x], [])
| x::y::zs ->
    let xs, ys = split zs
    (x::xs, y::ys)

let rec msort = function
| [ ] -> [ ]
| [x] -> [x]
| xs ->
    let ys, zs = split xs
    merge (msort ys, msort zs)

printfn "%A" <| msort [4; 6; 9; 8; 3; 5; 1; 7; 2]

実行結果

[1; 2; 3; 4; 5; 6; 7; 8; 9]

クイックソート

【問10】動きを考えて、F#に移植してください。

リスト[4, 6, 9, 8, 3, 5, 1, 7, 2]をソートします。

(n:xs) = 4 : [6, 9, 8, 3, 5, 1, 7, 2]

リストの最初の要素4を基準に3つの部分に分けます。

qsort (n:xs) = qsort lt ++ [n] ++ qsort gteq
    where
        lt   = [x | x <- xs, x <  n]
        gteq = [x | x <- xs, x >= n]

• 4未満: lt = [x | x <- xs, x < n] → [3, 1, 2]
• 4: [x] → [4]
• 4以上: gteq = [x | x <- xs, x >= n] → [6, 9, 8, 5, 7]

ltとgteqをソートして結合します。

実行イメージ

qsort [3, 1, 2] ++ [4] ++ qsort [6, 9, 8, 5, 7]
          ↓                           ↓
      [1, 2, 3] ++ [4] ++       [5, 6, 7, 8, 9]
          ↓                           ↓
      [1, 2, 3,     4,           5, 6, 7, 8, 9]

qsort [3, 1, 2]とqsort [6, 9, 8, 5, 7]の内部では、同様の処理が繰り返されています。

これを踏まえて移植します。

F#

let rec qsort = function
| [] -> []
| n::xs ->
    let lt   = [for x in xs do if x <  n then yield x]
    let gteq = [for x in xs do if x >= n then yield x]
    qsort lt @ [n] @ qsort gteq

printfn "%A" <| qsort [4; 6; 9; 8; 3; 5; 1; 7; 2]

実行結果

[1; 2; 3; 4; 5; 6; 7; 8; 9]

直角三角形の三辺

【問11】三辺の長さが各20以下の整数で構成される直角三角形を列挙してください。並び順による重複を排除する必要はありません。

複数ソースのリスト内包表記に三平方の定理で条件付けします。

printfn "%A" <| [
    for a in 1..20 do
    for b in 1..20 do
    for c in 1..20 do
    if a * a + b * b = c * c then yield (a, b, c)]

実行結果

[(3, 4, 5); (4, 3, 5); (5, 12, 13); (6, 8, 10); (8, 6, 10); (8, 15, 17);
 (9, 12, 15); (12, 5, 13); (12, 9, 15); (12, 16, 20); (15, 8, 17); (16, 12, 20)]

重複排除

※ 勉強会で出た意見を反映した項目です。

条件 $a<b$ を追加すれば並び順による重複が排除できます。

printfn "%A" <| [
    for a in 1..20 do
    for b in 1..20 do
    for c in 1..20 do
    if a * a + b * b = c * c && a < b then yield (a, b, c)]

実行結果

[(3, 4, 5); (5, 12, 13); (6, 8, 10); (8, 15, 17); (9, 12, 15); (12, 16, 20)]

条件で制限するのではなく、ソースから抜けば計算量が削減できます。

printfn "%A" <| [
    for a in 1..20 do
    for b in a..20 do
    for c in b..20 do
    if a * a + b * b = c * c then yield (a, b, c)]

実行結果

[(3, 4, 5); (5, 12, 13); (6, 8, 10); (8, 15, 17); (9, 12, 15); (12, 16, 20)]