Jekyllを使ってgithub.ioで運用しようと考えてましたが、github.ioのJekyllではtags/categoriesがうまく使えず、断念しました。 そこで、Hugoを使うことにしました。デプロイ先はこれから決める予定です。記事だけはこちらに書いていく予定です。 とは言ってもリポジトリはプライベートだし、デプロイもしないのでどこにも公開されないわけですが。

dojo/fsharp/MyList/Program.fs at main · tk3/dojo

今日はmapとfilterそしてfoldを実装した。 foldができたということで、これまで実装したlength、sum、reverseをfoldを使い実装し直した。foldを使うとこれまでのコードが短く書けて、汎用性が高い関数であることが分かった。

例えば、foldを使うことで、次のコードが

let sum list =
    let rec loop acc currentList =
        match currentList with
        | Empty -> acc
        | Cons(x, tail) -> loop (acc + x) tail
    loop 0 list

次のように書ける。

fold (fun acc x -> acc + x) 0 list5

ただ、実装していて腑に落ちなかったことが一つ。F#の文法についてだ。

コンパイルNGのコード

110 let foldFilter f list =
111     let folded = fold (fun acc x ->
112         if f x then
113             Cons(x, acc)
114         else acc
115     ) Empty list
116
117     reverse folded

エラーメッセージはこちら

Program.fs(115,7): error FS0010: Unexpected identifier in binding. Expected incomplete structured construct at or before this point or other token.
Program.fs(111,5): error FS3118: Incomplete value or function definition. If this is in an expression, the body of the expression must be indented to the same column as the 'let' keyword.

コンパイルOKのコード

dojo/fsharp/MyList/Program.fs at main · tk3/dojo

F#でデータ構造を理解するためにリストを実装した。面白かった。

おおもとのデータ定義。 ConsはConstructの略語。お決まりの宣言みたい。Emptyはその名の通り、空を表すもの。‘Tは値。今回のコードではintを使っている。

type MyList<'T> =
    | Empty
    | Cons of 'T * MyList<'T>

実際にリストを表現すると、以下のようになる。マトリョーシカのような感じで、前の値を包み込むようになっている。

Cons (4, Cons (3, Cons (2, Cons (1, Empty))))

今回は、length・sum・Some・contains・reverseを書いてみた。リスト実装はもう少し深掘りする予定。

ちなみにlengthはこんな感じ。forループではなく再帰で書いている。 accとは「Accumulator（アキュムレータ）」の略で、累積した値を保持している。この場合は長さを保持している。 matchで条件分岐し、Emptyになったら終了。再帰は何となくこんな感じで書くのかという理解。まだ慣れていないけれど。

let length list =
    let rec loop acc currentList =
        match currentList with
        | Empty -> acc
        | Cons(_, tail) -> loop (acc + 1) tail
    loop 0 list

アルゴリズムやっていくぞの気持ち。 初歩的なアルゴリズムが載ってあり、視覚化して分かりやすそうな気がして買いました。まずはこちらを見ながら、F#で実装しようと思っています。

アルゴリズム図鑑 増補改訂版 絵で見てわかる33のアルゴリズム（石田 保輝 宮崎 修一）｜翔泳社の本

あとこちらも。

問題解決力を鍛える！アルゴリズムとデータ構造 | 書籍情報 | 株式会社 講談社サイエンティフィク

Kindle版がセールしていたので、追加で購入しました。サンプルコードはC++。CかJavaが良かったけれど、まぁいいでしょう。私はなぜかC++には苦手意識があります。

dojo/fsharp/MyList/Program.fs at main · tk3/dojo

今日は選択ソート。昨日よりはすんなり書けて満足。もっと短く書けそうだが、今の自分には無理そう。

open System

[<EntryPoint>]
let main arg =
    let rnd = Random()
    let randomArray = [| for i in 1 .. 10 -> rnd.Next(1, 101) |]

    for i = 0 to randomArray.Length - 1 do
        let mutable target = i 
        let mutable minVal = randomArray[i]
        for j = i to randomArray.Length - 1 do
            if minVal > randomArray[j] then
                minVal <- randomArray[j]
                target <- j

        let tmp = randomArray[i]
        randomArray[i] <- randomArray[target]
        randomArray[target] <- tmp

    printfn "%A" randomArray

    0