程序员程序员的功能代码片段列表? [英] List of Functional code snippets for Procedural Programmers?

查看:154
本文介绍了程序员程序员的功能代码片段列表?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

有时,我仍然试图将程序代码翻译成功能代码。



是否有一组映射到过程式成语/片段的功能性成语/片段列表?

编辑

由于似乎没有中央化的网站,这些片段,我把它变成一个社区维基。请在此处粘贴任何程序化功能代码片段。 .net / forums / thread / 10157.aspxrel =noreferrer>这篇文章关于 fshub



第一次在OCaml / F#中进入休息/继续时,它给我一个(无限)循环,可以这么说,因为没有这样的事情存在!在OCaml中,可以使用异常从循环中断开,因为它们非常便宜,但在F#中(.NET),开销非常高,对于正常流量控制无用。 p>

当使用排序算法回来时(为了杀死一些时间),这会大量使用repeat / until和break。它让我意识到,递归尾调用函数可以达到完全相同的结果,只有轻微的可读性。所以,我抛出了'可变的bDone'和'while not bDone',并试图在没有这些命令结构的情况下编写代码。下面简单介绍一下循环部分,并说明如何使用尾调用来编写repeat / until,do / while,while / do,break / continue和test-in-the-middle风格的代码。这些显示的运行速度与传统的F#'while'语句运行速度完全相同,但是您的里程可能会有所不同(某些平台可能无法正确实施tailcall,因此可能会在发生故障之前进行堆栈)。最后是一种用两种风格编写的(差)排序算法,用于比较。



让我们从用传统F#命令风格编写的'do / while'循环开始,然后查看提供相同类型循环的函数变体,以及不同的语义,如while / do,repeat / until,中间测试,甚至break / continue(没有monads,um,工作流!)。

  #light 
(*可以在...上工作)
let v = ref 0
let f()= incr v;
let g()=!v;
让N = 100000000

让imperDoWhile()=
让可变x = 0
让可变bDone = false
不bDone做
f()
x < - x + 1
if x> = N then bDone < - true

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



以下是相同的代码,但是以功能样式表示。

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



<我们可以通过将函数调用放在if块中来将其转换为传统做法。

  let funWhileDo() = 
让rec循环x =
如果x < N然后(* While *)
f()(* Do *)
loop(x + 1)
loop 0

重复一个块直到某个条件为真(repeat / until)如何?很简单...

 让funRepeatUntil()= 
让rec循环x =
f()( *重复*)
如果x> = N那么()(*直到*)
else循环(x + 1)
循环0

那是什么关于无单调休息的?那么,只需引入一个返回'unit'的条件表达式,如下所示:

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

继续如何?那么,这只是另一个循环呼叫!首先,用一个语法拐杖:

  let funBreakContinue()= 
let break'()=()
让rec继续'()=
let x = g()
if x> N然后中断'()
elif x%2 = 0然后
f(); F(); F();
continue'()
else
f()
continue'()
continue'()

然后再没有(丑陋的)语法拐杖:

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

易如反掌!



这些循环形式的一个很好的结果就是它可以更容易地在您的循环。例如,气泡排序会连续遍历整个数组,交换发现它们时不合适的值。它跟踪是否通过阵列产生任何交流。如果不是,那么每个值必须在正确的位置,因此排序可以终止。作为优化,在每次通过数组时,数组中的最后一个值最终排序到正确的位置。所以,循环可以每次缩短一次。大多数算法检查交换并每次更新一个b修改标志。但是,一旦第一次交换完成,就不需要该分配;它已经设置为true!



这是实现气泡排序的F#代码(是的,冒泡排序是可怕的算法;快速排序的岩石)。最后是一个不改变状态的命令性实现;它为每个交换更新bModified标志。有趣的是,微型阵列上的命令式解决方案速度更快,而大型阵列上速度更慢一两个百分点。 (尽管是一个很好的例子)。

  let inline sort2 fij(a:'a array)= 
让i'= a。[i]
let j'= a。[j]
if f i'j'> 0然后
a。[i]< - j'
a。[j]< - i'

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

让rec修改i endix =
if i = endix然后
未修改0(endix-1)
else
let j = i + 1
sort2 fij xs
修改j endix
和未修改的i endix =
if i = endix then
()
else
let j = i + 1
let i'= xs。[i]
let j'= xs。[j]
if f我'j'> 0然后
xs。[i]< -j'
xs。[j]< -i'
修改的j endix
else
未修改的j endix $未修改的b $ b 0(xs.Length-1)

let bubble_imperitive f(xs:'a array)=
let mutable bModified = true
let mutable endix = xs .Length - 1
while b修改完成
b修改< - 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然后
xs。[i] < - j'
xs。[j] < - i'
b修改< - 真
完成
完成


Sometimes I still get stuck trying to translate procedural code into functional code.

Is there a list of functional idioms/snippets that are mapped to procedural idioms/snippets?

Edit

Since there doesn't seem to be a centralized website of these snippets, I am turning this into a community wiki. Please paste any procedural -> functional snippets here.

解决方案

(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

这篇关于程序员程序员的功能代码片段列表?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