程序程序员的功能代码片段列表?[关闭]

(编辑自 this post 在 fshub )

我第一次在ocaml/f中到达break/continue时,它让我陷入了一个(无限)循环,可以说,因为不存在这样的东西!在ocaml中,可以使用异常从循环中断,因为它们是 非常 虽然很便宜,但是在f(in.net)中,开销相当高,对于“正常”的流控制来说不太有用。

这是在前一段时间使用排序算法时出现的(为了消磨时间),这会大量使用重复/直到和中断。我突然想到,递归尾调用函数可以获得完全相同的结果,对可读性只有轻微的改进。因此,我抛出了“可变的bdone”和“while not bdone”,并尝试在不使用这些命令式构造的情况下编写代码。下面将提取循环部分,并演示如何使用tailcalls在中间样式的代码中编写repeat/until、do/while、while/do、break/continue和test。这些都与传统的“while”语句以完全相同的速度运行,但您的里程数可能会有所不同(某些平台可能无法正确地执行尾调用,因此可能会在修补之前堆积错误)。最后是用两种样式编写的(坏的)排序算法,用于比较。

让我们从一个“do/while”循环开始,它是用传统的f_命令式编写的,然后看看功能变化,它既提供了相同类型的循环,也提供了不同的语义,如while/do、repeat/until、中间测试,甚至中断/继续(没有monad)。嗯,工作流程!.

#light
(* something to work on... *)
let v = ref 0
let f() = incr v;
let g() = !v;
let N = 100000000

let imperDoWhile() =
    let mutable x = 0
    let mutable bDone = false
    while not bDone do
        f()
        x <- x + 1
        if x >= N then bDone <- true

好吧,这很简单。请记住,f()总是至少调用一次(do/while)。

这里有相同的代码,但是是一种函数式的。注意,我们不需要在这里声明可变的。

let funDoWhile() =
    let rec loop x =
        f()             (*Do*)
        if x < N then   (*While*)
            loop (x+1)
    loop 0

我们可以将函数调用放在if块中,从而将其转换为传统的do/while。

let funWhileDo() =
    let rec loop x =
        if x < N then   (*While*)
            f()         (*Do*)
            loop (x+1)
    loop 0

重复一个块直到某个条件为真(重复/直到)?足够简单…

let funRepeatUntil() =
    let rec loop x =
        f()                 (*Repeat*)
        if x >= N then ()   (*Until*)
        else loop (x+1)
    loop 0

那是什么关于一个没有单子的休息?那么,只需引入一个返回“Unit”的条件表达式,如:

let funBreak() =
    let rec loop() =
        let x = g()
        if x > N then ()    (*break*)
        else
            f()
            loop()
    loop()

继续怎么样?好吧,那只是另一个循环调用!首先,使用语法拐杖:

let funBreakContinue() =
    let break' () = ()
    let rec continue' () =
        let x = g()
        if   x > N then break'()
        elif x % 2 = 0 then
            f(); f(); f();
            continue'()
        else
            f()
            continue'()
    continue'()

又一次没有(丑陋的)语法拐杖:

let funBreakContinue'() =
    let rec loop () =
        let x = g()
        if   x > N then ()
        elif x % 2 = 0 then
            f(); f(); f();
            loop()
        else
            f()
            loop ()
    loop()

易如反掌!

这些循环形式的一个很好的结果是,它使得在循环中更容易发现和实现状态。例如,冒泡排序会在整个数组上不断循环,在找到值时交换不合适的值。它跟踪数组的传递是否产生任何交换。如果不是,那么每个值都必须在正确的位置,这样排序就可以终止。作为一种优化,在每次传递数组时,数组中的最后一个值都会被排序到正确的位置。因此,循环可以每次缩短一个。大多数算法检查交换,并在每次交换时更新“bmodified”标志。但是,一旦第一次交换完成,就不需要进行该分配;它已经设置为true!

下面是实现气泡排序的F代码(是的,气泡排序是糟糕的算法;快速排序岩石)。最后是一个不改变状态的命令式实现;它为每个交换更新bmodified标志。有趣的是,这个必要的解决方案在小阵列上速度更快,而在大阵列上只慢了1%或2%。(不过,这是个很好的例子)。

