quicksort [] = []
quicksort (x:xs) = quicksort [y | y <- xs, y<x]
++ [x]
++ quicksort [y | y <- xs, y>=x]
- 見慣れないシンボルが多いので備忘録
- "x:xs"
- これは、x1という要素と、[x2,x3,...,xn]というリストからできた[x1,x2,x3,...,xn]という意味
- どうしてそうなるか、というと、":"が ２つの引数（要素と、その要素と同じ型の要素が作るリスト)を取って、第１引数である要素を頭に付け加えた、１要素多いリストを返す、という関数であるから
- このような関数を、シンボル":"を使わずに言うと"cons"という。LISPではごく普通の関数だという
- (x:xs)
- (x:xs)は[x1,x2,x3,...,xn]というリストである
- n=0でもよいので、最短の場合は、[x1]という要素数１のリストである
- これは、quicksort関数の「１つの引数」
- quicksort関数は、長さが１以上のリストを引数として取って、その先頭の要素xとxを除いたリストxsとを使って、処理をする関数だ、と言っている
- 「手続き式の言語」だと、zというリストを引数として与えて、その第１要素z[1]なと、残りz[2:n]とを指定して処理をする、というように書くが、cons (":")関数を使って、引数自体を「分解のやり方を指定して渡す」というやり方をとっていることがわかる
- [y | y <-xs, y
というように数学で書けば、「yはXの要素であって、かつxより大であるものを要素とする集合」となる- ここではxsが(x:xs)というベクトル(x1,x2,x3,...,xn)の第2-n要素のベクトル(x2,x3,...,xn)であって、xは先頭要素x1であるように指定してある
