Clojureでインサーションソート

例によってソート実装。これは面白かった。

とりあえず書いてみたのは以下のコード：

(defn insert [x sorted]
  (let [[heads tails] (split-with #(<= % x) sorted)]
    (concat heads [x] tails)))

(defn insertion-sort [xs]
  (loop [[head & tail :as unsorted]  xs
         sorted                      []]
    (if (empty? unsorted)
      sorted
      (recur tail (insert head sorted))))) 

だんだん構文がお馴染みのものになってきた。

しかし、このままだとn=1000くらいでもStack Overflowを起こす。loop/recur使ってるのにおかしいなあと悩んでいたのだが、StackOverflowに答えがあった。

stackoverflow.com

この質問だとfilterが理由になっているが、私のコードだとinsert内のconcatが曲者である。

これをdoallで囲んでみる：

(defn insert [x sorted]
  (let [[heads tails] (split-with #(<= % x) sorted)]
    (doall (concat heads [x] tails))))

(defn insertion-sort [xs]
  (loop [[head & tail :as unsorted]  xs
         sorted                      []]
    (if (empty? unsorted)
      sorted
      (recur tail (insert head sorted))))) 

これならn=10000でも問題なく走る。毎回split-withしてるからそこで前回のconcatを評価しているのかと思ったのだが、Stack Overflow起こしているということはそもそもsplit-withも遅延評価なんだろう。遅延評価は便利なところではとことん便利、気をつけないと思わぬところでハマる。

ちなみにアルゴリズムの方はロジック上O(n²)なのでやっぱり遅い。