Module: Transducers

Defined in:
lib/transducers.rb

Overview

Transducers are composable algorithmic transformations. See http://clojure.org/transducers before reading on.

Terminology

We need to expand the terminology a bit in order to map the concepts described on http://clojure.org/transducers to an OO language like Ruby.

A reducer is an object with a step method that takes a result (so far) and an input and returns a new result. This is similar to the blocks we pass to Ruby's reduce (a.k.a inject), and serves a similar role in transducing process.

A handler is an object with a call method that a reducer uses to process input. In a map operation, this would transform the input, and in a filter operation it would act as a predicate.

A transducer is an object that transforms a reducer by adding additional processing for each element in a collection of inputs.

A transducing process is invoked by calling Transducers.transduce with a transducer, a reducer, an optional initial value, and an input collection.

Because Ruby doesn't come with free-floating handlers (e.g. Clojure's inc function) or reducing functions (e.g. Clojure's conj), we have to build these things ourselves.

Examples

# handler
inc = Class.new do
        def call(input) input += 1 end
      end.new

# reducer
appender = Class.new do
             def step(result, input) result << input end
           end.new

# transducing process
Transducers.transduce(Transducers.map(inc), appender, [], 0..9)
#=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

You can pass a Symbol or a Block to transducer constructors (Transducers.map in this example), so the above can be achieved more easily e.g.

Transducers.transduce(Transducers.map(:succ),   appender, [], 0..9)
#=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Transducers.transduce(Transducers.map {|n|n+1}, appender, [], 0..9)
#=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

You can omit the initial value if the reducer (appender in this example) provides one:

def appender.init() [] end
Transducers.transduce(Transducers.map {|n|n+1}, appender, 0..9)
#=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

You can also just pass a Symbol and an initial value instead of a reducer object, and the transduce method will build one for you.

Transducers.transduce(Transducers.map {|n|n+1}, :<<, [], 0..9)
#=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Composition

Imagine that you want to take a range of numbers, select all the even ones, double them, and then take the first 5. Here's one way to do that in Ruby:

(1..100).
  select {|n| n.even?}.
  map    {|n| n * 2}.
  take(5)
#=> [4, 8, 12, 16, 20]

Here's the same process with transducers:

t = Transducers.compose(
      Transducers.filter(:even?),
      Transducers.map {|n| n * 2},
      Transducers.take(5))
Transducers.transduce(t, :<<, [], 1..100)
#=> [4, 8, 12, 16, 20]

Now that we've defined the transducer as a series of transformations, we can apply it to different contexts, e.g.

Transducers.transduce(t, :+, 0, 1..100)
#=> 60
Transducers.transduce(t, :*, 1, 1..100)
#=> 122880

Defined Under Namespace

Classes: BaseTransducer, ComposedTransducer, PreservingReduced, RandomSampleHandler, Reduced, Reducer, WrappingReducer

Class Method Summary collapse

Class Method Details

.cat ⇒ Transducer

Returns:

  • (Transducer) 


586
587
588
589
590
591
592
 
# File 'lib/transducers.rb', line 586

define_transducer_class :cat do
  define_reducer_class do
    def step(result, input)
      Transducers.transduce(PreservingReduced.new, @reducer, result, input)
    end
  end
end

.compose(*transducers) ⇒ Transducer

Returns:

  • (Transducer) 


606
607
608
 
# File 'lib/transducers.rb', line 606

def compose(*transducers)
  ComposedTransducer.new(*transducers)
end

.dedupe ⇒ Transducer

Returns:

  • (Transducer) 


473
474
475
476
477
478
479
480
481
482
483
484
485
486
 
# File 'lib/transducers.rb', line 473

define_transducer_class :dedupe do
  define_reducer_class do
    def initialize(*)
      super
      @prior = :no_value_provided_for_transducer
    end

    def step(result, input)
      ret = input == @prior ? result : @reducer.step(result, input)
      @prior = input
      ret
    end
  end
end

.define_transducer_class(name, &block) ⇒ Object 



252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
 
# File 'lib/transducers.rb', line 252

def self.define_transducer_class(name, &block)
  t = Class.new(BaseTransducer)
  t.class_eval(&block)
  unless t.instance_methods.include? :apply
    t.class_eval do
      define_method :apply do |reducer|
        reducer_class.new(reducer, @handler, &@block)
      end
    end
  end

  Transducers.send(:define_method, name) do |handler=nil, &b|
    t.new(handler, &b)
  end

  Transducers.send(:module_function, name)
end

.drop(n) ⇒ Transducer

Returns:

  • (Transducer) 


434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
 
# File 'lib/transducers.rb', line 434

define_transducer_class :drop do
  define_reducer_class do
    def initialize(reducer, n)
      super(reducer)
      @n = n
    end

    def step(result, input)
      @n -= 1
      @n <= -1 ? @reducer.step(result, input) : result
    end
  end

  def initialize(n)
    @n = n
  end

  def apply(reducer)
    reducer_class.new(reducer, @n)
  end
end

.drop_while(handler = nil, &block) ⇒ Transducer

Parameters:

  • handler (Object, Symbol) (defaults to: nil) —

    Given an object that responds to +process+, uses it as the handler. Given a +Symbol+, builds a handler whose +process+ method will send +Symbol+ to its argument.

  • block (Block) —

    (optional) Given a +Block+, builds a handler whose +process+ method will call the block with its argument(s).

Returns:

  • (Transducer) 


457
458
459
460
461
462
463
464
465
466
467
468
469
 
# File 'lib/transducers.rb', line 457

define_transducer_class :drop_while do
  define_reducer_class do
    def initalize(*)
      super
      @done_dropping = false
    end

    def step(result, input)
      @done_dropping ||= !@handler.call(input)
      @done_dropping ? @reducer.step(result, input) : result
    end
  end
end

.filter(handler = nil, &block) ⇒ Transducer

Parameters:

  • handler (Object, Symbol) (defaults to: nil) —

    Given an object that responds to +process+, uses it as the handler. Given a +Symbol+, builds a handler whose +process+ method will send +Symbol+ to its argument.

  • block (Block) —

    (optional) Given a +Block+, builds a handler whose +process+ method will call the block with its argument(s).

Returns:

  • (Transducer) 


292
293
294
295
296
297
298
 
# File 'lib/transducers.rb', line 292

define_transducer_class :filter do
  define_reducer_class do
    def step(result, input)
      @handler.call(input) ? @reducer.step(result, input) : result
    end
  end
end

.keep(handler = nil, &block) ⇒ Transducer

Parameters:

  • handler (Object, Symbol) (defaults to: nil) —

    Given an object that responds to +process+, uses it as the handler. Given a +Symbol+, builds a handler whose +process+ method will send +Symbol+ to its argument.

  • block (Block) —

    (optional) Given a +Block+, builds a handler whose +process+ method will call the block with its argument(s).

Returns:

  • (Transducer) 


405
406
407
408
409
410
411
412
 
# File 'lib/transducers.rb', line 405

define_transducer_class :keep do
  define_reducer_class do
    def step(result, input)
      x = @handler.call(input)
      x.nil? ? result : @reducer.step(result, x)
    end
  end
end

.keep_indexed(handler = nil, &block) ⇒ Transducer

Note:

the handler for this method requires two arguments: the index and the input.

Parameters:

  • handler (Object, Symbol) (defaults to: nil) —

    Given an object that responds to +process+, uses it as the handler. Given a +Symbol+, builds a handler whose +process+ method will send +Symbol+ to its argument.

  • block (Block) —

    (optional) Given a +Block+, builds a handler whose +process+ method will call the block with its argument(s).

Returns:

  • (Transducer) 


417
418
419
420
421
422
423
424
425
426
427
428
429
430
 
# File 'lib/transducers.rb', line 417

define_transducer_class :keep_indexed do
  define_reducer_class do
    def initialize(*)
      super
      @index = -1
    end

    def step(result, input)
      @index += 1
      x = @handler.call(@index, input)
      x.nil? ? result : @reducer.step(result, x)
    end
  end
end

.map(handler = nil, &block) ⇒ Transducer

Returns a transducer that adds a map transformation to the reducer stack.

Parameters:

  • handler (Object, Symbol) (defaults to: nil) —

    Given an object that responds to +process+, uses it as the handler. Given a +Symbol+, builds a handler whose +process+ method will send +Symbol+ to its argument.

  • block (Block) —

    (optional) Given a +Block+, builds a handler whose +process+ method will call the block with its argument(s).

Returns:

  • (Transducer) 


282
283
284
285
286
287
288
289
 
# File 'lib/transducers.rb', line 282

define_transducer_class :map do
  define_reducer_class do
    # Can I doc this?
    def step(result, input)
      @reducer.step(result, @handler.call(input))
    end
  end
end

.mapcat(handler = nil, &block) ⇒ Transducer

Returns:

  • (Transducer) 


611
612
613
 
# File 'lib/transducers.rb', line 611

def mapcat(handler=nil, &block)
  compose(map(handler, &block), cat)
end

.partition_all ⇒ Transducer

Returns:

  • (Transducer) 


529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
 
# File 'lib/transducers.rb', line 529

define_transducer_class :partition_all do
  define_reducer_class do
    def initialize(reducer, n)
      super(reducer)
      @n = n
      @a = []
    end

    def step(result, input)
      @a << input
      if @a.size == @n
        a = @a.dup
        @a.clear
        @reducer.step(result, a)
      else
        result
      end
    end

    def complete(result)
      if @a.empty?
        result
      else
        a = @a.dup
        @a.clear
        @reducer.step(result, a)
      end
    end
  end

  def initialize(n)
    @n = n
  end

  def apply(reducer)
    reducer_class.new(reducer, @n)
  end
end

.partition_by ⇒ Transducer

Returns:

  • (Transducer) 


490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
 
# File 'lib/transducers.rb', line 490

define_transducer_class :partition_by do
  define_reducer_class do
    def initialize(*)
      super
      @a = []
      @prev_val = :no_value_provided_for_transducer
    end

    def complete(result)
      result = if @a.empty?
                 result
               else
                 a = @a.dup
                 @a.clear
                 @reducer.step(result, a)
               end
      @reducer.complete(result)
    end

    def step(result, input)
      prev_val = @prev_val
      val = @handler.call(input)
      @prev_val = val
      if val == prev_val || prev_val == :no_value_provided_for_transducer
        @a << input
        result
      else
        a = @a.dup
        @a.clear
        ret = @reducer.step(result, a)
        @a << input unless (Reduced === ret)
        ret
      end
    end
  end
end

.random_sample(prob) ⇒ Transducer

Returns:

  • (Transducer) 


580
581
582
 
# File 'lib/transducers.rb', line 580

def random_sample(prob)
  filter RandomSampleHandler.new(prob)
end

.remove(handler = nil, &block) ⇒ Transducer

Parameters:

  • handler (Object, Symbol) (defaults to: nil) —

    Given an object that responds to +process+, uses it as the handler. Given a +Symbol+, builds a handler whose +process+ method will send +Symbol+ to its argument.

  • block (Block) —

    (optional) Given a +Block+, builds a handler whose +process+ method will call the block with its argument(s).

Returns:

  • (Transducer) 


301
302
303
304
305
306
307
 
# File 'lib/transducers.rb', line 301

define_transducer_class :remove do
  define_reducer_class do
    def step(result, input)
      @handler.call(input) ? result : @reducer.step(result, input)
    end
  end
end

.replace(source_map) ⇒ Transducer

Returns:

  • (Transducer) 


374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
 
# File 'lib/transducers.rb', line 374

define_transducer_class :replace do
  define_reducer_class do
    def initialize(reducer, smap)
      super(reducer)
      @smap = smap
    end

    def step(result, input)
      if @smap.has_key?(input)
        @reducer.step(result, @smap[input])
      else
        @reducer.step(result, input)
      end
    end
  end

  def initialize(smap)
    @smap = case smap
            when Hash
              smap
            else
              (0...smap.size).zip(smap).to_h
            end
  end

  def apply(reducer)
    reducer_class.new(reducer, @smap)
  end
end

.take(n) ⇒ Transducer

Returns:

  • (Transducer) 


311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
 
# File 'lib/transducers.rb', line 311

define_transducer_class :take do
  define_reducer_class do
    def initialize(reducer, n)
      super(reducer)
      @n = n
    end

    def step(result, input)
      @n -= 1
      ret = @reducer.step(result, input)
      @n > 0 ? ret : Reduced.new(ret)
    end
  end

  def initialize(n)
    @n = n
  end

  def apply(reducer)
    reducer_class.new(reducer, @n)
  end
end

.take_nth(n) ⇒ Transducer

Returns:

  • (Transducer) 


345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
 
# File 'lib/transducers.rb', line 345

define_transducer_class :take_nth do
  define_reducer_class do
    def initialize(reducer, n)
      super(reducer)
      @n = n
      @count = 0
    end

    def step(result, input)
      @count += 1
      if @count % @n == 0
        @reducer.step(result, input)
      else
        result
      end
    end
  end

  def initialize(n)
    @n = n
  end

  def apply(reducer)
    reducer_class.new(reducer, @n)
  end
end

.take_while(handler = nil, &block) ⇒ Transducer

Parameters:

  • handler (Object, Symbol) (defaults to: nil) —

    Given an object that responds to +process+, uses it as the handler. Given a +Symbol+, builds a handler whose +process+ method will send +Symbol+ to its argument.

  • block (Block) —

    (optional) Given a +Block+, builds a handler whose +process+ method will call the block with its argument(s).

Returns:

  • (Transducer) 


335
336
337
338
339
340
341
 
# File 'lib/transducers.rb', line 335

define_transducer_class :take_while do
  define_reducer_class do
    def step(result, input)
      @handler.call(input) ? @reducer.step(result, input) : Reduced.new(result)
    end
  end
end

.transduce(transducer, reducer, coll) ⇒ Object .transduce(transducer, reducer, init, coll) ⇒ Object

Parameters:

  • transducer (Transducer)
  • reducer (Reducer, Symbol, Bock) 


231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
 
# File 'lib/transducers.rb', line 231

def transduce(transducer, reducer, init=:no_init_provided, coll)
  reducer = Reducer.new(init, reducer) unless reducer.respond_to?(:step)
  reducer = transducer.apply(reducer)
  result = init == :no_init_provided ? reducer.init : init
  case coll
  when Enumerable
    coll.each do |input|
      result = reducer.step(result, input)
      return result.val if Transducers::Reduced === result
      result
    end
  when String
    coll.each_char do |input|
      result = reducer.step(result, input)
      return result.val if Transducers::Reduced === result
      result
    end
  end
  reducer.complete(result)
end