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