Haskellで学ぶF#入門

Haskellと比較しながらF#を説明します。練習では再帰に慣れることに重点を置きます。再帰によるリスト処理の例として各種ソート（挿入ソート、バブルソート、マージソート、クイックソート）を紹介します。

※ 一応、Haskellは飛ばしてF#だけでも読めるようには配慮したつもりです。Haskellがよく分からなければ飛ばして読んでみてください。

この記事はHaskellの記事をベースにしています。

• Haskell 超入門 2014.08.20

練習の解答例は別記事に掲載します。

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

この記事には姉妹編があります。

• C#/JavaScriptで学ぶF#入門 2017.01.04

この記事には関連記事があります。

• doブロックとコンピュテーション式 2016.07.01
• functionのインデント 2016.12.14

F#を手っ取り早く試すために、私が常用している環境を紹介します。

• F#開発環境の紹介 2016.12.30

ハローワールド

Haskell	F#
main = do putStrLn "Hello, World!"	printfn "Hello, World!"
実行結果 Hello, World!	実行結果 Hello, World!

エントリーポイント

F#は処理をいきなり書き始めることができるため、mainは必須ではありません。もし必要であれば[<EntryPoint>]属性を添えて関数を書きます。関数名は任意でmainでなくても構いませんが、引数と戻り値は必須です。C言語と比較します。

C言語	F#
#include <stdio.h> int main(int argc, char *argv[]) { printf("Hello, World!\n"); return 0; }	[<EntryPoint>] let main args = printfn "Hello, World!" 0
実行結果 Hello, World!	実行結果 Hello, World!

F#は[<EntryPoint>]にdoブロックを組み合わせることで、引数や戻り値が省略可能です。

F#

[<EntryPoint>]
do
    printfn "Hello, World!"

実行結果

Hello, World!

簡単のため、以後の例ではエントリーポイントなしで処理を書きます。

do

Haskellはdoブロック内では文法が変わりますが、F#のdoではそういったことはありません。F#のdoはC言語などの{}と同じようにブロックを表します。

F#でHaskellのdoブロックに相当するのはコンピュテーション式です。詳細は次の記事を参照してください。

• doブロックとコンピュテーション式 2016.07.01

Haskellでは連続出力にdoが必須ですが、F#ではそういった制約はありません。

Haskell	F#
main = do putStrLn "Hello, World!" putStrLn "Hello, World!"	printfn "Hello, World!" printfn "Hello, World!"
実行結果 Hello, World! Hello, World!	実行結果 Hello, World! Hello, World!

printf

HaskellのprintはShowのインスタンスを受け付けます。F#ではフォーマットに%Aを指定すれば任意の型を受け付けます。

Haskell	F#
main = do print 1 print "abc"	printfn "%A" 1 printfn "%A" "abc"
実行結果 1 "abc"	実行結果 1 "abc"

F#では%dなどの型に紐付けられたフォーマットを指定すればコンパイラで型がチェックされるため、フォーマットでサポートされている型は個別に指定した方が無難です。

束縛

F#の変数（識別子）は後で別の値を再代入することができません。そのため代入ではなく束縛という用語を使います。

let

F#ではトップレベルやローカルの区別なく、束縛には常にletが必要です。

※ Haskellのwhereに相当するキーワードはありません。

Haskell	F#
a = 1 b = 2 main = do let c = a + b print c	let a = 1 let b = 2 do let c = a + b printfn "%d" c
実行結果 3	実行結果 3

関数

数学の $f(x)=x+1$ や $f(1)$ の括弧がない版だとイメージしてください。C言語のreturnに相当するキーワードは使いません。

※ returnは存在しますが別の意味です。詳細はdoブロックとコンピュテーション式を参照してください。

Haskell	F#
f x = x + 1 a = f 1 main = do print a	let f x = x + 1 let a = f 1 printfn "%d" a
実行結果 2	実行結果 2

aを経由せずにprintfnに直接f 1を渡すには、括弧で囲みます。

Haskell	F#
f x = x + 1 main = do print (f 1)	let f x = x + 1 printfn "%d" (f 1)
実行結果 2	実行結果 2

パイプライン演算子

閉じ括弧の省略にはパイプライン演算子<|が使えます。

Haskell	F#
main = do print (f 1) print $ f 1	printfn "%d" (f 1) printfn "%d" <| f 1