let inline sort2 f i j (a:'a array) =
    let i' = a.[ i ]
    let j' = a.[ j ]
    if f i' j' > 0 then
        a.[ i ] <- j'
        a.[ j ] <- i'

let bubble f (xs:'a array) =
    if xs.Length = 0
    then ()

    let rec modified i endix =
        if i = endix then
            unmodified 0 (endix-1)
        else
            let j = i+1
            sort2 f i j xs
            modified j endix
    and unmodified i endix =
        if i = endix then
            ()
        else
            let j = i+1
            let i' = xs.[ i ]
            let j' = xs.[ j ]
            if f i' j' > 0 then
                xs.[ i ] <- j'
                xs.[ j ] <- i'
                modified j endix
            else
                unmodified j endix
    in unmodified 0 (xs.Length-1)

let bubble_imperitive f (xs:'a array) =
    let mutable bModified = true
    let mutable endix = xs.Length - 1
    while bModified do
        bModified <- false
        endix <- endix - 1
        for i in 0..endix do
            let j = i+1
            let i' = xs.[ i ]
            let j' = xs.[ j ]
            if f i' j' > 0 then
                xs.[ i ] <- j'
                xs.[ j ] <- i'
                bModified <- true
        done
    done

哦,这是个很好的问题。这里有一些, code snips in python 或者其他什么东西:

• for循环可以替换为迭代器

  stripped_list = [line.strip() for line in line_list]

• for循环可以替换为apply、map或filter

  map(上,[“sentence”,“fragment”]) ['句子','片段']

• 嵌套for循环,由函数组成

• 尾部递归代替循环

• 代替for循环的生成器表达式

  sum(x*x for x in range(10))

旧作业问题:

函数

(define f-imperative (y) (x) ; x is a local variable
  (begin
    (set x e)
    (while (p x y)
       (set x (g x y)))
    (h x y)))

是一种典型的命令式样式,带有赋值和循环。编写一个不使用命令式特性begin(sequence)、while(goto)和set(assignment)的等效函数f-functional。您可以使用任意多的“helper函数”,只要它们是使用let或letrec定义的,而不是顶级的。

一种解决方案:

; The idea is simple: 
; Use parameter passing for binding the values 
; of the variables and recursion instead of iteration. 
;
; For those who like theory this is the main argument for proving 
; that recursive functions (LISP, lambda calculus) have the same 
; computational power as any imperative programming language. 

(define f-functional (y) 
  (letrec (
     (f-helper (lambda (x y)
                  (if (p x y) 
                     (f-helper (g x y) y)
                     (h x y)))))
     (f-helper e y)))

; Notice that y in f-helper is invariant.  Therefore, we can rewrite
; f-helper without y as follows.

(define f-functional (y) 
  (letrec (
     (f-helper (lambda (x)
                  (if (p x y) 
                     (f-helper (g x y))
                     (h x y)))))
     (f-helper e)))

; This is not the only solution, though I think it is one of the 
; nicer ones.

折叠是一个非常有趣的函数,它在许多函数算法中是核心。假设我们要添加列表中的所有元素。在过程代码中,您通常会创建一个accumulator变量并将其设置为0,然后遍历该列表并按项递增accumulator。

在ocaml中,通过使用fold以功能方式执行相同的操作:

List.fold_left (+) 0 [1; 2; 3];;
- : int = 6

例如,使用fold,可以计算列表中的单词数,并同时将它们连接起来:

List.fold_left (fun (count, concat) e -> (count + 1, concat ^ e)) (0, "") ["a"; "b"; "c"];;
- : int * string = (3, "abc")

折叠的另一个有用用途是将向量复制到集合中。由于ocaml中的集合是不可变的,因此您实际上需要为列表中的每个项创建一个新集合,其中包含前一个集合和新项。

module Int = struct type t = int let compare = compare end;;
module IntSet = Set.Make(Int);;

let s = List.fold_left (fun set e -> IntSet.add e set) IntSet.empty [1; 2; 3];;
val s : IntSet.t = <abstr>

IntSet.elements s;;
- : IntSet.elt list = [1; 2; 3]

这里,我们的初始对象是一个空的集合,在每次调用时,都会使用intset.add基于上一个集合和当前项创建一个新的集合。

实现一次递归折叠,了解如何在引擎盖下完成,然后在任何地方使用内置版本。即使在C++中 std::accumulate !

Pleac项目的目标几乎就是这样——用其他语言实现PerlCookBook中的所有示例。这里有到OCAML版本的链接(这是三个100%完成的版本之一) http://pleac.sourceforge.net/pleac_ocaml/index.html