代码之家 › 专栏 › 技术社区 › Patrick Parker

过滤器最大值n

ffl anura purely-functional filtering recursion

Patrick Parker · 技术社区 · 6 年前

可以用FFL写一个版本的 filter 在第一次负匹配后即假定其余项为正匹配后停止筛选?更一般地说,是一个过滤器。

例子:

filterMaxOf1([1,2,3,4], value<2)

预期结果:

[1、3、4]

这似乎是很难用纯粹的功能风格来写的东西。可能是递归或 let 会痛吗?

注:这个问题的全部动机是关于微观优化的假设。所以性能是非常相关的。我也在寻找一些通常适用于任何数据类型的东西,不仅仅是 int .

2 回复 | 直到 6 年前

Patrick Parker 6 年前

我最近添加了 find_index 对于能够轻松完成此操作的发动机:

if(n = -1, [], list[:n] + list[n+1:])
where n = find_index(list, value<2)
where list = [1,2,3,4]

查找索引 将返回第一个匹配项的索引,如果找不到匹配项,则返回-1。还有 find_index_or_die 它返回第一个匹配项的索引,并断言当您绝对确定列表中存在实例时是否找不到任何匹配项。

您还可以使用递归实现类似这样的功能:

def filterMaxOf1(list ls, function(list)->bool pred, list result=[]) ->list
base ls = []: result
base not pred(ls[0]): result + ls[1:]
recursive: filterMaxOf1(ls[1:], pred, result + [ls[0]])

1737973 6 年前

当然递归可以!D

filterMaxOf1(input, target)
where filterMaxOf1 = def
        ([int] l, function f) -> [int]
        if(size(l) = 0,
                [],
                if(not f(l[0]),
                        l[1:],
                        flatten([
                                l[0],
                                recurse(l[1:], f)
                        ])
                )
        )
where input = [
        1, 2, 3, 4, ]
where target = def
        (int i) -> bool
        i < 2

一些检查:

--> filterOfMax1([1, ]) where filterOfMax1 = [...]
[1]
--> filterOfMax1([2, ]) where filterOfMax1 = [...]
[]
--> filterOfMax1([1, 2, ]) where filterOfMax1 = [...]
[1]
--> filterOfMax1([1, 2, 3, 4, ]) where filterOfMax1 = [...]
[1, 3, 4]

这种风格失去了一些强大的类型安全性,但更接近尾部递归:

filterMaxOf1(input, target)
where filterMaxOf1 = def
        ([int] l, function f) -> [int]
        flatten(filterMaxOf1i(l, f))
where filterMaxOf1i = def
        ([int] l, function f) -> [any]
        if(size(l) = 0,
                [],
                if(not f(l[0]),
                        l[1:],
                        [
                                l[0],
                                recurse(l[1:], f)
                        ]
                )
        )
where input = [
        1, 2, 3, 4, ]
where target = def
        (int i) -> bool
        i < 2