Facebook Twitter LinkedIn E-mail
magnify
formats

imobilebbs.com -> guidebee.info

引路蜂技術博客網站 由www.imobilebbs.com

改成 www.guidebee.info

請修改您的書籤。 謝謝您的支持

 
 Share on Facebook Share on Twitter Share on Reddit Share on LinkedIn
imobilebbs.com -> guidebee.info已關閉評論  comments 
formats

F# 插入排序 和歸併排序

Published on 2016 年 09 月 04 日 by in F#

插入排序 insertSort

let insertSort array =
    let length = Array.length array
    for i in [1..(length-1)] do
        let key = array.[i]
        //insert key to sub array[0..i-1]
        let mutable j = i-1
        while (j>=0 && array.[j]>key) do
            array.[j+1] <- array.[j]
            j <- j-1
        array.[j+1]<-key

let a=[|6;7;1;3;2;9;8;18;18;12|]

a |> insertSort

歸併排序 mergesort


let merge array lo mid hi =
    let mutable i = lo
    let mutable j = mid
    let length = Array.length array
    let tempArray = Array.create length 0
    let mutable index =0
    while (i<mid && j<hi) do
        if array.[i]<array.[j] then
            tempArray.[index]<-array.[i]
            i<-i+1
            index<-index+1
        if array.[i]>=array.[j] then
            tempArray.[index]< -array.[j]
            j<-j+1
            index<-index+1

    //check if there's any remaining let
    if i<mid then 
        for k in [i .. (mid-1)] do
            tempArray.[index] <- array.[k]
            index<-index+1

    if j<hi then
        for k in [j .. (hi-1)] do
            tempArray.[index] <- array.[k]
            index<-index+1

    for i in [lo..(hi-1)] do
        array.[i] <- tempArray.[i-lo]

 
let rec mergeSort' array lo hi =
    let length = hi - lo
    if hi>1 + lo then
        let mid = (hi+lo)/2
        mergeSort' array lo mid
        mergeSort' array mid hi
        merge  array lo mid hi


let mergeSort array =
    mergeSort' array 0 (Array.length array)



let array =[|4;1;5;6;7;8;13;19;12|]

array |> mergeSort

 
Tags: ,
 Share on Facebook Share on Twitter Share on Reddit Share on LinkedIn
F# 插入排序 和歸併排序已關閉評論  comments 
formats

F#開發教程(13):函數化編程(十二)

延遲計算

伴隨函數化編程的是延遲計算。理論上認為,如果一個語言沒有「副作用」的話,那麼編譯器或是程序運行時可以自由選擇表達式的計算順序。
F#允許函數有副作用,因此編譯器或是運行時無法自由選擇表達式的計算順序。因此F#被認為具有嚴格的運算順序。但是你仍然可以利用延遲計算,然而你必須指明哪些計算可以延後計算。也就是有有需要時才計算。
F#中使用lazy來定義一個延後計算。定義在延遲計算中的表達式只有在明確指明需要計算時才會計算。計算的結果保存在緩存中以後後續調用,而無需重新計算。

> let lazyValue = lazy ( 2+3);;

val lazyValue : Lazy<int> = Value is not created.

> lazyValue.Force();;
val it : int = 5

lazy 定義了一個延遲計算,後門一行強制計算,返回5. 要注意的是延遲表達式最多只會計算一次,計算後,結果被保存,即使結果拋出異常。比如下個例子

> let lazySideEffect = 
-     lazy 
-         (
-              let temp = 2 + 2
-              printfn "%i" temp
-              temp
-          );;

val lazySideEffect : Lazy<int> = Value is not created.

> lazySideEffect.Force();;
4
val it : int = 4
> lazySideEffect.Force();;
val it : int = 4

lazySideEffect表達式定義一個「副作用」,顯示當前整數值,我們看以看到這段表達式只計算了一次,因此如果你依賴表達式的「副作用」來實現某些功能時,延遲計算可能就不太合適了。

延遲計算對於處理集合類型時比較有用,延遲集合類型的目的是只在需要集合的某個元素時才計算。F#中使用延遲計算的最常用的類型是序列Seq。
可能最重要也是最難理解的一個創建序列的函數是unfold。

