Как преобразователь отличается от частично применяемой функции?

Ответ 1

В Clojure (map inc) есть преобразователь, но не в Haskell, потому что Haskell должен подчиняться каррированию, но нетипизированный Lisp может нарушить это соглашение по карри по умолчанию. Вместо этого тип преобразователей:

type Transducer a b = forall r . (b -> r -> r) -> (a -> r -> r)

Мы говорим, что преобразователь "превращается a в b '. Да, a и b кажутся" обратными" с правой стороны. forall означает, что преобразователь должен оставить r как общую переменную типа, но полностью разрешено специализироваться на a и b.

Позвольте мне обратить два аргумента в foldr:

-- cf. with foldr :: (x -> r -> r) -> r -> [x] -> r
ffoldr :: (x -> r -> r) -> [x] -> r -> r
ffoldr = flip . foldr

(мы также можем использовать foldl, но он будет стремиться изменить ситуацию позже). Это означает, что a Transducer можно использовать для преобразования первого аргумента ffoldr из x в y, так что вместо него мы можем обрабатывать [x] с помощью y -> r -> r с помощью foldr. Преобразователи располагаются между "входами ([x], r) и конечным процессором (y, r) -> r.

Я перевернул два вторых аргумента, чтобы подчеркнуть также, что, на удивление, ffoldr :: Transducer [x] x. Используя симметрию аргументов, мы также имеем общий состав преобразователей, который является просто составной функцией:

(.) :: Transducer a b -> Transducer b c -> Transducer a c

(Если вы считаете, что это здорово, что предоставление этих терминов forall r позволяет нам обратить вспять, как вы обычно используете ., вы можете сделать это произвольно с помощью метода, называемого "продолжением передачи".)

Например, здесь фильтр-преобразователь:

tfilter :: (a -> Bool) -> (a -> r -> r) -> a -> r -> r 
    -- or: (a -> Bool) -> Transducer a a
tfilter predicate f a = if predicate a then f a else id

Это применит функцию сокращения f к a и r только в том случае, если предикат выполняется. Существует также преобразователь отображения:

tmap :: (a -> b) -> (b -> r -> r) -> a -> r -> r 
tmap ba f a = f (ba a)

Это дает сложную семантику карт/фильтров для любого типа "преобразуемого": одна карта/фильтр fn может работать для нескольких контекстов.

Тип Transducer имеет симпатичный изоморфизм: оказывается, что foldr списка forall r. (x -> r -> r) -> r -> r полностью эквивалентен этому списку [x] (это "церковная кодировка" этого списка), и поэтому он заменяет аргумент a к самому фронту определения преобразователя дает нам (IMO намного легче понять!) тип type TransL a b = a -> [b]. И это намного легче понять:

tl_map f = \a -> [f a]
tl_filter predicate = \a -> if predicate a then [a] else []

Чтобы запустить их в списке, используйте concatMap... который оказался просто >>=! Поэтому вы просто пишете collection >>= transducer, и у вас есть трансдуцированная коллекция. Тогда смысл TransL a b заключается в том, чтобы "взять каждый элемент исходного списка a и дать мне 0 или более элементов типа b для соединения в моем исходящем списке". Он фильтрует путем сращивания 0 элементов, когда предикат не работает; он отображает, получая 1 выходной элемент для каждого элемента ввода; другая операция tl_dupe = \a -> [a, a] - это преобразователь, который дублирует элементы в списке, [1,2,3] >>= tl_dupe становится [1,1,2,2,3,3].

Где foldr выглядит как Transducer [x] x, теперь он становится идентичным id :: TransL [x] x, который имеет способ просто выполнить операцию concat в середине вычисления; тождественная функция в этой алгебре фактически return = \a -> [a], также записана (:[]). Потеря только заключается в том, что мы больше не можем использовать . для их компоновки, но на самом деле одна и та же композиция предоставляется в Control.Monad как оператор композиции Клейсли >=>.

Короче говоря, преобразователи - это функции a -> [b], умно преобразованные с помощью немного церковного кодирования, так что оператор композиции Клейсли для этих стрелок Клейсли в монаде списка становится просто (.).