來試試Haskell:要遞歸哦

操練一下

如果你已經會用類似R之類的語言的話,如果你已經會用Matlab之類的語言的話,如果你已經會用Python之類的語言的話,那麼,學Haskell難度會小很多的。當然,無基礎開始也沒問題,多練習一下就好啊~

打開GHCi之後,我們會看到Haskell的一些信息,還有GHCi的命令提示符:“Prelude>”。看下截圖吧~

ghci截图

我這個截圖是在Windows裡面做的。裡面比較有意思的是命令:“: ?”,這個對於初學Haskell還是很有意義的。這裡列出了GHCi所有基礎命令。比如如何在GHCi中改換當前目錄啦(:cd),怎麼編輯某一個文件啦(:edit <file>),怎麼加載haskell的程序代碼啦(:load)……等等~不要怕麻煩,上來試試看,總是有些益處的。相信我的這個建議吧~不過,如果你想試驗一下加載、編輯之類的命令,你可以在當前目錄里添加一個什麼內容都沒有的.hs文件,文件名只要是英文也都是隨意。然後,嘗試吧。

現在我們增加一些難度。來點兒真正意義上需要學習的東西吧~我們輸入這樣幾個命令:

1+2
2*3
3/4
4-5
5^6
6>7
7<8
8==9
9*pi
pi**(-1/10)
sin 1.1
not True
True && False
True || False
sqrt pi
exp 1

是不是看起來和計算器很相似呢?不過應該比計算器要麻煩一點點~對於GHCi加載后默認的部分數學函數,我們可以參照:這個網頁,看一看,練習一下就好了。例如:要計算二次方根需要打四個字母(sqrt)。而且有些計算是不支持的,我們需要再為Haskell添加相應的方法,比如:向量、矩陣、虛數等。不過現在我們先不考慮這些,現在我們要想想下一個東西吧!

自己動手豐衣足食

除了默認自帶的函數,很多時候是不足我們使用的。這時候就要我們自己來動手豐衣足食了。比如,計算圓的面積,我們需要知道圓的半徑(或者直徑),就可以了,我們就以半徑為例,讓我們先在一個空文檔中寫下如下代碼:

areaR r = pi * ( r ^ 2 )

把上述代碼保存為.hs文件。最後,我們在GHCi中讀取文件,就可以在GHCi中調用areaR這個函數了(讀取.hs文件的方法,我希望你已經在練習GHCi的時候通過:help命令已經學到了,沒學到也OK,假設你保存的文件是:“areatest.hs”,就是在Prelude提示符下,輸入:“:load areatest.hs”,或者“:l areatest.hs”)。

現在試驗一下,我們的函數對不對:
xxx
看起來,是完全沒有問題了。

那如果我們需要更多的說明呢?比如說,我們想讓函數的輸出顯示出一句話告訴我們圓面積。這時候我們需要這麼寫下代碼:

areaR :: Float -> String
areaR r =  "The size of the area is " ++ show(pi * r * r) ++ " square centimeters."

這段代碼中,有兩個不一樣的東西,一個是字符串的連接運算符:“++”,一個是代碼的第一行。字符串連接符不用多說,我們詳細說說代碼的第一行:“areaR :: Float -> String”。第一行其實就是Haskell函數的聲明方法。我來給大家總結一下Haskell大概有哪些聲明函數的方法:

  1. func :: a -> a -> a:這是一個有兩個變量一個結果的函數,而且默認這個函數所有變量都是同一類型的;
  2. func :: [a] -> String:這是自變量是一個List而輸出是一個字符串的函數,並且會推斷List的每項也都是字符串;
  3. func :: (Num a)=>a->a:這是有一個變量一個結果的函數,並且一上來就聲明這兩個變量都是Num類型的;
  4. func :: Float -> String:這是一個變量一個結果的函數,輸入是Float類型,輸出時字符串類型的;
  5. func :: (Num a)=>a->a->String:這是兩個自變量一個結果的函數,自變量是Num類型的,輸出時字符串String類型的。

由此,我們至少可以得到這樣的一個想法,Haskell的函數聲明,也存在類型推斷,變量之間使用“->”連接,主要類型聲明使用“=>”連接。總之,一般情況下,我們需要謹慎考慮在使用“=>”的變量聲明方法,因為如果調配不好容易出現一些函數編譯的錯誤。

其實仔細想想,我們就不難發現,在不添加任何其他內容的時候,上面我們說的這個函數建立方法,就是我們在數學上但以計算模型“f(x)->y”的抽象。或者說,一般不涉及多函數共同構成的計算的情況下,初始的這個計算模型抽象“f(x)->y”就足夠使用了。可是,如果我們需要一個目標函數包含幾種不同計算公式又要怎麼做呢?

不要忘了還可以遞歸哦

那麼,我們現在就考慮一下這種多計算公式包含在一個目標函數內的情形。在數學上,我們最直觀的一類這樣的函數,就是所謂的分段函數。我們舉一個例子好了比如這個函數(這個函數純粹是我胡寫的,沒有任何意義,不要罵我就好):

