Accumulator factory
From Rosetta Code
You are encouraged to solve this task according to the task description, using any language you may know.
A problem posed by Paul Graham is that of creating a function that takes a single (numeric) argument and which returns another function that is an accumulator. The returned accumulator function in turn also takes a single numeric argument, and returns the sum of all the numeric values passed in so far to that accumulator (including the initial value passed when the accumulator was created).
The detailed rules are at http://paulgraham.com/accgensub.html and are reproduced here for simplicity (with additions in small italic text).
- Before you submit an example, make sure the function
- Takes a number n and returns a function (lets call it g), that takes a number i, and returns n incremented by the accumulation of i from every call of function g(i).
Although these exact function and parameter names need not be used - Works for any numeric type-- i.e. can take both ints and floats and returns functions that can take both ints and floats. (It is not enough simply to convert all input to floats. An accumulator that has only seen integers must return integers.) (i.e., if the language doesn't allow for numeric polymorphism, you have to use overloading or something like that)
- Generates functions that return the sum of every number ever passed to them, not just the most recent. (This requires a piece of state to hold the accumulated value, which in turn means that pure functional languages can't be used for this task.)
- Returns a real function, meaning something that you can use wherever you could use a function you had defined in the ordinary way in the text of your program. (Follow your language's conventions here.)
- Doesn't store the accumulated value or the returned functions in a way that could cause them to be inadvertantly modified by other code. (No global variables or other such things.)
- Takes a number n and returns a function (lets call it g), that takes a number i, and returns n incremented by the accumulation of i from every call of function g(i).
- E.g. if after the example, you added the following code (in a made-up language) where the factory function is called foo:
-
x = foo(1);
x(5);
foo(3);
print x(2.3);
-
- It should print 8.3. (There is no need to print the form of the accumulator function returned by foo(3); it's not part of the task at all.)
The purpose of this task is to create a function that implements the described rules. It need not handle any special error cases not described above. The simplest way to implement the task as described is typically to use a closure, providing the language supports them.
Where it is not possible to hold exactly to the constraints above, describe the deviations.
[edit] ActionScript
Closures work the same in ActionScript as in JavaScript. ActionScript will transparently convert integers to reals if the function is given a real argument, but the typeof operator must be used to ensure the function isn't sent invalid arguments, such as strings (which would silently convert the accumulated number to a string without throwing an error).
Translation of: Javascript
//Throw an error if a non-number argument is used. (typeof evaluates to
// "number" for both integers and reals)
function checkType(obj:Object):void {
if(typeof obj != "number")
throw new ArgumentError("Expected integer or float argument. Recieved " + typeof obj);
}
function accumulator(sum:Object):Function {
checkType(sum);
return function(n:Object):Object {checkType(n); return sum += n};
}
var acc:Function=accumulator(2);
trace(acc(10));
trace(acc(4));
trace(acc("123")); //This causes an ArgumentError to be thrown.
[edit] Aikido
Translation of: Javascript
function accumulator (sum:real) {
return function(n:real) { return sum += n }
}
var x = accumulator(1)
x(5)
println (accumulator)
println (x(2.3))
Output:
accumulator 8.3
[edit] ALGOL 68
Translation of: aikido
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d
Note: Standard ALGOL 68's scoping rules forbids exporting a procedure (or format) out of it's scope (closure). Hence this specimen will run on ELLA ALGOL 68, but is non-standard. For a discussion of first-class functions in ALGOL 68 consult "The Making of Algol 68" - C.H.A. Koster (1993).
MODE NUMBER = UNION(INT,REAL,COMPL);
PROC plus = (NUMBER in a, in b)NUMBER: (
CASE in a IN
(INT a): CASE in b IN (INT b): a+b, (REAL b): a+b, (COMPL b): a+b ESAC,
(REAL a): CASE in b IN (INT b): a+b, (REAL b): a+b, (COMPL b): a+b ESAC,
(COMPL a): CASE in b IN (INT b): a+b, (REAL b): a+b, (COMPL b): a+b ESAC
ESAC
);
main: (
# now override the + and +:= OPerators #
OP + = (NUMBER a, b)NUMBER: plus(a,b);
OP +:= = (REF NUMBER lhs, NUMBER rhs)NUMBER:
lhs := lhs + rhs;
PROC accumulator = (REF NUMBER sum)PROC(NUMBER)NUMBER:
(NUMBER n)NUMBER:
sum +:= n;
PROC (NUMBER)NUMBER x = accumulator(LOC NUMBER := 1);
x(5);
print(("x:",x(2.3), new line));
PROC (NUMBER)NUMBER y = accumulator(LOC NUMBER := 100);
y(500);
print(("y:",y(230), new line));
print(("x:",x(0), new line))
)
Output:
x: +.830000000000000e +1 y: +830 x: +.830000000000000e +1
[edit] Argile
Works with: Argile version 1.1.1
use std, array
let A = accumulator 42
print(A 0)
print(A 1)
print(A 10)
print(A 100)
let B = accumulator 4.2
print(B 0)
print(B 1)
print(B 10.0)
print(B 100.4)
~A ; ~B
(: use dbg; check mem leak :)
(: accumulator call :)
=: <accumulator a> <num x> := -> (a.t)
call ((a.func) as function(any)(a.t)->(a.t)) with (a.data) ((Cgen x) as a.t)
(: accumulator constructors :)
.: accumulator <int x> :. -> int accumulator
(val (int accumulator) A).init(x)
(A as Accumulator).func = ( .:<int& accu, int x>:. ->int {accu += x; accu} )
A
.: accumulator <real x> :. -> real accumulator
(val (real accumulator) A).init(x)
(A as Accumulator).func = ( .:<real&accu,real x>:. ->real{accu += x; accu} )
A
=: <accumulator& a>.init <num x> :=
a = new (Accumulator)
a.data = (new array of 1 a.t)
*(a.data as (a.t*)) = Cgen x
(: accumulator destructor :)
.: del Accumulator <Accumulator a>:.
free a.data
free a
=: ~ <accumulator a> := {del Accumulator a}
(: accumulator type :)
class Accumulator
function func
any data
=: [<type t=(int)>] accumulator := -> type
Accumulator.prefix
Accumulator.suffix
autocast accumulator<->Accumulator
[edit] C++
Deviation: The return type is wrong when the accumulator is called with an integer argument after is has been called with a float argument.
class Acc
{
public:
Acc(int init)
: _type(intType)
, _intVal(init)
{}
Acc(float init)
: _type(floatType)
, _floatVal(init)
{}
int operator()(int x)
{
if( _type == intType )
{
_intVal += x;
return _intVal;
}
else
{
_floatVal += x;
return static_cast<int>(_floatVal);
}
}
float operator()(float x)
{
if( _type == intType )
{
_floatVal = _intVal + x;
_type = floatType;
return _floatVal;
}
else
{
_floatVal += x;
return _floatVal;
}
}
private:
enum {floatType, intType} _type;
float _floatVal;
int _intVal;
};
int main(int argc, char* argv[])
{
Acc a(1);
a(5);
Acc(3);
std::cout << a(2.3f);
return 0;
}
[edit] C#
Library: System.Reflection
[edit] Notes
I am not using properties on purpose to conform to Rule 5. This will accept any of the C# types that implement System.IConvertible. Technically this means that strings, bools, datetimes, and Types are valid objects for accumulation. Thought about using generics to restrict possible values even more, but that would have prevented me from conforming to rule 2 without building some overly complicated mechanism. Probably non-numeric types could be filtered with an if block, throwing an exception if the IConvertible is a non-numeric, but this type of code <wishful_thinking>shouldn't be called in a location where that might be an issue.</wishful_thinking>
[edit] Task Code
using System;
using System.Reflection;
namespace RosettaCode.Tasks
{
public static class Accumulator_Task
{
public delegate IConvertible Accumulator ( IConvertible p_Value );
public static Accumulator StartAccumulation ( IConvertible p_StartValue )
{
double Sum = p_StartValue.ToDouble (null );
TypeCode RetType = p_StartValue.GetTypeCode ( );
return delegate ( IConvertible p_ChangeValue )
{
// Convert Everything to a double when storing. Technically System.Decimal is wider, but
// only for precision after the decimal. Decimal precision will be truncated.
Sum += Convert.ToDouble ( p_ChangeValue );
// Convert to a wider data type based on the increasing integer base values for TypeCode
// enum values as data type gets wider
TypeCode NewTypeCode = p_ChangeValue.GetTypeCode ( );
RetType = NewTypeCode > RetType ? NewTypeCode : RetType;
// Reflection is a bit messy sometimes, but still it rocks!
return typeof ( IConvertible )
.GetMethod ( String.Format ( "To{0}", RetType.ToString ( ) ) )
.Invoke ( ( Sum as IConvertible ), new object[ ] { null } ) as IConvertible;
};
}
}
}
[edit] Test Function
namespace RosettaCode.Tasks
{
public class Accumulator_Task
{
// Just a test function
public static void Test ( )
{
Console.WriteLine ( "Accumulator Factory" );
Accumulator X = StartAccumulation ( 1 );
X ( 5 );
StartAccumulation ( 3 );
IConvertible Val = X ( 2.3 );
Console.WriteLine ( "{0} : {1}", Val, Val.GetType ( ) );
}
}
}
[edit] Clojure
The atom function creates an atomically updatable identity holding a value. The swap! function atomically updates the atom's value, returning the new value. The function returned from an accum call satisfies all the requirements.
(defn accum [n]
(let [acc (atom n)]
(fn [m] (swap! acc + m))))
Similarly, a ref could be used.
(defn accum [n]
(let [acc (ref n)]
#(dosync (alter acc + %))))
[edit] Common Lisp
(defun accumulator (sum)
(lambda (n)
(setf sum (+ sum n))))
Example usage:
(defvar x (accumulator 1))
(funcall x 5)
(accumulator 3)
(funcall x 2.3)
This prints:
X 6 #<CLOSURE :LAMBDA (N) (SETF SUM (+ SUM N))> 8.3
[edit] E
def foo(var x) {
return fn y { x += y }
}
[edit] Factor
:: accumulator ( n! -- quot ) [ n + dup n! ] ;
1 accumulator
[ 5 swap call drop ]
[ drop 3 accumulator drop ]
[ 2.3 swap call ] tri .
[edit] Forth
Forth is untyped; this works on integers.
: accumulator
create ( n -- ) ,
does> ( n -- acc+n ) tuck +! @ ;
0 accumulator foo
1 foo . \ 1
2 foo . \ 3
3 foo . \ 6
[edit] F#
A dynamically typed version. Not sure whether a proper statically typed version is possible in F#.
open System
let acc (init:obj) : obj->obj=
let state = ref init
fun (x:obj) ->
if (!state).GetType() = typeof<Int32>
&& x.GetType() = typeof<Int32> then
state := (Convert.ToInt32(!state) + Convert.ToInt32(x)) :> obj
else
state := (Convert.ToDouble(!state) + Convert.ToDouble(x)) :> obj
!state
do
let x : obj -> obj = acc 1 // the type annotation is necessary here
(x 5) |> ignore
(acc 3) |> ignore
printfn "%A" (x 2.3)
[edit] Go
Deviations: This does not fulfill condition 2. The result is a float even if you only use integers.
package main
import "fmt"
func accumulator(sum float64) func(float64) float64 {
return func (n float64) float64 {
sum += n
return sum
}
}
func main() {
x := accumulator(1.0)
x(5.0)
accumulator(3.0)
fmt.Printf("%g\n", x(2.3))
}
outputs
8.3
[edit] Haskell
Translation of: Ruby
import Control.Monad.ST
import Data.STRef
accumulator :: (Num a) => a -> ST s (a -> ST s a)
accumulator sum0 = do
sum <- newSTRef sum0
return $ \n -> do
modifySTRef sum (+ n)
readSTRef sum
main :: IO ()
main = print foo
where foo = runST $ do
x <- accumulator 1
x 5
accumulator 3
x 2.3
outputs
8.3
[edit] Icon and Unicon
[edit] Icon
At first glance you might expect the example below to run under Icon; however, as the co-expression calling sequence is Unicon specific.
[edit] Unicon
Strictly speaking, genAcc(n) returns a co-expression, not a function. However, the invocation syntax here is indistinguishable from calling a function.
procedure main()
a := genAcc(3)
b := genAcc(5)
write(" " ,center("a",5), " ", center("b", 5))
write("genAcc: ", right(a(4),5), " ", right(b(4), 5))
write("genAcc: ", right(a(2),5), " ", right(b(3),5))
write("genAcc: ", right(a(4.5),5)," ", right(b(1.3),5))
end
procedure genAcc(n) # The generator factory
return makeProc { while i := (n@&source)[1] do n +:= i }
end
procedure makeProc(A) # A Programmer-Defined Control Operation
return (@A[1],A[1])
end
This example produces the output:
a b
genAcc: 7 9
genAcc: 9 12
genAcc: 13.5 13.3
[edit] J
See http://www.jsoftware.com/jwiki/Guides/Lexical_Closure
oleg=:1 :0
a=. cocreate''
n__a=: m
a&(4 : 'n__x=: n__x + y')
)
Example use:
F=: 10 oleg F 11 21 F 12 33
[edit] Java
Java has no first-class functions; the standard syntactic workaround is to use a standard method name. Java uses objects to maintain state.
public class Accumulator {
private double sum;
public Accumulator(double sum0) {
sum = sum0;
}
public double call(double n) {
return sum += n;
}
public static void main(String[] args) {
Accumulator x = new Accumulator(1);
x.call(5);
System.out.println(new Accumulator(3));
System.out.println(x.call(2.3));
}
}
outputs
Accumulator@42e816 8.3
To do a full version that sums with integers as long as possible before switching to double-precision floats requires a little more work and the use of the Number class...
Works with: Java version 5.0
public class Accumulator {
private Long sumA; // non-null if we're working in the integer domain
private double sumB;
public Accumulator(Number sum0) {
if (sum0 instanceof Double) {
sumB = sum0.doubleValue();
} else {
sumA = sum0.longValue();
}
}
public Number call(Number n) {
if (sumA != null) {
if (n instanceof Double) {
sumB = n.doubleValue() + sumA;
sumA = null;
return sumB;
}
return sumA += n.longValue();
}
return sumB += n.doubleValue();
}
public static void main(String[] args) {
Accumulator x = new Accumulator(1);
x.call(5);
Accumulator y = new Accumulator(3);
System.out.println(y+" has value "+y.call(0));
System.out.println(x.call(2.3));
}
}
Producing this sample output:
Accumulator@6100ab23 has value 3 8.3
[edit] JavaScript
Translation of: Ruby
Works with: SpiderMonkey
function accumulator(sum) {
return function(n) {return sum += n}
}
x = accumulator(1);
x(5);
print(accumulator(3));
print(x(2.3));
output
function (n) {
return sum += n;
}
8.3
[edit] Lua
Works with: Lua version 5.1
do
local accSum = 0; -- accumulator factory 'upvalue'
function acc(v) -- the accumulator factory
accSum = accSum + (v or 0) -- increment factory sum
local closuredSum = accSum; -- new 'upvalue' at each factory call
return function (w) -- the produced accumulator function
closuredSum = closuredSum + (w or 0) -- increment product 'upvalue'
return closuredSum -- return 'upvalue'
end, accSum -- end of product closure
end--acc
end--end of factory closure
Usage example:
x = acc(1) -- x stores the product with initial value = 1
x(5) -- add 5 to x's sum
acc(3) -- add 3 to factory's sum
print (x(2.3)) --> 8.3 -- add 2.3 to x's sum then print the result
y = acc() -- create new function with factory's sum as initial value
print (y()) --> 4 -- print the accumulated value inside the product y
[edit] Mathematica
accFactory[initial_] :=
Module[{total = initial},
Function[x, total += x]
]
x=accFactory[1];
x[5.0];
accFactory[3];
x[2.3]
outputs
8.3
[edit] OCaml
Translation of: Ruby
Deviations: An accumulator instance can take either integers or floats, but not both mixed (due to lack of runtime polymorphism).
let accumulator sum0 =
let sum = ref sum0 in
fun n ->
sum := !sum +. n;
!sum;;
let _ =
let x = accumulator 1.0 in
ignore (x 5.0);
let _ = accumulator 3.0 in
Printf.printf "%g\n" (x 2.3)
;;
outputs
8.3
[edit] Oz
A bit unwieldy because the '+' operator does not allow mixed type operands. The implementation is thread-safe (atomic Exchange operation).
declare
fun {Acc Init}
State = {NewCell Init}
in
fun {$ X}
OldState
in
{Exchange State OldState} = {Sum OldState X}
end
end
fun {Sum A B}
if {All [A B] Int.is} then A+B
else {ToFloat A}+{ToFloat B}
end
end
fun {ToFloat X}
if {Float.is X} then X
elseif {Int.is X} then {Int.toFloat X}
end
end
X = {Acc 1}
in
{X 5 _}
{Acc 3 _}
{Show {X 2.3}}
[edit] Perl
Translation of: Ruby
sub accumulator {
my $sum = shift;
sub { $sum += shift }
}
my $x = accumulator(1);
$x->(5);
print accumulator(3), "\n";
print $x->(2.3), "\n";
outputs
CODE(0x91131f0) 8.3
[edit] Perl 6
Works with: Rakudo version #23 "Lisbon"
sub accum ($n is copy) { sub { $n += $^x } }
Example use:
my $a = accum 5;
$a(4.5);
say $a(.5); # Prints "10".
[edit] PHP
<?
function accumulator($start){
return create_function('$x','static $v='.$start.';return $v+=$x;');
}
$acc=accumulator(5);
echo $acc(5); //prints 10
echo $acc(10); //prints 20
?>
[edit] PicoLisp
(de accumulator (Sum)
(curry (Sum) (N)
(inc 'Sum N) ) )
(def 'a (accumulator 7))
(a 1) # Output: -> 8
(a 2) # Output: -> 10
(a -5) # Output: -> 5
[edit] PostScript
/mk-acc { % accumulator generator
{0 add 0 0 2 index put}
7 array copy
dup 0 4 -1 roll put
dup dup 2 exch put
cvx
} def
% Examples (= is a printing command in PostScript):
/a 1 mk-acc def % create accumulator #1, name it a
5 a = % add 5 to 1, print it
10 mk-acc % create accumulator #2, leave it anonymous on the stack
2.71 a = % add 2.71 to 6, print it
dup 3.14 exch exec = % add 3.14 to 10, print it
dup 100 exch exec = % add 100 to 13.14, print it
12 a = % add 12 to 8.71, print it
% accumulator #2 is still available on the stack
[edit] Python
Works with: Python version 2.x/3.x
>>> def accumulator(sum):
def f(n):
f.sum += n
return f.sum
f.sum = sum
return f
>>> x = accumulator(1)
>>> x(5)
6
>>> x(2.3)
8.3000000000000007
>>> x = accumulator(1)
>>> x(5)
6
>>> x(2.3)
8.3000000000000007
>>> x2 = accumulator(3)
>>> x2(5)
8
>>> x2(3.3)
11.300000000000001
>>> x(0)
8.3000000000000007
>>> x2(0)
11.300000000000001
Translation of: Ruby Works with: Python version 3.x
def accumulator(sum):
def f(n):
nonlocal sum
sum += n
return sum
return f
x = accumulator(1)
x(5)
print(accumulator(3))
print(x(2.3))
outputs
<function f at 0xb7c2d0ac> 8.3
[edit] R
accumulatorFactory <- function(init) {
currentSum <- init
function(add) {
currentSum <<- currentSum + add
currentSum
}
}
outputs
> f <- accumulatorFactory(1) > f(5) [1] 6 > f(2.3) [1] 8.3
[edit] REBOL
make-acc-gen: func [start-val] [outputs
func [value /local state] compose/deep [
state: [(start-val)]
state/1: state/1 + value
state/1
]
]
>> x: make-acc-gen 1 >> x 5 == 6 >> make-acc-gen 3 >> print x 2.3 8.3
[edit] Ruby
Add some output to the 2nd call to "accumulator" to show what it returns
def accumulator(sum)
lambda {|n| sum += n}
end
x = accumulator(1)
x.call(5)
p accumulator(3)
puts x.call(2.3)
outputs
#<Proc:0x1002f14c@accumulator.rb:5> 8.3
[edit] Scala
The type of a function can't change in Scala, and there is no "numeric" type that is a supertype of all such types. So, if the accumulator is declared as integer, it can only receive and return integers, and so on.
def AccumulatorFactory[N](n: N)(implicit num: Numeric[N]) = {
import num._
var acc = n
(inc: N) => {
acc = acc + inc
acc
}
}
Sample:
scala> val x = AccumulatorFactory(1.0) x: (Double) => Double = <function1> scala> x(5.0) res7: Double = 6.0 scala> AccumulatorFactory(3.0) res8: (Double) => Double = <function1> scala> println(x(2.3)) 8.3
[edit] Scheme
Translation of: Ruby
(define (accumulator sum)
(lambda (n)
(set! sum (+ sum n))
sum))
;; or:
(define ((accumulator sum) n)
(set! sum (+ sum n))
sum)
(define x (accumulator 1))
(x 5)
(display (accumulator 3)) (newline)
(display (x 2.3)) (newline)
outputs
#<procedure> 8.3
[edit] Smalltalk
Works with: GNU Smalltalk
Object subclass: AccumulatorFactory [
AccumulatorFactory class >> new: aNumber [
|r sum|
sum := aNumber.
r := [ :a |
sum := sum + a.
sum
].
^r
]
]
|x y|
x := AccumulatorFactory new: 1.
x value: 5.
y := AccumulatorFactory new: 3.
(x value: 2.3) displayNl.
"x inspect."
"de-comment the previous line to show that x is a block closure"
[edit] Tcl
Works with: Tcl version 8.6
This uses nested coroutines to manage the state, which for the outer coroutine is a counter used to generate unique instances of the inner coroutine, and for the inner coroutine it is the actual accumulator variable. Note that Tcl commands (including coroutines) are never nameless, but it is trivial to synthesize a name for them. It's possible to guarantee uniqueness of names, but just using a simple sequence generator gets 90% of the effect for 10% of the effort.
package require Tcl 8.6
# make the creation of coroutines without procedures simpler
proc coro {name arguments body args} {
coroutine $name apply [list $arguments $body] {*}$args
}
# Wrap the feeding of values in and out of a generator
proc coloop {var body} {
set val [info coroutine]
upvar 1 $var v
while 1 {
set v [yield $val]
if {$v eq "stop"} break
set val [uplevel 1 $body]
}
}
# The outer coroutine is the accumulator factory
# The inner coroutine is the particular accumulator
coro accumulator {} {
coloop n {
coro accumulator.[incr counter] n {
coloop i {
set n [expr {$n + $i}]
}
} $n
}
}
Sample usage (extra characters over Paul's example to show more clearly what is going on):
% set x [accumulator 1]
::accumulator.1
% $x 5
6
% accumulator 3
::accumulator.2
% puts ">>[$x 2.3]<<"
>>8.3<<
[edit] Unicon
Strictly speaking, genAcc(n) returns a co-expression, not a function. However, the invocation syntax here is indistinguishable from calling a function.
procedure main()
a := genAcc(3)
b := genAcc(5)
write(" " ,center("a",5), " ", center("b", 5))
write("genAcc: ", right(a(4),5), " ", right(b(4), 5))
write("genAcc: ", right(a(2),5), " ", right(b(3),5))
write("genAcc: ", right(a(4.5),5)," ", right(b(1.3),5))
end
procedure genAcc(n) # The generator factory
return makeProc { while i := (n@&source)[1] do n +:= i }
end
procedure makeProc(A) # A Programmer-Defined Control Operation
return (@A[1],A[1])
end
Note: The co-expression calling sequence used is Unicon specific.
This example produces the output:
a b
genAcc: 7 9
genAcc: 9 12
genAcc: 13.5 13.3
[edit] VBScript
I'm not entirely convinced that this is actually doing what is asked. A VBScript guru I'm not. The answer's right, though.
[edit] Implementation
class accumulator
dim A
public default function acc(x)
A = A + x
acc = A
end function
public property get accum
accum = A
end property
end class
[edit] Invocation
dim a
set a = new accumulator
x = a( 1 )
a 5
dim b
set b = new accumulator
b 3
wscript.echo a(2.3)
[edit] Output
8.3
