함수형 사고 모드의 세례

서문에

이하 문맥은 모두 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)))
}

三.礼畢

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

서문에