chr1, chr2, ..., chr22, chrX, chrY という文字列のリスト^[A]があるとき，この順番は自然な並びになっています。しかし普通に文字列としてソートすると， chr1, chr10, chr11, ... という並びになってしまいます。前者のように数字を数値として比較した場合のソートを自然順ソートなどと呼びます。

F# で自然順ソートを実装してみます。

まずはじめに，文字列を文字のブロックと数字のブロックに分解します。

type Token =
   | String of string
   | Number of string

let rec span predicate = function
   | [] -> [], []
   | x :: xs when predicate x -> let matched, rest = span predicate xs in x :: matched, rest
   | list -> [], list

let isDigit c = System.Char.IsDigit (c)
let compareTokenType c1 c2 =  isDigit c1 = isDigit c2

let tokenize s =
   let rec loop = function
      | [] -> []
      | x :: xs ->
         let ys, zs = span (compareTokenType x) xs
         let token =
            let token = System.String (List.toArray <| x :: ys)
            if isDigit x then Number token else String token
         token :: loop zs
   loop (List.ofSeq s)

span は，リストの各要素に対して predicate の返す bool 値でグルーピングを行い，グループの境界でリストをわける (takeWhile の結果とその残りをタプルで得る) 関数です。たとえばリスト [0; 2; 1; 3; 4] に対して predicate を fun n -> n % 2 = 0 とすれば， [true; true; false; false; true] になるので，結果は [[0; 2]; [1; 3; 4]] となります。これを繰り返し用いて文字列中の各文字が数字か数字以外かで分類し，文字のブロックと数字のブロックに分解しています。

分解したら，先頭からブロック単位で比較していけば，自然な比較になります。

let parseNumber s = System.Numerics.BigInteger.Parse (s)

let naturalCompare (x : string) (y : string) =
   let rec loop = function
      | [], [] -> 0
      | [], _ -> -1
      | _, [] -> 1
      | Number left :: _, String right :: _
      | String left :: _, Number right :: _ -> compare left right
      | String s1 :: r1, String s2 :: r2 ->
         let c = compare s1 s2
         if c = 0 then loop (r1, r2) else c
      | Number n1 :: r1, Number n2 :: r2 ->
         let numericComparison = compare (parseNumber n1) (parseNumber n2)
         if numericComparison = 0 then
            let stringComparison = compare n1 n2
            if stringComparison = 0 then loop (r1, r2) else stringComparison
         else
            numericComparison
   loop (tokenize x, tokenize y)

naturalCompare は 2 つの文字列を比較して，自然な順番での比較を行います。 Number 同士の比較で数値が等しいときに文字列として比較するのは，数値としては同じだけど文字列として異なる値 (例えば 01 と 0001) を区別するための処理です。

naturalCompare 関数より自然な比較が可能になりました。あとは sortWith に部分適用してやれば，自然順ソートが可能になります^[B]。

let naturalSort = List.sortWith naturalCompare

最初の例で試すと，期待通りの結果になります。

履歴

• [2013-05-21 20:50] span の説明が誤っていたのを修正。

脚注

1. UCSC Genome Browser で使われている (ヒト) 染色体の名前。 [↩]
2. Seq.sortWith がないのが残念です。 [↩]