連続で使用した場合、<|はHaskellの$とは挙動が異なるので注意が必要です。F#でHaskellの挙動を真似するには<<による関数合成と併用する必要があります。対応を示します。

Haskell	F#
main = do print $ abs $ 3 - 5 let a = atan2 (sqrt 2) (sqrt 3) print a	printfn "%d" << abs <| 3 - 5 let a = atan2 <| sqrt 2. <| sqrt 3. printfn "%f" a
実行結果 2 0.684719203002283	実行結果 2 0.684719

逆向きの |> もあります。連続して使用すれば、関数の多重ネストをシェルのパイプのように記述できます。

F#

printfn "%d" (abs (3 - 5))
3 - 5 |> abs |> printfn "%d"

実行結果

2
2

関数の演算子化

F#ではHaskellのように関数を演算子として使うことはできません。

Haskell

add x y = x + y

main = do
    print $ add 1 2
    print $ 1 `add` 2  -- 関数の演算子化

実行結果

3
3

演算子の関数化

中置演算子を()で囲むと関数として使用できます。

Haskell	F#
main = do print $ 1 + 2 print $ (+) 1 2	printfn "%d" <| 1 + 2 printfn "%d" <| (+) 1 2
実行結果 3 3	実行結果 3 3

四則演算

F#で割り算で小数点以下を扱う場合は、オペランドを明示的に浮動小数点数で記述します。Haskellのような / と div の区別はありません。

Haskell	F#
main = do print $ 5 + 2 print $ 5 - 2 print $ 5 * 2 print $ 5 / 2 print $ div 5 2 print $ mod 5 2 print $ 5 `div` 2 print $ 5 `mod` 2	printfn "%d" <| 5 + 2 printfn "%d" <| 5 - 2 printfn "%d" <| 5 * 2 printfn "%f" <| 5. / 2. printfn "%d" <| (/) 5 2 printfn "%d" <| (%) 5 2 printfn "%d" <| 5 / 2 printfn "%d" <| 5 % 2
実行結果 7 3 10 2.5 2 1 2 1	実行結果 7 3 10 2.500000 2 1 2 1

命名規則

Haskellとは異なり変数や関数を大文字で始めてもエラーにはなりませんが、慣習的に小文字で始めます。

if - then - else

まず、一行で書いてみます。

Haskell	F#
a = 1 main = do if a == 1 then print "1" else print "?"	let a = 1 if a = 1 then printfn "1" else printfn "?"
実行結果 "1"	実行結果 1

※ 「等しい」は=、「等しくない」は<>です。

複数行で書く場合のインデントにはある程度のバリエーションがありますが、よく使われるパターンを示します。

Haskell	F#
a = 1 main = do if a == 1 then print "1" else print "?"	let a = 1 if a = 1 then printfn "1" else printfn "?"
実行結果 "1"	実行結果 1

※ F#のelseはインデントで特別なルールがありますが、書き方が複数あると混乱するため説明を省略します。

値を返す

ifは値を返すため、C言語の三項演算子のように使えます。

Haskell	F#
a = 1 main = do print $ if a == 1 then "1" else "?"	let a = 1 printfn "%s" <| if a = 1 then "1" else "?"
実行結果 "1"	実行結果 1

関数の定義と組み合わせた例です。

Haskell	F#
f a = if a == 1 then "1" else "?" main = do print $ f 0 print $ f 1	let f a = if a = 1 then "1" else "?" printfn "%s" <| f 0 printfn "%s" <| f 1
実行結果 "?" "1"	実行結果 ? 1

関数のパターンマッチ

関数内の全体をifで切り分ける代わりに、functionキーワードで引数を振り分けられます。このような書き方をパターンマッチと呼びます。

※ Haskellのように関数を複数定義するような形にはしません。

Haskell	F#
f 1 = "1" f a = "?" main = do print $ f 0 print $ f 1	let f = function | 1 -> "1" | a -> "?" printfn "%s" <| f 0 printfn "%s" <| f 1
実行結果 "?" "1"	実行結果 ? 1

値を無視する引数は_と書くことで、値を無視していることを明示します。

Haskell	F#
f 1 = "1" f _ = "?"	let f = function | 1 -> "1" | _ -> "?"

これは独特な書き方のため、慣れが必要です。

