関数型思考モードの洗礼

前言

以下の文脈はすべて Haskell で、ループ構造はなく、再帰のみを使って宿題をします

一.再帰

まずシンプルな再帰問題から関数型言語の構文の魅力を感じましょう

配列中の最大要素を求めるには、こうできます：

-- if-else
maximum' xs = if null xs then error "Empty list"
  else if length xs == 1 then head xs
    else max (head xs) (maximum' (tail xs))

配列中の最大要素は先頭要素と残りの要素の最大値の二者のうちより大きい方です

あまり綺麗に見えないので、修正：

-- パターンマッチ
maximum'' [] = error "Empty list"
maximum'' (x:xs) = if null xs then x
  else max x (maximum' xs)

少し感覚がつかめてきました、さらに修正：

-- Guard
maximum''' [] = error "Empty list"
maximum''' (x:xs)
  | null xs = x
  | otherwise = max x (maximum''' xs)

guard に変えると if-else が消え、还不够清楚、さらに修正：

maximum'''' [] = error "Empty list"
maximum'''' [x] = x
maximum'''' (x:xs) = max x (maximum'''' xs)

これで意味が非常に自然になりました：

1.例外処理：空 List には最大値がない、エラー
2.境界条件：単要素 List の最大値はその要素
3.再帰定義：多要素 List の最大値は先頭要素と残り要素の最大値の間の大きい方

再帰アルゴリズム自体に強い記述性があり、パターンマッチと組み合わせることで意味をより明確自然にできます

二.関数型思考モード

よし、今私たちはループ文がない世界に投げ込まれました、再帰が唯一の道です

シンプルなシナリオ

まずシンプルな問題を考えましょう、length 関数を実装するには？List を入力し、その長力を出力

length :: Foldable t => t a -> Int

慣れ親しんだ命令型思考に従い、List を traverse してカウントすれば完了。では、どのように再帰で List の長さを記述するか（つまりその再帰定義を提供するか）？

length' [] = 0
length' (_:xs) = 1 + length' xs

非常に地道な書き方で、意味は以下の通り：

1.境界条件：空 List の長さは 0
2.再帰定義：空でない List の長さは 1 加える尾の長さ

何となくそんな感じです、再帰アルゴリズムは問題の解の再帰定義を与えることで、通常は出口、つまり境界条件を与える必要があります

問題自体が再帰定義されているものもあります、例えばフィボナッチ数列：

fib 0 = 0
fib 1 = 1
fib n
  | n < 0 = error "Negative n is invalid"
  | otherwise = fib (n - 1) + fib (n - 2)

一方、他の問題の再帰定義はそれほど明確ではありません、例えば上記の length 関数、どうやら一つずつ数える方が思考習慣に合っているようです、此时就需要给出其再帰定義、进而得出再帰アルゴリズム

P.S.出口を残さない死再帰もあります、例えば repeat 関数：

repeat' :: t -> [t]
repeat' x = x : (repeat' x)

長さを限定できれば、replicate 関数になります：

replicate' times x
  | times <= 0 = []
  | otherwise = x : (replicate' (times - 1) x)

あまりシンプルでないシナリオ

List 操作ではよく take 関数を使って List の最初の n 項を取り出します：

take :: Int -> [a] -> [a]

命令型スタイルなら、当然 traverse して最初の n 項を収集。しかし私たちは今関数型文脈にあり、どのデータ構造もコンテナとして使えず、置く場所がありません。だから結果は当然演算で拼凑された新しい List です：

take'' n xs
  | n <= 0 || null xs = []
  | otherwise = (head xs) : (take'' (n - 1) (tail xs))

意味は还算明確：

1.境界条件：最初の 0 項または空 List の take 結果は空 List
2.再帰定義：最初の n 項は先頭項並べる尾の最初の n-1 項

しかし書き方が还不够地道：

take' _ [] = []
take' n _
  | n <= 0 = []
take' n (x:xs) = x : take' (n - 1) xs

次に面白いシナリオを試しましょう、reverse 関数を実装：

reverse :: [a] -> [a]

今回は「破壊的な」List を作り出す必要があります、純粋なデータ構造操作：

reverse' xs
  | length xs <= 1 = xs
  | otherwise = last xs : (reverse' (init xs))

上記の関数は、List 反転結果は尾元並べる残り要素の反転結果と言います

もう一つデータ構造を操作するものを、例えば zip：

zip :: [a] -> [b] -> [(a, b)]

2 つの List を二元組 List に統合し、長い部分は切り落とします：

zip' [] _ = []
zip' _ [] = []
zip' (x:xs) (y:ys) = (x, y) : (zip' xs ys)

これは、2 つの List の統合結果は各自の先頭元で組成された二元組並べる残り部分の統合結果と言います

データ構造をいじる再帰はつまらなくなってきました、純粋な論理の を試しましょう、例えば elem 関数：

elem :: (Foldable t, Eq a) => a -> t a -> Bool

List が指定要素を含むかどうかをどのように判断するか？一つずつ比較：

elem'' _ [] = False
elem'' n (x:xs) = x == n || (elem'' n xs)

まず空 List には確かにない、空でない List に対して、先頭元をチェック、マッチしなければ残り要素をチェック。あまり再帰らしく聞こえない、言語を再編成：空でない List の包含性は先頭元の包含性或べる残り要素の包含性

コードも再編成、より地道なバージョン：

elem''' _ [] = False
elem''' n (x:xs)
  | x == n = True
  | otherwise = elem'' n xs

少し複雑なシナリオ

今回最初の小さな関門に直面しました、List 中の 2 つの要素を交換するには？

swap :: Int -> Int -> [a] -> [a]

知っている「套路」 を試しましょう：

t = a
a = b
b = t

これは関数型環境��は通じないようです、では他の方法はあるか？もちろんあります：

swap _ _ [] = []
swap i j xs
  | i == j = xs
  | i > j = swap j i xs
  | otherwise  = (take i xs) ++ [xs !! j] ++ (drop (i + 1) (take j xs)) ++ [xs !! i] ++ (drop (j + 1) xs)

上記の関数は、1 本の線が 2 つの点で 3 段に分けられ、List 中 2 つの要素交換の結果は第一段並べる 2 番目の点、並べる中間那段、再並べる 1 番目の点と最後一段と言います

もちろん、この問題は再帰とは関係なく、だから再帰が唯一の選択と言うのは traverse が必要なシナリオに対してで、すべての問題都得用这把锤子钉两下 ではありません

注意、その中の drop a (take b xs) は List 中索引が (a, b] の間の要素を取り出すのに使い、より地道な書き方は：

sublist _ _ [] = []
sublist a b xs
  | a > b = []
  | a == b = [xs !! a]
  | otherwise = (drop a . take (b + 1)) xs

だから修正後の swap はこうなります：

swap _ _ [] = []
swap i j xs
  | i == j = xs
  | i > j = swap j i xs
  | otherwise  = (take i xs) ++ [xs !! j] ++ (sublist (i + 1) (j - 1) xs) ++ [xs !! i] ++ (drop (j + 1) xs)
  where sublist _ _ [] = []
        sublist a b xs
          | a > b = []
          | a == b = [xs !! a]
          | otherwise = (drop a . take (b + 1)) xs

より強い表現力を追求するなら、残り頭尾 2 段も sublist に換えられます

P.S.関数型言語は小而美の組合せを追求するので、slice のようなものはなく、drop, take で組合せられるから、专门提供一个就显得多余了

複雑なシナリオ

クイックソートを知っていますね、書いてみましょう

クイックソートの核心思路 は：

男は左に立て、女は右に立て、先生は中に立て

よし、席順を並べ始めました。数学記述は以下の通り：

入力集合：A = {x | x <- a}
划分規則：
  Left = {x | x <- a, x < pivot}
  P = {pivot}
  Right = {x | x<- a, x >= pivot}
再帰定義：sort(A) = sort(Left) U P U sort(Right)

その中で pivot は軸（通常は先頭元を選び、安定性を追求するなら、ランダムに選ぶ）、つまり上記の「先生」で、左側の要素は彼より小さく、右側の要素は彼より大きい（または等しい）

毎回のクイックソートの目標は pivot の最終位置を見つけることで、この目的はバブル/選択ソートと差不多：毎回 1 つの最大/最小要素を選ぶ。問題を解決する思路はマージソートに類似：集合划分を通じて問題規模を縮減、マージソートは先部分有序再整体有序、而クイックソートは相当于先整体有序、再各部分有序

私たちが知る經典クイックソートアルゴリズムは 2 つのポインタが輪換移動、左右両端から pivot の最終位置に逼近、ポインタが重合する位置が今回の要找的划分点、集合を二分し、再分別排序

よし、では、赶紧弄两个指针、开始移动吧

等一下、我们这会儿在関数型世界、集合操作再简单不过了、要什么指针

クイックソートの再帰定義をもう一度見て、不就是想知道哪些要素大于 pivot，哪些要素小于 pivot嘛、好説：

left (x:xs) = [a | a <- xs, a < x]
right (x:xs) = [a | a <- xs, a >= x]

2 行の List Comprehension で搞定。だからクイックソートの実装が非常に優雅 になります：

quickSort' [] = []
quickSort' (x:xs) = (quickSort' left) ++ [x] ++ (quickSort' right)
  where left = [a | a <- xs, a < x]
        right = [a | a <- xs, a >= x]

では、もし非要要用两个指针的經典方式実装呢？もちろんできます：

-- 2 個のポインタ、常用的な寻找 p 最終位置的策略
-- p L ... H
quickSort'' [] = []
quickSort'' list @(x:xs) = (quickSort'' left) ++ [x] ++ (quickSort'' right)
  where assign i v xs = (take i xs) ++ [v] ++ (drop (i + 1) xs)
        pass p l h ltr xs
          -- 把*l 賦值为 p、划分結束
          | l >= h = l : (assign l p xs)
          -- l 右移
          | ltr == True = if low < p then pass p (l + 1) h True xs
              else pass p l (h - 1) False (assign h low xs)
          -- r 左移
          | ltr == False = if high > p then pass p l (h - 1) False xs
              else pass p (l + 1 ) h True (assign l high xs)
          where low = xs !! l
                high = xs !! h
        nextList = pass x 0 (length list - 1) False list
        (left, right) = let (x:xs) = nextList in ((take x xs), (drop (x + 1) xs))

中で使う assign が有点意思：

assign i v xs = (take i xs) ++ [v] ++ (drop (i + 1) xs)

データは不変、だから又以这种「新奇」的方式来完成简单操作：1 个点把一条線分成 2 段、抠掉这个点換上别的値、再把左右两段並べる

よし、今変態欲望が満たされました：私たちは可行的なアルゴリズムが関数型/命令型環境と無関係であることを証明しました、虽然多写了很多行。重新审视上記这两种思考モード的差异：

命令型：我跟你講啊、弄两个指针、分別從左右両端逼近、这样做就能找出划分点、再对划分后的子集分別排序

関数型：排序就是把集合從軸一分为二、再対左右両辺分別排序。其中、左辺都小于軸、右辺都大于（等于）軸

問題を記述する角度から、関数型思考はより問題の解の定義に専念し、而命令型はよりどのように每一个细节步驟を清楚に言うことに注目。思考モードの差異は大致：前者は先抽象後具体、後者は先具体後抽象

もちろん、命令型言語中でも抽象から具体に（先アルゴリズム骨格、再填充）、だから思考モードの差異と言います。PowerPoint テンプレート中の「主標題、副標題、列表項」带来的干扰一样、方便高效的循環構造在很大程度上影响了我们的思考モード：

この問題、感觉得 traverse、我们先写个循环、接下来再看循环体里该做什么

問題を解決する方法と具体步驟同样重要、関数型的表現力就在于対方法的准确記述。听起来很熟悉、没错、小学 6 年生の時、数学の先生が言った：

この問題は二元一次方程式で解くのが非常に容易、算術方法で考えるのは不太好

抽象から具体へ、是一种正向的思考過程、想要一步达到具体、则难的多

P.S.要不、来个 JS のクイックソート？：

function quickSort([x, ...xs]) {
  return !arguments[0].length ?
    [] :
    quickSort(xs.filter(a => a < x)).concat([x]).concat(quickSort(xs.filter(a => a >= x)))
}

なぜ !arguments[0].length は醜く見える、アロー関数は良くないのか？

良くない、JS には関数オーバーロード/パターンマッチがなく、xxs @(x:xs) のような原参照を保留する方式もない、才出此下策。而アロー関数は arguments オブジェクトにアクセスできず、具体は [4.关于 arguments オブジェクト](/articles/アロー関数-es6 ノート 6/#articleHeader8) を参照、非要要用なら、現在只有更醜的：

const quickSort = xxs => {
  if (!xxs.length) return []
  let [x, ...xs] = xxs
  return quickSort(xs.filter(a => a < x)).concat([x]).concat(quickSort(xs.filter(a => a >= x)))
}

三.礼畢

よし、今後また两��指针が動来動去的话を談ぶ時、関数型思考了解一下？怎么找划分点真的重要か？

前言