Menu
In Kenneth Iversonβs A Programming Language the reduction operation op/ is defined as a foldl (left fold):
The β-reduction of a vector π₯ is denoted by β/π₯ and defined as
zββ/π₯ βΊ z = (β―((π₯β β π₯β) β π₯β) β β― π₯α΅’)
However in modern APLs, it is clearly a right fold (foldr)
{βΊβ΅}/'abcd'
ββββββββββββ
βa βββββββββ
β βb ββββββ
β β βcdβββ
β β ββββββ
β βββββββββ
ββββββββββββ
I wonder when this change has happened (and what was the motivation)?
Perhaps(?) defining β/v merely as vβ β vβ β β― β vβ, which (given APL rules) would parse as foldr does make some sense. On the other hand, implementing efficient foldl is rather easier.
526
fold is a much more valuable function than reduce . You can define many different functions in terms of fold . reduce is just a subset of fold . You define your fold differently from List.
With foldl , the function argument takes a default value, the first element of the list, and returns a new default value. When the list is empty, that default value will be the result of the fold. This is admittedly a simple example.
Haskell : foldl. Description: it takes the second argument and the first item of the list and applies the function to them, then feeds the function with this result and the second argument and so on. See scanl for intermediate results.
A Programming Language is from 1962.
The 1963 paper Programming Notation in Systems Design has the same definition.
The 1964 paper A Common Language for Hardware, Software, and Applications quotes the definition from A Programming Language.
At the very end of the 1966 paper Conventions Governing Order of Evaluation, Iverson wrote:
In the definition
β
F/x β‘ x1 F x2 F x3 F ... F xβ΄x
β
the right-to-left convention leads to a more useful definition for nonassociative functionsFthan does the left-to-right convention. For example,-/xdenotes the alternating sum of the components ofx, whereas in a left-to-right convention it would denote the first component minus the sum of the remaining components. Thus if d is the vector of decimal digits representing the numbern, then the value of the expression0=9|+/ddetermines the divisibility ofnby9; in the right-to-left convention, the similar expression0=11|-/ddetermines divisibility by11.
121
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
