algorithm - 优雅的 Array.multipick(?) 实现

Question

我想实现一些类似于想象中的Array.multipick:

Array.multipick : choosers:('a -> bool) [] -> array:'a [] -> 'a []

在内部，我们用所有选择器测试每个数组的元素，第一个返回true的选择器从选择器中移除code> 数组，然后我们将 chooser 的参数添加到结果中。之后，当 choosers 数组还有元素时，我们继续 交互。

最后一部分很重要，因为如果没有提前退出的要求，这可以通过 Array.fold 来解决。

这可以很容易地用类似的东西实现:

let rec impl currentIndex currentChoosers results

但这对我来说太程序化了。也许有更优雅的解决方案？

Answer 1

使用大小可变的数组编写优雅的代码是相当困难的。下面是一些适用于列表的代码，不会改变任何值。

let rec pick accum elem tried = function
    | [] -> (accum, List.rev tried)
    | chooser :: rest ->
        if chooser elem then (elem :: accum, List.rev_append tried rest)
        else pick accum elem (chooser :: tried) rest

let rec multipick_l accum choosers list =
    match choosers, list with
    | [], _
    | _, [] -> List.rev accum
    | _, elem :: elems ->
        let (accum', choosers') = pick accum elem [] choosers in
        multipick_l accum' choosers' elems

let multipick choosers array =
    Array.of_list
        (multipick_l [] (Array.to_list choosers) (Array.to_list array))

如果你认为Array.fold_left 除了提早退出的要求外还有用，你可以使用异常提早退出。