トポロジカルソートをF#で実装

topological-sort.fsx

// https://programmingpraxis.com/2010/11/19/topological-sort/
// 上記ページ記載のアルゴリズムを末尾再帰化、効率向上、閉路存在時の例外追加

let topologicalSort edges =
  let rec loop removed isolated = function
    | [] -> List.rev removed @ Set.toList isolated
    | edges ->
      let src, dst = edges |> List.unzip
      let dstSet = set dst
      let noIncomingVertex =
        src |> List.tryFind (fun s -> Set.contains s dstSet |> not) |> Option.defaultWith (fun() ->
          invalidArg $"{nameof edges}" $"""閉路が存在します:{edges |> Seq.map string |> String.concat ","}""")
      let nextRemoved = noIncomingVertex::removed
      let nextIsolated = Set.remove noIncomingVertex isolated
      let nextEdges = edges |> List.filter (fst >> (<>) noIncomingVertex)
      loop nextRemoved nextIsolated nextEdges
  let dstSet = edges |> List.map snd |> set
  loop [] dstSet edges

let test() =
  topologicalSort [
    (5, 11)
    (11, 2); (11, 10); (11, 9)
    (7, 11); (7, 8)
    (8, 9)
    (3, 10); (3, 8)
  ]

let testCycle() =
  topologicalSort [
    (5, 11)
    (11, 2); (11, 10); (11, 9)
    (7, 11); (7, 8)
    (8, 9)
    (3, 10); (3, 8)
    (9, 3)
  ]

let test2() =
  topologicalSort [
    (11, 2); (11, 10); (11, 9)
  ]

> test();;
val it : int list = [5; 7; 11; 3; 8; 2; 9; 10]

> test2();;
val it : int list = [11; 2; 9; 10]

> testCycle();;
System.ArgumentException: 閉路が存在します:(8, 9),(3, 10),(3, 8),(9, 3) (Parameter 'edges')
   at FSI_0045.noIncomingVertex@318-20.Invoke(Unit unitVar0)
   at FSI_0045.loop@312-13[b](FSharpList`1 removed, FSharpSet`1 isolated, FSharpList`1 _arg1)
   at FSI_0045.topologicalSort[a](FSharpList`1 edges)
   at FSI_0046.testCycle()
   at <StartupCode$FSI_0049>.$FSI_0049.main@()
Stopped due to error