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