使用部分功能短路列表映射 [英] Short circuiting a list mapping with a partial function

问题描述

因此，我制作了一个名为tryMap的函数，如下所示:

/// tryMap, with failure and success continuations.
let rec tryMapC : 'R -> ('U list -> 'R) -> ('T -> 'U option) -> ('T list) -> 'R =
    fun failure success mapping list -> 
        match list with
        | []         -> success []
        | head::tail -> 
            match mapping head with
            | None        -> failure
            | Some result -> 
                let success = (fun results -> result::results |> success)
                tryMapC failure success mapping tail

/// <summary>
/// Attempts to map a list with a partial function.
/// <para/>
/// If a value which maps to None is encountered, 
/// the mapping stops, and returns None.
/// <para/>
/// Else, Some(list), containing the mapped values, is returned.
/// </summary>
let tryMap : ('T -> 'U option) -> 'T list -> 'U list option = 
    fun mapping list -> 
        tryMapC None Some mapping list

如其文档中所述，其目的是使用部分函数来映射列表，如果缺少更好"的单词，则在完全"映射不可能"的情况下简短地求知.

The purpose, as described in its documentation, is to map a list using a partial function, and short curcuit if a "full" mapping isn't "possible", for lack of better words.

以下是如何使用它的示例:

使用此功能...

let tryFac n = 
    do printf "The factorial of %d" n
    if n < 0 then 
        do printf " cannot be computed.\n"
        None
    else
        let result = (List.fold (*) 1 [1..n])
        do printf " is %d\n" result
        Some result

...现在，我们可以使用tryMap对整数列表进行全有或全无的映射，如下所示:

...we can now do an all-or-nothing mapping of a list of integers with tryMap like this:

> let all = tryMap tryFac [1..5];;
The factorial of 1 is 1
The factorial of 2 is 2
The factorial of 3 is 6
The factorial of 4 is 24
The factorial of 5 is 120
val all : int list option = Some [1; 2; 6; 24; 120]

> let nothing = tryMap tryFac [1;2;-3;4;5];;
The factorial of 1 is 1
The factorial of 2 is 2
The factorial of -3 cannot be computed.
val nothing : int list option = None

随后，例如，计算这些值的总和将很容易-如果可以全部进行计算，那就是

Afterwards it would be easy to, for example, calculate the sum of these values - if they could all be computed, that is.

现在，我的问题是:

是否有更简单/更干净的方法来实现此 tryMap 函数?(当然，除了不那么冗长之外::-P)我感觉可以使用列表表达式，也许表达式(来自FSharpx)或两者的结合来完成一些聪明的事情，但是目前我还不太清楚该怎么做.:-/

Is there a simpler/cleaner way to implement this tryMap function? (Besides not being so darn verbose, of course. :-P) I have a feeling something smart could be done using list expressions, maybe-expressions (from FSharpx) or maybe a combination of both, but I can't quite figure out how, at the moment. :-/

PS:如果该功能的名称比'tryMap'更好，请随时发表评论.:-)

更新1:

我想出了这个版本，该版本与我的初衷非常接近，只是它不会短路.:-/

I have come up with this version, which is very close to what I had in mind, except it sadly doesn't short-circuit. :-/

let tryMap : ('T -> 'U option) -> 'T list -> 'U list option = 
    fun mapping list -> maybe { for value in list do return mapping value }

注意:这使用FSharpx的may-表达式.

更新2:

感谢 Tomas Petricek ，我有了一个替代方案:

Thanks to Tomas Petricek, I got an idea for an alternative:

let tryMap (mapping : 'T -> 'U option) (list : 'T list) : 'U list option =
    List.fold
        (
            fun (cont,quit) value -> 
                if quit then 
                    (cont,quit)
                else
                    match mapping value with
                    | None   -> (cont,true)
                    | Some r -> ((fun rs -> (r::rs)) >> cont,quit)
        )
        (id,false)
        list
    |> (fun (cont,quit) -> if quit then None else Some (cont []))

此函数在映射到其第一个 None 值后停止映射.发生这种情况时， quit 将为 true ，其余元素将不会被映射.之后，如果 quit 为 true ，则部分映射的列表将被丢弃，并返回 None .如果它从未映射到 None ，则它将最终构建出用于构造映射列表的延续.

This function stops mapping after it maps to its first None value. When that happens, quit will be true, and the remaining elements won't be mapped. Afterwards, if quit is true, the partly mapped list is discarded and None is returned. If it never maps to None, it will have ended up building a continuation for constructing the mapped list.

尽管它仍然很大，但现在它仅发生轻度"短路，从某种意义上说，它不再尝试映射列表，但仍然遍历列表，因为这是折叠的工作方式.:-/

It's still quite large though, and now it only does a "light" short circuit, in the sense that it stops trying to map the list, but it still traverses it, since that's how a fold works. :-/

推荐答案

基于Daniel和SørenDebois的回答和评论，我提出了以下建议:

Based on answers and comments by Daniel and Søren Debois, I've come up with the following:

let tryMap f xs =
    let rec loop ys = function
        | []    -> maybe { return List.rev ys }
        | x::xs -> maybe { let! y = f x in return! loop (y::ys) xs }
    loop [] xs

我不太确定它是否为尾递归，因为我不是计算(或在这种情况下:也许)表达式的内部专家.

I'm not quite sure if it's tail-recursive or not though, since I'm not a total expert in the inner workings of computation- (or in this case specifically: maybe-) expressions.

你们怎么看?:-)

这篇关于使用部分功能短路列表映射的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！