First-class functions
You are encouraged to solve this task according to the task description, using any language you may know.
According to wp:First-class functions, a language has first class functions if:
- New functions can be created from others at run time
- Functions can be stored in other collection types of the language
- Functions can be used as arguments to other functions
- Functions can be returned as the value of functions.
The above to be accomplished without invoking a compiler or eval/exec or metaprogramming from the main program.
Write a program to create an ordered collection of a mixture of built-in and user defined functions of a real number, together with another ordered collection of their inverses. Try and use sin, asin, cos, acos, and cube, cube-root as the functions. Create a function compose, (as in Functional Composition problem) that given two functions as arguments returns a new function that applies first the second argument to compose to its argument, then the first argument to compose to the result, i.e:
composed_function = compose(f,g) where composed_function(x) == compose(f,g)(x) == f(g(x))
Applying the compose of a function and its inverse from the two ordered collections of functions in pairs, show that the result in each case is the original value.
The Python example conforms to the above.
ALGOL 68
Note: Returning PROC (REAL x)REAL: f1(f2(x)) from a function apparently
violates standard ALGOL 68's scoping rules. ALGOL 68G warns about this during
parsing, and then - if run out of scope - rejects during runtime.
<lang algol>MODE F = PROC (REAL)REAL;
OP ** = (REAL x, power)REAL: exp(ln(x)*power);
- Add a user defined function and its inverse #
PROC cube = (REAL x)REAL: x * x * x; PROC cube root = (REAL x)REAL: x ** (1/3);
- First class functions allow run-time creation of functions from functions #
- return function compose(f,g)(x) == f(g(x)) #
PROC non standard compose = (F f1, f2)F: (REAL x)REAL: f1(f2(x)); # eg ELLA ALGOL 68RS # PROC compose = (F f, g)F: ((F f2, g2, REAL x)REAL: f2(g2(x)))(f, g, );
- Or the classic "o" functional operator #
PRIO O = 5; OP (F,F)F O = compose;
- first class functions should be able to be members of collection types #
[]F func list = (sin, cos, cube); []F arc func list = (arc sin, arc cos, cube root);
- Apply functions from lists as easily as integers #
FOR index TO UPB func list DO
STRUCT(F f, inverse f) this := (func list[index], arc func list[index]); print(((inverse f OF this O f OF this)(.5), new line))
OD </lang> Output:
+.500000000000000e +0 +.500000000000000e +0 +.500000000000000e +0
D
D 2.0 version of compose function (template). <lang D>
import std.stdio; import std.math;
T delegate(S) compose(T, U, S)(T delegate(U) f, U delegate(S) g) {
return (S s) { return f(g(s)); };
}
</lang>
Compose working both in D 1.0 and 2.0: <lang D>
T delegate(S) compose(T, U, S)(T delegate(U) f, U delegate(S) g) {
struct Wrapper {
typeof(f) fcp;
typeof(g) gcp;
T foobar(S s) { return fcp(gcp(s)); }
}
Wrapper* hold = new Wrapper;
hold.fcp = f;
hold.gcp = g;
return &hold.foobar;
}
</lang>
Example:
<lang D>
void main()
{
auto sinwrp = delegate (real x){ return sin(x);};
auto coswrp = delegate (real x){ return cos(x);};
auto sincos_n = delegate (real x) { return sin(cos(x)); };
auto sincos_r = compose(sinwrp, coswrp);
auto funcTbl = cast(real delegate(real) [])[sinwrp, coswrp, sincos_n, sincos_r];
for (int i = 1; i <= 10; i++) {
real arg = (i*2.0*PI) / 10.0;
foreach (f; funcTbl)
writef ("%10f ", f(arg));
writefln("");
}
}
</lang>
E
First, a brief summary of the relevant semantics: In E, every value, including built-in and user-defined functions, "is an object" — it has methods which respond to messages. Methods are distinguished by the given name (verb) and the number of parameters (arity). By convention and syntactic sugar, a function is an object which has a method whose verb is "run".
The relevant mathematical operations are provided as methods on floats, so the first thing we must do is define them as functions.
<lang e>def sin(x) { return x.sin() } def cos(x) { return x.cos() } def asin(x) { return x.asin() } def acos(x) { return x.acos() } def cube(x) { return x ** 3 } def curt(x) { return x ** (1/3) }
def forward := [sin, cos, cube] def reverse := [asin, acos, curt]</lang>
There are no built-in functions in this list, since the original author couldn't easily think of any which had one parameter and were inverses of each other, but composition would work just the same with them.
Defining composition. fn params { expr } is shorthand for an anonymous function returning a value.
<lang e>def compose(f, g) {
return fn x { f(g(x)) }
}</lang>
<lang e> ? def x := 0.5 \ > for i => f in forward { > def g := reverse[i] > println(`x = $x, f = $f, g = $g, compose($f, $g)($x) = ${compose(f, g)(x)}`) > }
x = 0.5, f = <sin>, g = <asin>, compose(<sin>, <asin>)(0.5) = 0.5 x = 0.5, f = <cos>, g = <acos>, compose(<cos>, <acos>)(0.5) = 0.4999999999999999 x = 0.5, f = <cube>, g = <curt>, compose(<cube>, <curt>)(0.5) = 0.5000000000000001</lang>
Note: def g := reverse[i] is needed here because E as yet has no defined protocol for iterating over collections in parallel. Page for this issue.
Forth
<lang forth>
- compose ( xt1 xt2 -- xt3 )
>r >r :noname
r> compile,
r> compile,
postpone ;
- cube fdup fdup f* f* ;
- cuberoot 1e 3e f/ f** ;
- table create does> swap cells + @ ;
table fn ' fsin , ' fcos , ' cube , table inverse ' fasin , ' facos , ' cuberoot ,
- main
3 0 do i fn i inverse compose ( xt ) 0.5e execute f. loop ;
main \ 0.5 0.5 0.5 </lang>
Groovy
Solution: <lang groovy>def compose = { f, g -> { x -> f(g(x)) } }</lang>
Test program: <lang groovy>def cube = { it * it * it } def cubeRoot = { it ** (1/3) }
funcList = [ Math.&sin, Math.&cos, cube ] funcListI = [ Math.&asin, Math.&acos, cubeRoot ]
println GroovyCollections.transpose( [funcList, funcListI] ).collect { compose(it[0],it[1]) }.collect{ it(0.5) } println GroovyCollections.transpose( [funcListI, funcList] ).collect { compose(it[0],it[1]) }.collect{ it(0.5) }</lang>
Output:
[0.5, 0.4999999999999999, 0.5000000000346574] [0.5, 0.4999999999999999, 0.5000000000346574]
Haskell
<lang haskell>Prelude> let cube x = x ^ 3 Prelude> let croot x = x ** (1/3) Prelude> let compose f g = \x -> f (g x) -- this is already implemented in Haskell as the "." operator Prelude> -- we could have written "let compose f g x = f (g x)" but we show this for clarity Prelude> let funclist = [sin, cos, cube] Prelude> let funclisti = [asin, acos, croot] Prelude> zipWith (\f inversef -> (compose inversef f) 0.5) funclist funclisti [0.5,0.4999999999999999,0.5] </lang>
JavaScript
<lang javascript> compose(f,g) { return function(x) { return f(g(x)) } }
var fn = [Math.sin, Math.cos, function(x) { return x*x*x }] var inv = [Math.asin, Math.acos, function(x) { return Math.pow(x, 1/3) }]
test() {
for (var i=0; i<3; i++) {
var fn = compose(inv[i], fn[i])
print(fn(0.5)) // 0.5
}
} </lang>
OCaml
<lang ocaml># let cube x = x ** 3.;; val cube : float -> float = <fun>
- let croot x = x ** (1. /. 3.);;
val croot : float -> float = <fun>
- let compose f g = fun x -> f (g x);; (* we could have written "let compose f g x = f (g x)" but we show this for clarity *)
val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
- let funclist = [sin; cos; cube];;
val funclist : (float -> float) list = [<fun>; <fun>; <fun>]
- let funclisti = [asin; acos; croot];;
val funclisti : (float -> float) list = [<fun>; <fun>; <fun>]
- List.map2 (fun f inversef -> (compose inversef f) 0.5) funclist funclisti;;
- : float list = [0.5; 0.499999999999999889; 0.5] </lang>
Octave
<lang octave>function r = cube(x)
r = x.^3;
endfunction
function r = croot(x)
r = x.^(1/3);
endfunction
compose = @(f,g) @(x) f(g(x));
f1 = {@sin, @cos, @cube}; f2 = {@asin, @acos, @croot};
for i = 1:3
disp(compose(f1{i}, f2{i})(.5))
endfor</lang>
Perl
<lang perl>use Math::Complex ':trig';
my $cube = sub {shift()**3}; my $croot = sub {shift()**(1/3)};
sub compose
{my ($f, $g) = @_;
return sub {$f->($g->(@_));};}
my @flist1 = (\&Math::Complex::sin, \&Math::Complex::cos, $cube); my @flist2 = (\&asin, \&acos, $croot);
foreach (0 .. $#flist1)
{print compose($flist1[$_], $flist2[$_])->(.5), "\n";}</lang>
Python
Python 2.X <lang python>>>> #some built in functions and their inverses >>> from math import sin, cos, acos, asin >>> # Add a user defined function and its inverse >>> cube = lambda x: x * x * x >>> croot = lambda x: x ** (1/3.0) >>> # First class functions allow run-time creation of functions from functions >>> # return function compose(f,g)(x) == f(g(x)) >>> compose = lambda f1, f2: ( lambda x: f1(f2(x)) ) >>> # first class functions should be able to be members of collection types >>> funclist = [sin, cos, cube] >>> funclisti = [asin, acos, croot] >>> # Apply functions from lists as easily as integers >>> [compose(inversef, f)(.5) for f, inversef in zip(funclist, funclisti)] [0.5, 0.49999999999999989, 0.5] >>> </lang>
Ruby
<lang ruby>irb(main):001:0> cube = proc {|x| x ** 3} => #<Proc:0xb7cac4b8@(irb):1> irb(main):002:0> croot = proc {|x| x ** (1/3.0)} => #<Proc:0xb7ca40d8@(irb):2> irb(main):003:0> compose = proc {|f,g| proc {|x| f[g[x]]}} => #<Proc:0xb7c9996c@(irb):3> irb(main):004:0> funclist = [Math.method(:sin).to_proc, Math.method(:cos).to_proc, cube] => [#<Proc:0xb7c84be8@(irb):4>, #<Proc:0xb7c84bac@(irb):4>, #<Proc:0xb7cac4b8@(irb):1>] irb(main):005:0> funclisti = [Math.method(:asin).to_proc, Math.method(:acos).to_proc, croot] => [#<Proc:0xb7c7a88c@(irb):5>, #<Proc:0xb7c7a850@(irb):5>, #<Proc:0xb7ca40d8@(irb):2>] irb(main):006:0> funclist.zip(funclisti).map {|f,inversef| compose[inversef, f][0.5] } => [0.5, 0.5, 0.5] </lang>
Smalltalk
<lang smalltalk>|forward reverse composer compounds| "commodities" Number extend [
cube [ ^self raisedTo: 3 ]
]. Number extend [
cubeRoot [ ^self raisedTo: (1 / 3) ]
].
forward := #( #cos #sin #cube ). reverse := #( #arcCos #arcSin #cubeRoot ).
composer := [ :f :g | [ :x | f value: (g value: x) ] ].
"let us create composed funcs" compounds := OrderedCollection new.
1 to: 3 do: [ :i |
compounds add: ([ :j | composer value: [ :x | x perform: (forward at: j) ]
value: [ :x | x perform: (reverse at: j) ] ] value: i)
].
compounds do: [ :r | (r value: 0.5) displayNl ].</lang>
Output:
0.4999999999999999 0.5 0.5000000000000001
Standard ML
<lang sml>- fun cube x = Math.pow(x, 3.0); val cube = fn : real -> real - fun croot x = Math.pow(x, 1.0 / 3.0); val croot = fn : real -> real - fun compose (f, g) = fn x => f (g x); (* this is already implemented in Standard ML as the "o" operator = we could have written "fun compose (f, g) x = f (g x)" but we show this for clarity *) val compose = fn : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b - val funclist = [Math.sin, Math.cos, cube]; val funclist = [fn,fn,fn] : (real -> real) list - val funclisti = [Math.asin, Math.acos, croot]; val funclisti = [fn,fn,fn] : (real -> real) list - ListPair.map (fn (f, inversef) => (compose (inversef, f)) 0.5) (funclist, funclisti); val it = [0.5,0.5,0.500000000001] : real list </lang>
Tcl
The following is a transcript of a session with an interactive tclsh (8.5 or better). <lang Tcl>% namespace path tcl::mathfunc ;# to import functions like abs() etc. % proc cube x {expr {$x**3}} % proc croot x {expr {$x**(1/3.)}} % proc compose {f g} {list apply {{f g x} {{*}$f [{*}$g $x]}} $f $g}
% compose abs cube ;# returns a partial command, without argument apply {{f g x} {{*}$f [{*}$g $x]}} abs cube
% {*}[compose abs cube] -3 ;# applies the partial command to argument -3 27
% set forward [compose [compose sin cos] cube] ;# omitting to print result % set backward [compose croot [compose acos asin]] % {*}$forward 0.5 0.8372297964617733 % {*}$backward [{*}$forward 0.5] 0.5000000000000017</lang>