Можно ли написать функцию, которая берет карту, уменьшает или фильтрует и возвращает их «функционализированную» версию?

Question

Простите, что у меня нет правильной терминологии - я ничего не знаю о морфизмах и т. Д., Но у меня есть ощущение, что концепция, которую я пытаюсь выразить, может быть описана каким-то термином такого рода.

Отображение, уменьшение и фильтрация классических функций высшего порядка имеют общую структуру: функция f и список данных xs и что-то с этим f для всех * 1006. *. Теперь для каждой из них я могу представить себе «функционализированную» версию - назовите их mapf, reduf и filterf - которая вместо этого берет часть данных x и список функций fs и выполняет каждую из функций fs к данным x. В частности, mapf выдаст вам список f1(x), f2(x), ..., reduf даст вам f3 (f2 (f1 (x))) или f1 (f2 (f3 (x))) (в зависимости от того, будет ли он левым или правым), а filterf проверит, был ли каждый из f1(x), f2(x), ... истинным, и возвратит только fs, которые были.

Мой вопрос заключается в следующем: возможно ли написать общую функцию functionise, которая принимает map, reduce или filter в качестве аргумента и создает соответствующую функцию mapf, reduf или filterf? (Конечно, элегантно, не просто как последовательность выражений).

Я не против, какой язык программирования используется; в своих собственных экспериментах я использовал Haskell, и что привело меня к этому вопросу, так это то, что я заметил, что все три функции могут быть определены очень аналогичным образом:

rev = \x y -> y x

mapf :: a -> [a -> b] -> [b]
mapf x fs = map (rev x) fs

reducef :: a -> [a -> a] -> a
reducef x fs = foldl rev x fs

filterf :: a -> [a -> Bool] -> [a -> Bool]
filterf x fs = filter (rev x) fs

Меня восхищает их сходство, поэтому я хотел бы либо выяснить, что это возможно, и посмотреть, как, либо показать, что это невозможно, и понять, почему. Как я уже сказал, язык программирования не имеет решающего значения, поэтому я не против, если это возможно на языке A, но не на языке B из-за системы типов языка B. Это было бы интересно.

Спасибо!

Answer 1

Не имеет смысла преуменьшать ваши идеи, но это вряд ли стоит усилий. Например, применить список функций к значению будет:

map ($ v) [f1, f2, f3]

Ваш mapf это просто еще одна специализация map

mapf :: v -> [(v -> a)] -> [a]
mapf v fs = map ($v) fs

Answer 2

reducef не совсем соответствует тому же шаблону, что и другие, но для map и filter шаблон равен \g x fs -> g (rev x) fs или (. rev) для краткости:

> :t (. rev) map
(. rev) map :: a -> [a -> t] -> [t]
> :t (. rev) filter
(. rev) filter :: a -> [a -> Bool] -> [a -> Bool]

Если вы хотите включить reducef, вам понадобится немного другой шаблон, \g x fs -> g rev x fs, который можно сократить до ($ rev):

> :t ($ rev) foldl
($ rev) foldl :: t -> [t -> t] -> t

Он не будет работать на map и filter напрямую, но вы можете использовать его на (map .) и (filter .):

> :t ($ rev) (map .)
($ rev) (map .) :: t1 -> [t1 -> t] -> [t]
> :t ($ rev) (filter .)
($ rev) (filter .) :: t1 -> [t1 -> Bool] -> [t1 -> Bool]

Так что я думаю, functionalise = ($ rev) - это как можно ближе.

Answer 3

Ваш код похож на 'swing', который я нашел спрятанным в вики под pointfree .

swing f c a = f ($ a) c

swing map :: forall a b. [a -> b] -> a -> [b]
swing any :: forall a. [a -> Bool] -> a -> Bool
swing foldr :: forall a b. b -> a -> [a -> b -> b] -> b
swing zipWith :: forall a b c. [a -> b -> c] -> a -> [b] -> [c]
swing find :: forall a. [a -> Bool] -> a -> Maybe (a -> Bool)

-- applies each of the predicates to the given value, returning the first
-- predicate which succeeds, if any

swing partition :: forall a. [a -> Bool] -> a -> ([a -> Bool], [a -> Bool])