F#で Priority Queueを使う

概要

競技プログラミング的なものを解いているときに, 優先度付きキューを使いたくなることがあるのでそのメモ

コード

.NETの標準ライブラリには存在しないので F#向けのコレクションライブラリを nugetから取ってくる. fsxで書いている場合は以下のような行を足す. projectがある場合は dotnet add で依存関係を追加する

#r "nuget: FSharpx.Collections"

定義を見るとわかるが, キューの要素は comparison制約を満たす必要があり, System.IComparableを実装している必要がある. IComparableを実装する際は Equals, GetHashCodeも overrideする必要があるのでそれを行う.

以下に例を示す. 年齢順, 年齢が同じなら名前で並べるというもの. F#で独自の比較, 等価性のチェックを行う場合は該当の methodを override, 実装するだけでなく属性も指定する必要があるようである.

open FSharpx.Collections

[<CustomEquality; CustomComparison>]
type PersonData =
    { Name: string
      Age: int }

    override this.GetHashCode() = hash this

    override this.Equals other =
        match other with
        | :? PersonData as o -> this.Name = o.Name && this.Age = o.Age
        | _ -> false

    interface System.IComparable with
        member this.CompareTo other =
            match other with
            | :? PersonData as o ->
                if this.Age <> o.Age then
                    compare this.Age o.Age
                else
                    compare this.Name o.Name
            | _ -> failwith "cannot compare with different object"

全体の例は以下の通り.

#r "nuget: FSharpx.Collections"

open FSharpx.Collections

[<CustomEquality; CustomComparison>]
type PersonData =
    { Name: string
      Age: int }

    override this.GetHashCode() = hash this

    override this.Equals other =
        match other with
        | :? PersonData as o -> this.Name = o.Name && this.Age = o.Age
        | _ -> false

    interface System.IComparable with
        member this.CompareTo other =
            match other with
            | :? PersonData as o ->
                if this.Age <> o.Age then
                    compare this.Age o.Age
                else
                    compare this.Name o.Name
            | _ -> failwith "cannot compare with different object"

let q =
    PriorityQueue.empty true
    |> PriorityQueue.insert { Name = "Alice"; Age = 42 }
    |> PriorityQueue.insert { Name = "Bob"; Age = 50 }
    |> PriorityQueue.insert { Name = "Chris"; Age = 18 }
    |> PriorityQueue.insert { Name = "David"; Age = 73 }
    |> PriorityQueue.insert { Name = "Elly"; Age = 33 }
    |> PriorityQueue.insert { Name = "Yoshida"; Age = 73 }

let (a, q1) = PriorityQueue.pop q
printfn "poped=%A" a // Yoshida

let (b, q2) = PriorityQueue.pop q1
printfn "poped=%A" b // David

let (c, q3) = PriorityQueue.pop q2
printfn "poped=%A" c // Bob

let (d, q4) = PriorityQueue.pop q3
printfn "poped=%A" d // Alice

let (e, q5) = PriorityQueue.pop q4
printfn "poped=%A" e // Elly

let (f, _) = PriorityQueue.pop q5
printfn "poped=%A" f // Chris