Topic: sequence reduction

topics > computer science > data > Group: sequence operations

processing a sequence
function application
functional programming
reduction machines


A sequence is reduced to a single value by sequential application of an operator. For instance using addition, a sequence of integers is reduced to their total. Reduction can be applied to a sub-sequence, replacing the sub-sequence by its reduced value. With two element sequences, reduction is equivalent to Polish notation, e.g., '+ a b'. is 'a+b'. Sequence reduction is used in APL for control determination and array summation. The mathematical inner product is vector element multiply followed by reduction addition. (cbb 5/80)
Subtopic: beta reduction up

Quote: in CmLisp, .beta. reduction applies a function to the values of a xector in logarithmic time; ignores indices [»hillWD_1985]
Quote: the simplest .beta. reduces a xector to a value; general form reduces portions of xectors and produces a xector [»hillWD_1985]
Quote: the generalized .beta. creates a xector from a value xector, an index xector, and a combining function for duplicates; gives example [»hillWD_1985]
Quote: simple .beta. reduction is the generalized .beta. operation applied to one xector; every value is combined [»hillWD_1985]

Subtopic: summation up

QuoteRef: grayJC_1973 ;;170 dyadic application: eg +!s2 sums all members of s2
QuoteRef: simscrip_1971 ;;68 reduction over a set or collection by e.g., for i=1 to 10, compute total = sum of x(i)

Subtopic: inner product up

QuoteRef: grayJC_1973 ;;170 indirect product of two sets: from all element is set A form a reduction in set B and check number of elements
QuoteRef: mckeWM_1966 ;;114 compression e.g., inner product by +/a*b
QuoteRef: wileDS11_1973 ;;40 accumulate operator / y/s== like APL reduction or evaluate program on one register machine

Subtopic: sub-sequence up

QuoteRef: wileDS11_1973 ;;33 gen operator removes a sub-sequence e.g., <1> conc<2;<3;4>;5> = < <1>gen <2;<3;4>;5>gen? = <1;2;<3;4>;5> and == s

Related Topics up

Topic: histogram (5 items)
Topic: processing a sequence (17 items)
Topic: function application (18 items)
Topic: functional programming (45 items)
Topic: reduction machines
(14 items)

Updated barberCB 1/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.