Mozokreduce
Есть мнение, что reduce -- это fold
l , а не fold
r .
Если допустить использование foldl, то задача становится совсем по-детски тривиальной:
1.
Hugs> foldl (\x y -> y:x) [] [ 1 , 2 , 3 , 4 ]
[ 4 , 3 , 2 , 1 ]
Частично предположение об аналогии с foldl подтверждается исходниками clisp 2.48.
clisp-2.48/src/sequence.d
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
/*
...
UPD (lambda (seq pointer) ...) -> pointer
returns a pointer to the adjacent neighbor at the right.
SEQ-UPD can assume, that the right border of
SEQ is not stepped over.
...
INIT-START (lambda (seq index) ...) -> pointer
returns a pointer which moves in SEQ from left to right
from Position index. Must execute the Range-test by itself.
...
*/
...
LISPFUN(reduce,seclass_default, 2 , 0 ,norest,key, 5 ,
(kw(from_end),kw(start),kw(end),kw(key),kw(initial_value)) )
{ /* (REDUCE function sequence [:from-end] [:start] [:end] [:key]
[:initial-value]), CLTL p. 251, CLTL2 p. 397
Stack layout: function, sequence, from-end, start, end, key, initial-value. */
...
/* Stack layout: function, seq, from-end, start, end, key, initial-value,
typdescr, count, pointer, value. */
do {
/* Calculate next value: */
pushSTACK(STACK_( 5 + 4 )); pushSTACK(STACK_( 1 + 1 ));
funcall(seq_access(STACK_( 3 + 2 )), 2 ); /* (SEQ-ACCESS seq pointer) */
funcall_key(STACK_( 1 + 4 ),value1); /* (FUNCALL key (SEQ-ACCESS seq pointer)) */
pushSTACK(STACK_0); pushSTACK(value1);
funcall(STACK_( 6 + 4 + 2 ), 2 ); /* (FUNCALL fun value (FUNCALL key (SEQ-ACCESS seq pointer))) */
STACK_0 = value1; /* =: value */
into_fromstart_loop:
/* Advance pointer: */
pointer_update(STACK_1,STACK_( 5 + 4 ),STACK_3);
/* count := (1- count) : */
decrement(STACK_2);
} while (!eq(STACK_2,Fixnum_0)); /* count (an integer) = 0 ? */
VALUES1(popSTACK()); /* return value */
skipSTACK( 7 + 3 );
}
}
"Частично" -- потому что тут цикл, а не рекурсия. В Prelude.hs же определение foldl явно рекурсивно:
Prelude.hs
1.
2.
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
хотя, конечно, будучи хвостовым, соптимизируется в цикл, но всё же.
umniaxa, операторы (двуместные функции) ($) и (.) определены в Prelude.hs:
Prelude.hs
1.
2.
3.
4.
5.
($) :: (a -> b) -> a -> b
f $ x = f x
...
(.) :: (b -> c) -> (a -> b) -> (a -> c)
(f . g) x = f (g x)
Это аппликация и композиция соответственно.
