JSでクイックソートを書いてみる

📅 November 28, 2020

•

⏱️3 min read

こんちは！テストコードを書く書く詐欺おじさんです。

関数型プログラミングなるものを勉強したく、すごいHaskellたのしく学ぼう！ | ＭｉｒａｎＬｉｐｏｖａｃａ, 田中英行, 村主崇行 | 工学 | 本 | Amazon通称「すごいH本」を読み始めました。

アラビア語を読んでるのではないか？と思うくらい、わかりません。新しい言語を初めて触るときなんて、そんなもんだと割り切って気長に読み進めようと思います。

「再帰」の章が結構感動的だったので、メモ書きです。

Haskellでクイックソートを実装すると

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = 
  let smallerOrEqual = [a | a <- xs, a <= x]
      larger = [a | a <- xs, a > x]
      in quicksort smallerOrEqual ++ [x] ++ quicksort larger

こんな感じになるそうです。 1行目は、型の宣言です。aというOrd型（大小比較できるやつら）の配列を受け取って、同じ型の配列を返すよ。って宣言です。

2行目以降でパターンマッチを使ってるそうです。quicksort関数に、空配列が来た場合は、から配列を返して関数から抜けます。

3行目に到達するのは、引数が空配列以外のときです。 (x:xs) headとtailに分けています。JSでいう分割代入的な感じです。引数が[1,2,3]の場合は x = 1 xs=[2,3] になります。

[a | a <- xs, a <= x] はリスト内包表記と言うそうです。JSで言うmapとかfilterの親戚だと思われます。

xsの配列の値を先頭から1つずつaに代入して、　a <= x のとき、smallerOrEqualリストに追加するって感じです。

largerもリスト内包表記です。

in で再帰的にquicksortを呼び出して、最終的に、リストにまとめて返してます。

JSでクイックソートを書く

Haskellを勉強しだしたそもそもの目的は、いい感じのバグらないテストしやすいJSを書きたいってのがモチベーションなので、JSで書き直してみます!!

const quickSort = (arr: number[]): number[] => {
  if (arr.length === 0) return []
  const tail = arr.slice(1)
  const smallerOrEqual = tail.filter(v => v <= arr[0]) 
  const larger = tail.filter(v => v > arr[0])
  return [...quickSort(smallerOrEqual), arr[0], ...quickSort(larger)]
}

(あ。JSと言いつつTSです。ごめんなさい）

リスト内包表記とかJSにねーよって、ことでfilter使ってます。

感想

再帰的っていう凄いやつ（色んな意味で）がいるらしいというのは、前から知ってたのですが、まだ再帰的な関数に慣れてないせいか、再帰を見てると脳がバグりそうになります。

あと、Haskellでアルゴリズム勉強して、JSに書き直すっていうの結構楽しいので、ただH本写経するだけじゃんくて、Haskell -> JSの人間トランスコンパイラを目指そうと思います。

← Prev Next →