階乗

例としてよく引き合いに出されます。

Haskell	F#
fact 0 = 1 fact n = n * fact (n - 1) main = do print $ fact 5	let rec fact = function | 0 -> 1 | n -> n * fact (n - 1) printfn "%d" <| fact 5
実行結果 120	実行結果 120

factの中でfactを呼んでいます。このような流れを再帰と言います。再帰関数にはrecキーワードを付けます。recを付けなければ自分が参照できずにエラーになります。

※ デフォルトで再帰可能になっていないのは、同名の変数で覆い隠すシャドウイングを考慮した言語設計のようです。F#の元になったOCamlについての記事を紹介します。

• @camlspotter: OCaml の let と let rec はなぜ別扱いになっているのか、決定版、もしくは OCaml 暦十何年だったか忘れたけど仕事で Haskell を一年使ってみた - Oh, you `re no (fun _ → more) 2011.05.09

再帰は往復で処理されるため往路と復路に分けて考えます。

再帰の往路をトレースします。

1. | 5 -> 5 * fact 4
2. | 4 -> 4 * fact 3
3. | 3 -> 3 * fact 2
4. | 2 -> 2 * fact 1
5. | 1 -> 1 * fact 0
6. | 0 -> 1

| 0 -> 1が折り返し点となり、反転して復路に入ります。

1. | 1 -> 1 * fact 0 = 1 * 1 = 1
2. | 2 -> 2 * fact 1 = 2 * 1 = 2
3. | 3 -> 3 * fact 2 = 3 * 2 = 6
4. | 4 -> 4 * fact 3 = 4 * 6 = 24
5. | 5 -> 5 * fact 4 = 5 * 24 = 120

※ 往路だけで復路のない末尾再帰もありますが、今回の範囲を超えるため省略します。

簡約

往路をインライン展開すると次のように捉えることができます。

1. fact 5
2. 5 * fact 4
3. 5 * 4 * fact 3
4. 5 * 4 * 3 * fact 2
5. 5 * 4 * 3 * 2 * fact 1
6. 5 * 4 * 3 * 2 * 1 * fact 0
7. 5 * 4 * 3 * 2 * 1 * 1
8. 120

このような式変形を簡約と呼びます。

基底部・再帰部

折り返し点となる定義を基底部、自分自身を呼び出している定義を再帰部と呼びます。

• 基底部: | 0 -> 1
• 再帰部: | n -> n * fact (n - 1)

コツ

再帰の取り扱いにはパターンがあります。そこを意識するのがコツです。

作り方のコツ

1. 基底部を定義
2. 具体例に当てはめて一般化する

まず基底部を定義します。自然数を指定するタイプでは値が減少しながら再帰を繰り返すのが定石で、これ以上減少できない最小値が基底部となります。

階乗について考えます。マイナスの階乗が定義されていないため、計算可能な最小の階乗は $0!$ です。このことから基底部を定義します。

基底部

let rec fact = function
| 0 -> 1

再帰部は具体例を通して考えるのがコツです。たとえば5の階乗を考えます。

具体例

5! = 5 × 4 × 3 × 2 × 1

再帰は引数を5から0に向かって減少させて処理します。1つ小さい引数（この場合は4）の結果を利用するのが定石です。このパターンで表すため、5の階乗を4の階乗で表せないか考えます。

式変形

5! = 5 × (4 × 3 × 2 × 1) = 5 × 4!

特定の数（この場合は5）での関係が得られました。これを一般化して5を$n$に置き換えます。4は$n-1$です。このように隣接する項目との関係で表された式を漸化式と呼びます。

漸化式

n! = n × (n-1)!

漸化式をコード化すれば再帰部が得られます。

fact再帰部

| n -> n * fact (n - 1)

このように基底部と再帰部は順を追って別々に作ることになるため、パターンマッチで分岐する書き方と相性が良いです。

※ 数学の問題であれば得られた式を数学的帰納法で証明することが求められますが、今回はプログラミングの練習が目的なので、いくつか具体例で動作確認して済ませます。

確認のコツ

一旦書き上げたプログラムを確認するコツです。既存のコードを読むときにも使えます。

再帰の流れは追わずに、結果が信頼できるものと見なして具体例で考えます。

fact再帰部

| n -> n * fact (n - 1)

1. | 5 -> 5 * fact 4
2. fact 4は定義より4! = 24が返されると考えます。
3. 5 * 24 = 120

次に再帰を使った練習問題をやるので、この方法を試してみてください。

練習

フィボナッチ数は0, 1が初期値として与えられ、それ以降は前2つの数字を合計して得られる数列です。

• 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

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

ヒント: 基底部は1つとは限りません。

⇒ 解答例

ガード

パターンマッチにwhenで条件を付加するガードという書き方があります。

上で実装したfactに負の数を渡すと無限ループになります。対策としてガードを追加して引数を制限します。

※ マイナスの階乗は数学的に定義されていないので、弾いても問題ありません。

Haskell	F#
fact 0 = 1 fact n | n > 0 = n * fact (n - 1) main = do print $ fact 5	let rec fact = function | 0 -> 1 | n when n > 0 -> n * fact (n - 1) printfn "%d" <| fact 5
実行結果 120	実行結果 120

例外

先ほどのコードは Imcomplete patter matches と警告されます。マイナスのときの処理が抜けているためです。

警告を消すため、残り全部の意味で _で受けてfailwithで例外を発生させます。

F#

let rec fact = function
| 0 -> 1
| n when n > 0 -> n * fact (n - 1)
| _ -> failwith "< 0"

※ Haskellでは例外を使用するには構造を変える必要があるため、対応コードは省略します。Haskellで例外を使わずに処理する方法についてはHaskell Maybeモナド 超入門を参照してください。

練習

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

⇒ 解答例

match

関数の中でパターンマッチを行うには match - with を使います。

※ Haskellとは異なり、F#ではfunctionもmatchも->を使います。

Haskell	F#
fact n = case n of 0 -> 1 _ | n > 0 -> n * fact (n - 1) main = do print $ fact 5	let rec fact n = match n with | 0 -> 1 | _ when n > 0 -> n * fact (n - 1) | _ -> failwith "< 0" printfn "%d" <| fact 5
実行結果 120	実行結果 120

※ 引数でnとして受けているため、match中のパターンマッチでは_として受け流しています。

functionは関数レベルの分岐のためインデントしませんでしたが、matchは関数の中のためインデントが必須です。詳細は次の記事を参照してください。

• functionのインデント 2016.12.14

練習

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

⇒ 解答例

リスト

他言語の配列と似たようなものです。F#では要素は ; で区切ります。慣れるまで間違えやすいので注意してください。

※ F#では , で区切ると意味が変わり、大抵の場合はエラーとなります。

Haskell	F#
main = do print [1, 2, 3, 4, 5]	printfn "%A" [1; 2; 3; 4; 5]
実行結果 [1,2,3,4,5]	実行結果 [1; 2; 3; 4; 5]

※ F#ではリストとは別に配列もあります。今回はリストの使い方に慣れることを目的とするため、配列については省略します。

要素は改行によっても区切られます。実際には改行の方が基本で、改行せずに区切るのが ; です。

F#

printfn "%A" [
    1
    2
    3
    4
    5]

実行結果

[1; 2; 3; 4; 5]

要素の取り出し

リストから要素を取り出すには.[]を使います。先頭の要素は0番目です。

※ 他の言語に慣れていると . が異様に映りますが、[]もオブジェクトのメソッドだということを示しています。

Haskell	F#
main = do print $ [1, 2, 3, 4, 5] !! 3	printfn "%d" [1; 2; 3; 4; 5].[3]
実行結果 4	実行結果 4

連番

連番リストを生成する専用の書き方があります。

Haskell	F#
main = do print [1..5]	printfn "%A" [1..5]
実行結果 [1,2,3,4,5]	実行結果 [1; 2; 3; 4; 5]

連結

@によりリスト同士を結合できます。

Haskell	F#
main = do print $ [1, 2, 3] ++ [4, 5]	printfn "%A" <| [1; 2; 3] @ [4; 5]
実行結果 [1,2,3,4,5]	実行結果 [1; 2; 3; 4; 5]

::

::によりリストの先頭に要素を挿入できます。

※ Haskellとは:と::の意味が逆なのに注意が必要です。

Haskell	F#
main = do print $ 1:[2..5]	printfn "%A" <| 1::[2..5]
実行結果 [1,2,3,4,5]	実行結果 [1; 2; 3; 4; 5]

複数の先頭要素を連ねることもできます。

Haskell	F#
main = do print $ 1:2:[3..5]	printfn "%A" <| 1::2::[3..5]
実行結果 [1,2,3,4,5]	実行結果 [1; 2; 3; 4; 5]

::では末尾に追加できないため@を使用します。

Haskell	F#
main = do print $ [1..4] ++ [5]	printfn "%A" <| [1..4] @ [5]
実行結果 [1,2,3,4,5]	実行結果 [1; 2; 3; 4; 5]

文字列

Haskellでは文字列は文字のリストとして扱われますが、F#では別物です。文字列の連結は+で、@や::は使えません。

F#で文字列をリストに変換するにはList.ofSeqを使用します。

Haskell	F#
main = do print $ "abcde" print $ ['a', 'b', 'c', 'd', 'e'] print $ ['a'..'e'] print $ 'a':"bcde" print $ 'a':'b':"cde" print $ "abc" ++ "de" print $ "abcde" !! 3	printfn "%A" <| "abcde" printfn "%A" <| ['a'; 'b'; 'c'; 'd'; 'e'] printfn "%A" <| ['a'..'e'] printfn "%A" <| 'a'::List.ofSeq "bcde" printfn "%A" <| 'a'::'b'::List.ofSeq "cde" printfn "%A" <| "abc" + "de" printfn "%A" <| "abcde".[3]
実行結果 "abcde" "abcde" "abcde" "abcde" "abcde" "abcde" 'd'	実行結果 "abcde" ['a'; 'b'; 'c'; 'd'; 'e'] ['a'; 'b'; 'c'; 'd'; 'e'] ['a'; 'b'; 'c'; 'd'; 'e'] ['a'; 'b'; 'c'; 'd'; 'e'] "abcde" 'd'

文字のリストから文字列への変換は次のようにします。

F#

let a = ['a'..'f']
let s = Array.ofList a |> System.String.Concat
printfn "%A -> %A" a s

実行結果

['a'; 'b'; 'c'; 'd'; 'e'; 'f'] -> "abcdef"

パターンマッチ

パターンマッチでリストの先頭要素を取り出せます。

Haskell	F#
first (x:xs) = x main = do print $ first [1..5] print $ first "abcdef"	let first = function | x::xs -> x | _ -> failwith "empty" printfn "%A" <| first [1..5] printfn "%A" <| first (List.ofSeq "abcdef")
実行結果 1 'a'	実行結果 1 'a'

x::xsで先頭xとその後ろのリストxsに分割して受け取ります。xsはxの複数形を意図しています。これらの名前には文法的な意味はなく、あくまで慣習です。

この例ではxsを使っていないため_で未使用を明示した方が無難です。

Haskell	F#
first (x:_) = x	| x::_ -> x

先頭要素は複数を連ねることもできます。

Haskell	F#
second (_:x:_) = x main = do print $ second [1..5] print $ second "abcdef"	let second = function | _::x::_ -> x | _ -> failwith "too short" printfn "%A" <| second [1..5] printfn "%A" <| second (List.ofSeq "abcdef")
実行結果 2 'b'	実行結果 2 'b'

リスト関係の関数

F#ではListのメソッドという扱いです（List.ofSeq など）。

List.は省略できません。これは冗長な印象を受けますが、いくつかメリットがあります。

• F#では型推論を優先する言語設計のため、関数のオーバーロードができません。モジュールのメソッドであれば、配列・リスト・シーケンスなど互換性のない型に対して、同じ名前のメソッドが提供できます。
• インテリセンスのサポートがある環境では、List.と打てばメソッド名の候補が補完されます。

length

リストの要素数を取得します。

Haskell	F#
main = do print $ length [1, 2, 3]	printfn "%d" <| List.length [1; 2; 3]
実行結果 3	実行結果 3

sum

リストの要素をすべて足します。

Haskell	F#
main = do print $ sum [1..5]	printfn "%d" <| List.sum [1..5]
実行結果 15	実行結果 15

rev

リストの要素を逆に並べます。

Haskell	F#
main = do print $ reverse [1..5]	printfn "%A" <| List.rev [1..5]
実行結果 [5,4,3,2,1]	実行結果 [5; 4; 3; 2; 1]

練習

lengthと同じ機能の関数を再実装する例です。

F#

let rec length = function
| []    -> 0
| _::xs -> 1 + length xs

printfn "%d" <| length [1; 2; 3]

実行結果

3

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

ヒント: リストを再帰で処理するパターンは| x::xs -> x ... f xsです。

⇒ 解答例

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

⇒ 解答例

タプル

関数で複数の値を返すことができます。括弧で複数の値を囲んだ部分をタプルと呼びます。

※ F#ではタプルの括弧を省略できますが、この記事では混乱を避けるため省略しません。

Haskell	F#
addsub x y = (x + y, x - y) main = do print $ addsub 1 2	let addsub x y = (x + y, x - y) printfn "%A" <| addsub 1 2
実行結果 (3,-1)	実行結果 (3, -1)

タプルは全体でも分割でも受け取れます。

Haskell	F#
addsub x y = (x + y, x - y) a = addsub 1 2 (a1, a2) = addsub 1 2 main = do print a print a1 print a2	let addsub x y = (x + y, x - y) let a = addsub 1 2 let (a1, a2) = addsub 1 2 printfn "%A" a printfn "%d" a1 printfn "%d" a2
実行結果 (3,-1) 3 -1	実行結果 (3, -1) 3 -1

数学の座標をイメージすると良いでしょう。

• $P=(1,2)$
• $(x,y)=(1,2)$ ⇔ $x=1,y=2$

リストとの比較

• リストの項目数は任意ですが、タプルでは固定です。
• リストの要素はすべて同じ型でないといけませんが、タプルでは任意です。
  • × [1; "a"]
  • ○ (1, "a")

関数

要素が2つのタプルから値を取り出す関数fst, sndがあります。

Haskell	F#
main = do let p2 = (1, 2) print $ fst p2 print $ snd p2	let p2 = (1, 2) printfn "%d" <| fst p2 printfn "%d" <| snd p2
実行結果 1 2	実行結果 1 2

要素が3つ以上のタプルからは変数経由で値を取り出します。

Haskell	F#
main = do let p3 = (1, 2, 3) print p3 let (_, _, p3z) = p3 print p3z	let p3 = (1, 2, 3) printfn "%A" p3 let (_, _, p3z) = p3 printfn "%d" p3z
実行結果 (1,2,3) 3	実行結果 (1, 2, 3) 3

※ リストのように.[]で値を取り出すことはできません。

練習

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

具体的には次のコードが動くようにしてください。0.などは浮動小数点数（float）のリテラルです。

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

実行結果

(1.0, 1.0)

ヒント: $ax + by = c$ の傾きは $-\frac{a}{b}$ です。直交する直線の傾きとの積が $-1$ となることから、垂線は $bx - ay = d$ と表せます。連立方程式を解けば交点が求まります。

⇒ 解答例

キャスト

intなどの基本的な型は、型名を関数として扱うことでキャストできます。

キャストを使用して、文字コードを取得したり、文字コードを文字に変換したりする例です。

※ Haskellでは専用の関数をインポートして使用します。

Haskell	F#
import Data.Char main = do print $ ord 'A' print $ chr 65	printfn "%d" <| int 'A' printfn "%c" <| char 65
実行結果 65 'A'	実行結果 65 A

練習

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

具体的には次のコードが動くようにしてください。

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

実行結果

Uryyb, Jbeyq!
Hello, World!

⇒ 解答例

ソート

挿入ソートの実装例を示します。

Haskell	F#
insert x [] = [x] insert x (y:ys) | x < y = x:y:ys | otherwise = y : insert x ys isort [] = [] isort (x:xs) = insert x (isort xs) main = do let t = [4, 6, 9, 8, 3, 5, 1, 7, 2] print $ isort t	let rec insert x = function | [] -> [x] | y::ys when x < y -> x::y::ys | y::ys -> y :: insert x ys let rec isort = function | [] -> [] | x::xs -> insert x (isort xs) let t = [4; 6; 9; 8; 3; 5; 1; 7; 2] printfn "%A" <| isort t
実行結果 [1,2,3,4,5,6,7,8,9]	実行結果 [1; 2; 3; 4; 5; 6; 7; 8; 9]

処理の流れを説明します。

F#

let rec isort = function
| [] -> []
| x::xs -> insert x (isort xs)

リストの先頭の要素を取り出しながら再帰することで、リストの要素を順番に挿入して行きます。

リスト[4; 6; 9; 8; 3; 5; 1; 7; 2]の往路をトレースします。

1. | [4; 6; 9; 8; 3; 5; 1; 7; 2] -> insert 4 (isort [6; 9; 8; 3; 5; 1; 7; 2])
2. | [6; 9; 8; 3; 5; 1; 7; 2] -> insert 6 (isort [9; 8; 3; 5; 1; 7; 2])
3. | [9; 8; 3; 5; 1; 7; 2] -> insert 9 (isort [8; 3; 5; 1; 7; 2])
4. | [8; 3; 5; 1; 7; 2] -> insert 8 (isort [3; 5; 1; 7; 2])
5. | [3; 5; 1; 7; 2] -> insert 3 (isort [5; 1; 7; 2])
6. | [5; 1; 7; 2] -> insert 5 (isort [1; 7; 2])
7. | [1; 7; 2] -> insert 1 (isort [7; 2])
8. | [7; 2] -> insert 7 (isort [2])
9. | [2] -> insert 2 (isort [])
10. | [] -> []

insertの第2引数は必ずisortでソートされたリストが渡されます。

挿入先のリストはソート済みであることを前提にできるため、挿入箇所の判定は後続要素との比較だけで済みます。

再帰により挿入先のリストの要素と順番に比較していきます。末尾に達するとys = []となるため、そこに挿入します。

F#

let rec insert x = function
| [] -> [x]
| y::ys when x < y -> x::y::ys
| y::ys -> y :: insert x ys

例を示します。

1. insert 3 [1; 2; 5; 7] 次へ
2. 1::insert 3 [2; 5; 7] 次へ
3. 1::2::insert 3 [5; 7] ここへ挿入
4. 1::2::3::[5; 7]
5. [1; 2; 3; 5; 7]

isortの復路をトレースします。

1. | [2] -> insert 2 []
2. | [7; 2] -> insert 7 [2]
3. | [1; 7; 2] -> insert 1 [2; 7]
4. | [5; 1; 7; 2] -> insert 5 [1; 2; 7]
5. | [3; 5; 1; 7; 2] -> insert 3 [1; 2; 5; 7]
6. | [8; 3; 5; 1; 7; 2] -> insert 8 [1; 2; 3; 5; 7]
7. | [9; 8; 3; 5; 1; 7; 2] -> insert 9 [1; 2; 3; 5; 7; 8]
8. | [6; 9; 8; 3; 5; 1; 7; 2] -> insert 6 [1; 2; 3; 5; 7; 8; 9]
9. | [4; 6; 9; 8; 3; 5; 1; 7; 2] -> insert 4 [1; 2; 3; 5; 6; 7; 8; 9]
10. [1; 2; 3; 4; 5; 6; 7; 8; 9]

このように要素を1つずつソートされたリストに挿入しています。

確認のコツ

再帰の確認のコツを説明しましたが、挿入ソートに適用してみます。具体例を使って、結果が信頼できるものと見なします。

isort再帰部

| x::xs -> insert x (isort xs)

1. | [3; 5; 1; 7; 2] -> insert 3 (isort [5; 1; 7; 2])
2. | [5; 1; 7; 2]は定義よりソート済みの[1; 2; 5; 7]が返されると考えます。
3. insert 3 [1; 2; 5; 7] = [1; 2; 3; 5; 7]

デバッグ

F#ではHaskellのように副作用の分離が強制されないため、通常のprintfデバッグが可能です。

挿入ソートをトレースしてみます。

F#

let rec insert x = function
| [] -> [x]
| y::ys when x < y -> x::y::ys
| y::ys -> y :: insert x ys

let rec isort = function
| [] -> []
| x::xs ->
    printfn "isort %A = insert %d (isort %A)" (x::xs) x xs
    let xs' = isort xs
    let ret = insert x xs'
    printfn "insert %d %A = %A" x xs' ret
    ret

let t = [4; 6; 9; 8; 3; 5; 1; 7; 2]
printfn "%A" <| isort t

実行結果

isort [4; 6; 9; 8; 3; 5; 1; 7; 2] = insert 4 (isort [6; 9; 8; 3; 5; 1; 7; 2])
isort [6; 9; 8; 3; 5; 1; 7; 2] = insert 6 (isort [9; 8; 3; 5; 1; 7; 2])
isort [9; 8; 3; 5; 1; 7; 2] = insert 9 (isort [8; 3; 5; 1; 7; 2])
isort [8; 3; 5; 1; 7; 2] = insert 8 (isort [3; 5; 1; 7; 2])
isort [3; 5; 1; 7; 2] = insert 3 (isort [5; 1; 7; 2])
isort [5; 1; 7; 2] = insert 5 (isort [1; 7; 2])
isort [1; 7; 2] = insert 1 (isort [7; 2])
isort [7; 2] = insert 7 (isort [2])
isort [2] = insert 2 (isort [])
insert 2 [] = [2]
insert 7 [2] = [2; 7]
insert 1 [2; 7] = [1; 2; 7]
insert 5 [1; 2; 7] = [1; 2; 5; 7]
insert 3 [1; 2; 5; 7] = [1; 2; 3; 5; 7]
insert 8 [1; 2; 3; 5; 7] = [1; 2; 3; 5; 7; 8]
insert 9 [1; 2; 3; 5; 7; 8] = [1; 2; 3; 5; 7; 8; 9]
insert 6 [1; 2; 3; 5; 7; 8; 9] = [1; 2; 3; 5; 6; 7; 8; 9]
insert 4 [1; 2; 3; 5; 6; 7; 8; 9] = [1; 2; 3; 4; 5; 6; 7; 8; 9]
[1; 2; 3; 4; 5; 6; 7; 8; 9]

printfnを2回使うことで、往路と復路が確認できるように表示しています。

練習

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

ヒント: 交換する関数とソートする関数を分離して実装します。

⇒ 詳細説明, 解答例

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

ヒント: リストを分割する関数を実装します。

⇒ 解答例

リスト内包表記

リストの要素すべてに同じ処理を施した別のリストを作成します。

Haskell	F#
fact 0 = 1 fact n | n > 0 = n * fact (n - 1) main = do print [1, 2, 3, 4, 5] print [fact 1, fact 2, fact 3, fact 4, fact 5] print [fact x | x <- [1..5]]	let rec fact = function | 0 -> 1 | n when n > 0 -> n * fact (n - 1) | _ -> failwith "< 0" printfn "%A" <| [1; 2; 3; 4; 5] printfn "%A" <| [fact 1; fact 2; fact 3; fact 4; fact 5] printfn "%A" <| [for x in 1..5 -> fact x]
実行結果 [1,2,3,4,5] [1,2,6,24,120] [1,2,6,24,120]	実行結果 [1; 2; 3; 4; 5] [1; 2; 6; 24; 120] [1; 2; 6; 24; 120]

1..5の要素を1つずつxとして取り出して、fact xとして処理したリストを作成しています。

※ 同じことができるmapという関数もありますが、詳細は省略します。

条件

要素を取り出す際に条件を指定する例を示します。

Haskell	F#
main = do print [x | x <- [1..9], x < 5]	printfn "%A" <| [for x in 1..9 do if x < 5 then yield x]
実行結果 [1,2,3,4]	実行結果 [1; 2; 3; 4]

1..9のうちx < 5を満たすものだけでリストを作成しています。

※ 同じことができるfilterという関数もありますが、詳細は省略します。

練習

Haskellの特徴を示す例として、クイックソートがよく引き合いに出されます。

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

main = do
    print $ qsort [4, 6, 9, 8, 3, 5, 1, 7, 2]

実行結果

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

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

⇒ 解答例

多重ループ

リスト内包表記で多重ループを使った例を示します。

複数のリストから値を取り出すこともできます。多重ループのようにすべての組み合わせが得られます。

Haskell	F#
main = do print [(x, y) | x <- [1..3], y <- "abc"]	printfn "%A" <| [ for x in 1..3 do for y in "abc" -> (x, y)]
実行結果 [(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c'), (3,'a'),(3,'b'),(3,'c')]	実行結果 [(1, 'a'); (1, 'b'); (1, 'c'); (2, 'a'); (2, 'b'); (2, 'c'); (3, 'a'); (3, 'b'); (3, 'c')]

練習

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

ヒント: 直角三角形の成立条件は三平方（ピタゴラス）の定理です。

⇒ 解答例