фильтр макс N - PullRequest
       18

фильтр макс N

0 голосов
/ 23 мая 2018

Можно ли написать в FFL версию filter, которая прекращает фильтрацию после первого отрицательного совпадения, то есть предполагается, что оставшиеся элементы являются положительными совпадениями?в более общем смысле - фильтр.

Пример:

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

Ожидаемый результат:

[1,3,4]

Это кажется чем-то очень сложным для написания в чисто функциональном стиле.Может быть, рекурсия или let могли бы ее достичь?

Примечание: весь мотив этого вопроса заключался в гипотезе о микрооптимизации.так что производительность очень актуальна.Я также ищу что-то, что обычно применимо к любому типу данных, а не только int.

Ответы [ 2 ]

0 голосов
/ 24 мая 2018

Я недавно добавил find_index в движок, что позволяет легко это сделать:

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

find_index вернет индекс первого совпадения или -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]])
0 голосов
/ 23 мая 2018

Конечно рекурсия может!: 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
...