$$
f(x)=\left\{\begin{matrix}
x^2 & x<0\\ 1 & x>=0 \cap x<1\\ \log_{e} x & x>=1
\end{matrix}\right.
$$

我們使用Haskell來實現這個函數。因為函數只有一個輸入和輸出,所以,我們先考慮他的函數聲明,根據我們前面的總結,我們可以這樣設計(是否可以使用其他的聲明方式呢?這需要看這篇文章的讀者來自己考慮一下,我覺得這是理解Haskell類型和函數聲明時的絕妙機會):

funtest :: Double -> Double

然後,我們考慮要如何使用Haskell進行分段處理呢?一般的例如C的程序語言,會使用if-else語句進行劃分。但是,純函數式的編程的Haskell卻有自己的方式:

funtest :: Double -> Double
funtest a
	| a < 0 = a**2
	| a >= 1 = log a
	| otherwise = 1.0

對於這段代碼,我們仔細分析一下。其中的“a”就是指代函數的自變量這點根絕我們寫的第一個Haskell函數就可以明白,主要是這底下的那幾行有點讓人看起來暈暈的。其實啊,在Haskell里,下面這三行可以叫做 Guards。什麼是Guards呢?其實就是Haskell裡面用來判斷一段語句是否可以運行的方式,和一般的if語句差不多。當我們把它與分段函數對應之後,就不難發現,Guards是為了抽象類似分段函數這類載不動自變量區間內有不同計算公式的函數而設計的。這樣,就會好懂一些了吧?(或者,我解釋的范兒複雜了?哎呀~捂臉~)

這裡需要注意的是,“otherwise”這個關鍵詞,這就是指不同於上面情況的其他情況,是一個非常好的填補計算域的方法。對於Guards中的一行,是存在一個很明顯的框架結構的:“| 判斷條件 = 運算公式”。只要注意這個結構,一般情況下,我們出錯的概率就很低了。

不過,你是否已經發現?就算Guards結構再好,也還是有一些問題解決不了,比如斐波那契數列啊之類是由遞歸公式定義出函數的時候,我們需要,怎麼做?好吧,我不想人云亦云的用斐波那契數列或者Haskell經典的幾個求最大最小的範例,我們考慮一個稍有點不一樣的問題:求出某個整數以內的全部素數

首先,素數是只能被自己和1整除的數,也就是說,一個數V最大能被整除的數就是\( \sqrt V \),那可不可能比這個數大的整除V的數存在呢?顯然不可能。所以,我們只需要對2至V這些整數中搜索所有從2至\(\left \lfloor \sqrt V \right \rfloor\)不能被蒸出的數,就可以了。寫成一個簡單的算法就是:

  • 定義2至V的區間所有整數為A
  • 從數組A中,先刪去被區間第一個數整除的所有數,剩下的重新定義為A
  • 從數組A中,刪去能被區間第二個數整除的所有數,剩下的重新定義為A
  • 以此類推直到需要參考的數大於\(\left \lfloor \sqrt V \right \rfloor\)時結束,這是剩下的數組就是我們的目標了。

我們把這個用Haskell來寫出來吧!恩,是的,用Haskell的遞歸方式寫出來,雖然這麼寫不一定有什麼效率,畢竟現在我們的目标不是效率,稍有效率的方法我們在後面會接觸到,到時我們再來做一次。

prime (p:xs) = p : prime [x| x <- xs , mod x p /=0 ]

你看!我們只是用了一行Haskell的語句就大致的完成了上面的那個啰嗦算法(聰明的讀者一定已經發現了,這行代碼缺少了搜索的終止條件!)。這個方法的弊端是在搜索效率很低,同時這也是一個用到這裡所展示的Haskell編程知識我們不好解決的問題。

相對這種很直接的遞歸而言,很多時候,是有條件的遞歸,比如:在某一個輸入的條件下是要這麼遞歸,在另一個輸入條件下需要那樣的遞歸。一般語言中的解決是依然是使用if-else構建條件選擇,而在Haskell裡面,我們有兩個選擇一個是極其類似if-else結構的case-of方法,一個是模式匹配。為了說明和展示,我們考慮這樣一個問題好了,就在這個計算素數的基礎上我們稍加推廣:計算一個數列中有多少個素數。

xdo :: [Integer] -> Integer
xdo [] = 0
xdo (1:xt) = xdo xt
xdo (x:xt) | isPrime x = 1 + xdo xt
	   | otherwise = xdo xt
	   where isPrime :: Integer -> Bool
	         isPrime x = head (filter (\y -> mod x y == 0) [2..x]) == x

這是解決一個數列裡面有多少素數的Haskell函數。我們看到在函數聲明後面有很多的xdo開頭的語句。也就是這後面的三句xdo的語句就是模式匹配了。含義上,模式匹配就是指當xdo的變量為“[]”的時候,函數的結果就為0,函數xdo的變量為“(1:xt)”的時候,函數的結果就是“xdo xt”的結果。同理可知“xdo (x:xt)”的含義。不過這裡也還有幾個我們之前未說明的東西,比如:“where”。

where”在這裡,是用來說明前面函數中,“isPrime x”這個函數的出處,還有定義。總的來說,where可以把一段代碼集中管理起來,使得這段代碼能在前面的Guards里被重複使用,並且最重要的是,使得代碼可讀性加強。因為where的命名區間是獨立的,所以,不怕這裡的局部函數、變量名污染總體的命名空間。同時,where裡面也可以使用模式匹配。總之,這就是一個很方便的幫我們進一步把純函數式變成貫徹到底的小東西。

其他的未曾說過的語法點,我們下面會進一步說明。所以,沒看懂的部分也不用著急(就比如“filter (\y -> mod x y == 0) [2..x]”這一段)。

sidneyzhang

#iPhone #Mathematiker #male #Skorpion #Wordpress #Chineser #WOWer #MacBookPro #CSI #TBBT #LaTeX #Linux #Trading #lover@jossitixzhao

您可能还喜欢...

发表评论

电子邮件地址不会被公开。 必填项已用*标注