// Signature:
Seq.unfold : ('State -> ('T * 'State) option) -> 'State -> seq<'T>

// Usage:
Seq.unfold generator state

如果我們聯繫起數列的遞推公式,就可以比較容易的理解unfold。比如 Fibonacci數列的遞推公式

S0=1; S1=1
Sn+2=Sn+ Sn+1

我們使用一個二元組作為參數(這裡有兩個初始值,二元組是個比較合適的類型)

> Seq.unfold ( fun state -> Some( fst state, ((snd state),(fst state)+(snd state)))) (1,1);;
val it : seq<int> = seq [1; 1; 2; 3; ...]

如果把state用二元組(ao,a1)的形式表示,可以簡化為

> Seq.unfold ( fun (n0,n1) -> Some(n0,(n1,n0+n1))) (1,1);;
val it : seq<int> = seq [1; 1; 2; 3; ...]
 
Tags:
 Share on Facebook Share on Twitter Share on Reddit Share on LinkedIn
F#開發教程(13):函數化編程(十二)已關閉評論  comments 
formats

F#開發教程(12):函數化編程(十一)

異常和異常處理

F#中定義異常和定義聯合類似,異常處理類似於模式匹配。定義異常使用excpetion關鍵字,然後是異常的名稱,再次為可選的異常數據類型。多個類型使用*分隔(其實是元組類型)
例如

exception WrongSecond of int

使用raise來拋出異常。F#中還有一個failwith函數可以拋出異常。

> exception WrongSecond of int
- let primes = [ 2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59 ];;

exception WrongSecond of int
val primes : int list =
  [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59]

> let testSecond() =
-     try
-         let currentSecond = System.DateTime.Now.Second 
-         if List.exists (fun x -> x = currentSecond) primes then
-             failwith "A prime second"
-         else
-             raise (WrongSecond currentSecond)
-     with
-     WrongSecond x ->
-         printf "The current was %i,which is not prime" x;;

val testSecond : unit -> unit

> testSecond();;
The current was 1,which is not primeval it : unit = ()

try 和 with 用來處理異常,將可能會出現異常的表達式放在try 和 with 之間。with之後定義一個或多個異常類型的模式匹配。和普通的模式匹配最大的差異在於異常的模式匹配在沒有沒有完全定義所有異常模式處理時編譯器不會給出警告,這是因為任何沒有處理的異常都會逐步向上傳播。
F#也支持finally,它和try一起使用。但finally不能和with一同使用。

// function to write to a file
let writeToFile() =
    // open a file
    let file = System.IO.File.CreateText("test.txt")
    try
// write to it
        file.WriteLine("Hello F# users")
    finally
        // close the file, this will happen even if
        // an exception occurs writing to the file
        file.Dispose()
// call the function
writeToFile()
 
Tags:
 Share on Facebook Share on Twitter Share on Reddit Share on LinkedIn
F#開發教程(12):函數化編程(十一)已關閉評論  comments 
formats

F#開發教程(11):函數化編程(十)

計量單位

F#的類型系統有個非常有趣的功能是支持計量單位。支持給數值添加計量單位。目的是避免在使用數值時錯誤的引用。比如把一個單位為厘米的長度數據和單位為英寸的長度數據未經轉換直接相加。
F#使用屬性來定義一個計量單位,比如定義m為長度單位。

[<Measure>]type m

然後你就可以使用這個單位來定義數值,比如

> let meters = 10<m>;;

val meters : int<m> = 10

比如之前我們使用聯合定義多種計量單位,我們換用屬性

> [<Measure>]type pint;;

[<Measure>]
type pint

> [<Measure>]type liter;;

[<Measure>]
type liter

> let vol1 = 2.5<liter>;;

val vol1 : float<liter> = 2.5

> let vol2 = 2.5<pint>;;

val vol2 : float<pint> = 2.5

> let newVol = vol1 + vol2;;

  let newVol = vol1 + vol2;;
  --------------------^^^^

/Users/James/stdin(43,21): error FS0001: The unit of measure 'pint' does not match the unit of measure 'liter'

可以看到把兩個使用不同計量單位的數值相加,系統報錯。
你可以定義轉換成統一的計量單位,然後在計算。

// define some units of measure
[<Measure>]type liter
[<Measure>]type pint
// define some volumes
let vol1 = 2.5<liter>
let vol2 = 2.5<pint>
// define the ratio of pints to liters
let ratio =  1.0<liter> / 1.76056338<pint>

 
Tags:
 Share on Facebook Share on Twitter Share on Reddit Share on LinkedIn
F#開發教程(11):函數化編程(十)已關閉評論  comments 
formats

F#開發教程(10):函數化編程(九)

活躍模式

活躍模式(active patterns)提供了一個靈活的方式來使用F#中的模式匹配。它允許你積極主動地調用一個函數來判斷輸入是否匹配,這也是它被稱為「活躍」模式的原因。
所有的活躍模式根據輸入進行一個的計算來判斷是否有匹配發生。有兩種類型的活躍模式:
完全活躍模式 支持你將匹配拆分成有限的幾種情況。
部分活躍模式 有匹配或匹配失敗兩種情況之一。

完全活躍模式

定義完全活躍模式和定義函數的語法比較近似,關鍵的差別是完全活躍模式的標誌符包含在香蕉括弧(banana brackets)中.香蕉括弧是括弧加豎直線(||).不同的匹配類型以豎直線分隔。活躍模式的主體部分為一F#函數,該函數必須返回定義在香蕉括弧中所有類型。在返回所有的類型數據時可以返回額外的數據,如同聯合類型一樣。

> open System;;
> let (|Bool|Int|Float|String|) input =
-     let success,res = Boolean.TryParse input
-     if success then Bool(res)
-     else
-         let success,res = Int32.TryParse input
-         if success then Int(res)
-         else
-             let success,res = Double.TryParse input
-             if success then Float(res)
-             else String(input);;

val ( |Bool|Int|Float|String| ) :
  input:string -> Choice<bool,int,float,string>

> let printInputWithType input =
-     match input with 
-     | Bool b -> printfn "Boolean: %b" b
-     | Int i -> printfn "Integer: %i" i
-     | Float f -> printfn "Floating point: %f" f
-     | String s -> printfn "String: %s" s;;

val printInputWithType : input:string -> unit

> printInputWithType "true";;
Boolean: true
val it : unit = ()
> printInputWithType "12";;  
Integer: 12
val it : unit = ()
> printInputWithType "-12.3";;
Floating point: -12.300000
val it : unit = ()

部分活躍模式

部分活躍模式定義和完全活躍模式定義接近,所不同是部分活躍模式的香蕉括弧內只有兩種情況,一個是有匹配,一個無匹配。此外完全活躍模式可以保證返回香蕉括弧中定義的類型之一,而部分活躍模式可能有不匹配情況的發送,因此它的返回值得類型是可選類型Option.
所有活躍模式出輸入參數外,還可以有額外的參數,這想額外參數必須定義在輸入參數的前面,比如

open System.Text.RegularExpressions
// the definition of the active pattern
let (|Regex|_|) regexPattern input =
    // create and attempt to match a regular expression
    let regex = new Regex(regexPattern)
    let regexMatch = regex.Match(input)
    // return either Some or None
    if regexMatch.Success then
        Some regexMatch.Value
    else
        None

// function to print the results by pattern
// matching over different instances of the
// active pattern
let printInputWithType input =
    match input with
    | Regex "$true|false^" s -> printfn "Boolean: %s" s
    | Regex @"$-?\d+^" s -> printfn "Integer: %s" s
    | Regex "$-?\d+\.\d*^" s -> printfn "Floating point: %s" s
    | _ -> printfn "String: %s" input
// print the results
printInputWithType "true"
printInputWithType "12"
printInputWithType "-12.1"

完全活躍模式的行為和聯合類型非常一致,意味著如果匹配規則沒有覆蓋所有情況時會給出警告。而部分活躍模式,需要最後定義個通配規則,部分活躍模式也它的優點,也就是可以將多個規則串接在一起,比如上面例子中定義了三個不同的正規語法匹配。

 
Tags:
 Share on Facebook Share on Twitter Share on Reddit Share on LinkedIn
F#開發教程(10):函數化編程(九)已關閉評論  comments