這些問題在一般情況下要多做一些關于如何遞回思考的問題，但我會舉一個具體的例子來說明。
Graham HuttonmSort在視頻中解釋了這個函式：
https://youtu.be/I9S61BYM9_4?t=2089
因此，在我在視頻中鏈接的特定點上，教授說：
在這里，我有兩個排序串列：
msort :: [Int] -> [Int]
msort [] = []
msort [x] = [x]
msort xs = (msort ys) (msort zs)
where
(ys, zs) = halve xs
并突出顯示運算式(msort ys)和(msort zs)。然后，他merge在這些表達之前添加了這個詞。
msort :: [Int] -> [Int]
msort [] = msort []
msort [x] = msort [x]
msort xs = merge (msort ys) (msort zs)
where
(ys, zs) = halve xs
對我來說，似乎有一些假設，類似于邏輯中的假設，比如“如果這個假設場景是真的，那么（推匯出一些陳述）”。這些對于考慮遞回很有用，但與遞回函式的評估無關。所以，我的問題是：
- 他怎么能在沒有完全定義的
msort ys時候談論什么？msort - 當然，寫在那里的一切都沒有任何神奇的意義。但是選擇的詞是否僅有助于推理功能？我在問，因為他說
msort ys的是“排序串列”。他使用過去時。 - 這是否假設
halve將以合理的方式定義？再次，halve只是一個名字。
如果這些真的是基本問題，我深表歉意。這是我最近才開始疑惑的事情。
uj5u.com熱心網友回復：
這些問題是“基本的”，但從某種意義上說，它們是理解函式式語言和遞回程式概念的基礎，而不是因為它們很容易或顯而易見。
與邏輯假設的相似性并非完全巧合。msort赫頓給出的定義與數理邏輯中的歸納證明有關。在通常的數學歸納證明中，我們證明某事物適用于一個小的“基本情況”（例如，適用于n=0），然后我們證明如果某事物適用于任何任意大小的情況（例如，任何特定的n），它就成立對于“稍大”的情況（例如， for n 1）。由此，我們可以得出結論，它適用于所有情況（例如，對于 的所有值n>=0）。
在這里，我們為幾個小案例證明了一個屬性（例如，很容易對空串列進行排序，并且很容易對單元素串列進行排序），然后我們證明如果我們可以對兩個大致長度的串列進行排序n/2(例如，msort ys和msort zs)，那么我們可以對長度為n( msort xs) 的串列進行排序，并且我們通過歸納得出結論，可以對任意大小的串列進行排序。這里有很多細節要填寫，比如用一個奇數長度串列的一半長度來得到兩個“大約”一半長度的串列意味著什么，等等，但這是一般的想法。
可能值得指出的是，即使部分數學證明采用“如果我們假設大小為 15 的串列可以排序，那么我們可以對大小為 30 的串列進行排序”的形式，我們也沒有必要假設大小 15 可以排序以使用此證明。證明有效，因為前提“可以對大小為 1 的串列進行排序”和“假設可以對大小為 n 的串列進行排序，那么可以對大小為 n*2 的串列進行排序”允許我們得出結論，所有大小相等的串列可以對 2 的冪進行排序（并且對這個證明進行一些小的修改，我們可以證明任何大小的串列也可以排序）。“假設”是有效證明的形式結構的一部分，而不是我們需要為證明有效而做出的假設。
在某種程度上，遞回函式也是如此msort。現代函式式語言的魔力在于它msort 可以在msort“完全定義”之前使用。那是因為我們不需要證明我們可以定義msort一個大小為 15 的串列。我們只需要證明我們可以msort為大小為 30 的串列定義一個大小為15msort的串列，并且只要我們添加了幾個不依賴的基本情況msort（例如，大小為 0 或 1 的串列直接排序），定義msort- 就像歸納的數學證明一樣 - 作業正常。
當 Sutton 談到msort ys按過去時進行排序時，他遇到了將英語時態與遞回函式的含義相匹配的困難。在編譯時，msort ys它只是對正在定義程序中的函式的參考，但這就是遞回函式的魔力——定義它們的程序的一部分涉及呼叫正在定義中的函式。在運行時，時態是準確的。當您運行時msort [4,3,2,1]，它會呼叫msort [4,3]which 會將串列排序為[3,4]and msort [2,1]，它將將串列排序為[1,2]，并且這些排序（過去時）的值將可用于merged 到最終結果[1,2,3,4]中。
我不確定我是否理解您為什么不確定您是否理解halve- 是的，這假設halve將以與其名稱匹配的某種合理方式定義。但是，由于halve不依賴于msort或halve，因此它不會提出與 相同的哲學問題msort。如果有幫助，假裝halve被定義為：
halve xs = (take n xs, drop n xs) where n = length xs `div` 2
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/513466.html
標籤：哈斯克尔递归