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

Question

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the help center寻求指导。




9年前关闭。




有时我仍然在尝试将程序代码转换为函数代码时遇到困难。

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

编辑

由于似乎没有这些片段的集中网站，因此我将其变成了社区 wiki。请在此处粘贴任何程序 -> 功能片段。

Answer 1

(编辑自 this post 上 fshub )

我第一次在 OCaml/F# 中尝试中断/继续时，它让我陷入了一个(无限)循环，可以这么说，因为不存在这样的东西!在 OCaml 中，可以使用异常来中断循环，因为它们非常便宜，但在 F#(在 .NET 中)中，开销非常高，对于“正常”流控制没有用处。

这在不久前使用排序算法(以消磨时间)时出现，该算法大量使用重复/直到和中断。令我震惊的是，递归尾调用函数可以达到完全相同的结果，只是对可读性有一点影响。所以，我抛弃了“可变 bDone”和“虽然不是 bDone”，并尝试在没有这些命令式结构的情况下编写代码。下面仅提取循环部分，并展示如何使用尾调用编写重复/直到、do/while、while/do、break/continue 和 test-in-the-middle 样式代码。这些似乎都以与传统 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 block 中，我们可以将其旋转为传统的 do/while。

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

重复一个 block 直到某些条件成立(重复/直到)怎么样？够简单...

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