Clojure — трансдьюсеры, редьюсеры и прочая муть

[AndersonDunai]

М-м-м, аж покушать захотелось.

[Vitter]

Если редьюсеры — это свёртки(fold) в Хаскеле, то кто такие трансдюсеры?

[anjensan]

Редьюсеры — это частично примененная foldl,
с фиксированным списком и «препроцессором» для редукт функции.
Собственно этот «препроцессор» и суть трансдьюсер:

type RFn a r = r -> a -> r
type Reducer a =  forall r . RFn a r -> r -> r
type Transducer b a = forall r . RFn a r -> RFn b r

-- трансдьюсер `#(map %)`
map_t :: (a -> b) -> Transducer a b
map_t f xf r a = xf r (f a)

-- аналог `clojure.core.reducers/reducer`
reducer :: Transducer a b -> [a] -> Reducer b
reducer xf ls rf a = foldl (xf rf) a ls

-- трансдьюсер `(map inc)`
my_transducer :: Transducer Int Int
my_transducer = map_t (+1)

my_list :: [Int]
my_list = [1, 2, 3]

my_reducer :: Reducer Int
my_reducer = reducer my_transducer my_list

main = print $ my_reducer (*) 1 

[shock_one]

Если я правильно понимаю, идея в том, чтобы сворачивать коллекции проходясь по ним только один раз. Для производительности. Я честно пытался прочитать все примеры, но до конца так и не осилил.

Ваш пример на Haskell смотрится немного странно, учитывая, что эту простыню можно заменить на обычное

foldl (*) 1 $ map (+1) [1,2,3]

Правда ли, что мы хотим добиться чего-то типа

foldl (+) 0 $ (map succ). (filter (> 2)). (map (*3)) $ [1,2,3,4]

но в форме

foldl ((succ. (> 2). (* 3)) (+)) 0 [1,2,3,4]

то есть, чтобы комбинировать некомбинируемые средствами языка «трансдюсеры»?

Если да, то я даже не знаю, это не будет быстрее, зато будет намного непонятнее. Кстати, в конкретном случае с map-t можно комбинировать с помощью function composition — точки. Правда, с предикатамы filter-t так не сработает, но они комбинируются как моноиды или с помощью list comprehension.

filter (getAll. foldMap (All.) [odd, (>7), (<100), prime])

[x | x < — xs, odd x, x > 7, x < 100, prime x]

[anjensan]

В целом идея понята верно, но упущен один очень важный момент.
Мы хотим сворачивать коллекции в Clojure, проходя по ним только один раз.

Я привел код на Haskell дабы продемонстрировать что такое трансдьюсеры/редьюсеры с точки зрения типов, как бы мы, если бы вдруг нам приспичило, их могли написать. Посмотрите еще раз на эту «простыню», там даже список как отдельная 0-арная функция объявлен. Это же лишь пример.

Вы очень хорошую ссылку привели — в Haskell для производительности добавли оптимизацию. Так вот трансдьюсеры для Clojure — это тоже своего рода оптимизация. Только ее нельзя спрятать под капотом — язык сильно другой.

[Vitter]

Есть подозрения, что трансдюсеры — это попытка иметь сворачиваемые моноиды:

class Foldable t where
    -- | Combine the elements of a structure using a monoid.
    fold :: Monoid m => t m -> m
    fold = foldMap id

    -- | Map each element of the structure to a monoid,
    -- and combine the results.
    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldMap f = foldr (mappend . f) mempty

    foldr :: (a -> b -> b) -> b -> t a -> b

Собственно reducer это foldMap.
Похоже?

[anjensan]

Похоже. Дабы было меньше домыслов, то вот определение трансдьюсеров от Рича Хикки.

[vaniaPooh]

Непривычный, все-таки у Clojure синтаксис. Обычно дети, которые не умеют читать, смотрят только картинки и не читают текст. В данной ситуации — наоборот, смог прочитать только текст и не осилил листинги программ.

[roller]

Можно попробовать начать с игрушечного лиспа на рубях fogus.github.io/ulithp, а потом уже погружаться со всеми потрохами в мир кложуры :)

[comerc]

Легко!