当前位置：文江博客话题详情

程序程序员的功能代码片段列表？

发布于 2024-07-19 05:58:00 字数 165 浏览 6 评论 0 原文

有时，我仍然在尝试将过程代码转换为功能代码时陷入困境。

是否有映射到程序习语/片段的功能习语/片段列表？

编辑

由于这些片段似乎没有一个集中的网站，因此我将其转变为社区维基。请粘贴任何程序-> 功能片段在这里。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

冰火雁神 2024-07-26 05:58:00

（编辑自这篇文章，位于 fshub)

我第一次在 OCaml/F# 中进行中断/继续操作时，它让我陷入了（无限）循环，可以这么说，因为没有这样的事情存在！在 OCaml 中，可以使用异常来中断循环，因为它们非常便宜，但在 F#（在 .NET 中）中，开销相当高，对于“正常”流控制没有用处。

不久前（为了消磨时间）使用排序算法时，出现了这个问题，该算法大量使用了重复/直到和中断。我突然意识到，递归尾部调用函数可以达到完全相同的结果，只是可读性略有下降。因此，我抛弃了“mutable bDone”和“while not bDone”，并尝试在没有这些命令式构造的情况下编写代码。下面仅提取循环部分，并展示如何使用尾调用编写重复/直到、执行/同时、执行/执行、中断/继续和中间测试样式代码。这些似乎都以与传统 F# 'while' 语句完全相同的速度运行，但您的里程可能会有所不同（某些平台可能无法正确实现尾部调用，因此可能会出现堆栈错误，直到它们被修补）。最后是用两种风格编写的（糟糕的）排序算法，以供比较。

让我们从以传统 F# 命令式风格编写的“do/while”循环开始，然后查看提供相同类型循环以及不同语义（例如 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

无 monad 的休息是什么意思？好吧，只需引入一个返回“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 标志。有趣的是，命令式解决方案在小型阵列上速度更快，而在大型阵列上仅慢一两个百分点。（不过，这是一个很好的例子）。

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

(Edited from this post on fshub)

The first time I went to reach for break/continue in OCaml/F#, it threw me for an (infinite) loop, so to speak, because no such thing exists! In OCaml, one can use exceptions to break from a loop because they are very cheap, but in F# (in .NET) the overhead is quite high and not useful for "normal" flow control.

This came up when playing with sort algorithms a while back (to kill some time), which make heavy use of repeat/until and break. It hit me that recursive tail call functions can achieve exactly the same result, with only a slight ding to readability. So, I threw out 'mutable bDone' and 'while not bDone' and tried writing the code without these imperative constructs. The following distills out just the looping parts and shows how to write repeat/until, do/while, while/do, break/continue, and test-in-the-middle style code using tailcalls. These all appear to run at exactly the same speed as a traditional F# 'while' statement, but your mileage may vary (some platforms may not properly implement tailcall and therefore may stack fault until they are patched). At the end is a (bad) sort algorithm written in both styles, for comparison.

Let's start with a 'do/while' loop, written in traditional F# imperative style, then look at functional variations which provide both the same type of loop, as well as different semantics like while/do, repeat/until, test in the middle, and even break/continue (without monads.. um, workflows!).

#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

Ok, that's easy enough. Keep in mind that f() is always called at least once (do/while).

Here is the same code, but in a functional style. Note that we don't need to declare a mutable here.

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

We can spin that to a traditional do/while by putting the function call inside the if block.

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

How about repeating a block until some condition is true (repeat/until)? Easy enough...

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

What was that about a monad-less break? Well, just introduce a conditional expression which returns 'unit', as in:

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

How about continue? Well, that's just another call to loop! First, with a syntax crutch:

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'()

And then again without the (ugly) syntax crutch:

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()

Easy as pie!

One nice result of these loop forms is that it makes it easier to spot and implement states in your loops. For example, a bubble sort continually loops over an entire array, swapping values that are out of place as it finds them. It keeps track of whether a pass over the array produced any exchanges. If not, then every value must be in the right place, so the sort can terminate. As an optimization, on every pass thru the array, the last value in the array ends up sorted into the correct place. So, the loop can be shortened by one each time through. Most algorithms check for a swap and update a "bModified" flag every time there is one. However, once the first swap is done, there is no need for that assignment; it's already set to true!

Here is F# code which implements a bubble sort (yes, bubble sort is terrible algorithm; quicksort rocks). At the end is an imperative implementation which does not change state; it updates the bModified flag for every exchange. Interestingly, the imperative solution is faster on tiny arrays and just a percent or two slower on large ones. (Made for a good example, though).

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

回复收藏 0 原文

離人涙 2024-07-26 05:58:00

哦，这是一个很好的问题。这里有一些，python 中的代码片段或一些 cloe：

for 循环可以替换为迭代器

stripped_list = [line.strip() for line in line_list]
for循环可以替换为apply或map或filter

<块引用>
<块引用>
<块引用>

map(上, ['句子', '片段'])
['句子'，'片段']
由函数组成的嵌套 for 循环
尾部递归代替循环
< p>生成器表达式代替 for 循环

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

回复收藏 0 原文

打小就很酷 2024-07-26 05:58:00

老作业问题：

功能

(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)))

是典型的命令式风格，带有赋值和循环。编写一个等效的 f-泛函函数，该函数不使用命令式功能 begin（排序）、while（goto）和 set（赋值）。您可以使用任意数量的“辅助函数”，只要它们是使用 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.

Old homework question:

The function

(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)))

is in a typical imperative style, with assignment and looping. Write an equivalent function f-functional that doesn't use the imperative features begin (sequencing), while (goto), and set (assignment). You may use as many ``helper functions'' as you like, as long as they are defined using let or letrec and not at top level.

One solution:

; 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.

回复收藏 0 原文

别忘他 2024-07-26 05:58:00

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

在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")

fold的另一个有用的用法是将向量复制到一套。由于 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！

The fold is a very interesting function, that is central in many functional algorithms. Let's say we want to add all the elements of a list. In procedural code, you would generally create an accumulator variable and set it to 0, then iterate through the list and increment the accumulator by the item.

In Ocaml, you perform the same action in a functional way by using fold:

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

Using fold, you can for example count the number of words in the list and concatenate them at the same time:

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

Another useful utilisation of fold is to copy a vector into a set. As sets in Ocaml are immutable, you effectively need to create for each item of the list a new set that contains the previous set plus that new item.

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]

Here, our initial object is an empty set, and at each call, a new set is created, based on the previous set and the current item by using IntSet.add.

Implement fold recursively yourself once, to know how it is done under the hood, then use the built-in version everywhere. Even in C++, with std::accumulate!

回复收藏 0 原文