foldl,foldr

Hugs.Base> foldl (/) 2 [1, 2, 4, 8]
0.03125
Hugs.Base> foldr (/) 2 [1, 2, 4, 8]
0.5

foldl (/) 2 [1, 2, 4, 8] は、(((2 / 1) / 2) / 4) / 8
foldr (/) 2 [1, 2, 4, 8] は、1 / (2 / (4 / (8 / 2)))ということですね。

Hugs.Base> foldl (/) 3 [1, 3, 5, 7, 2, 1]
0.0142857142857143
Hugs.Base> foldr (/) 3 [1, 3, 5, 7, 2, 1]
1.42857142857143

Schemeで書いてみる。Schemeのライブラリ、SRFIのfoldは

> (fold / 2 '(1 2 4 8))
8

これは8 / (4 / (2 / (1 / 2)))になってしまう。自分で書くしかない。

(define (foldl proc elem list)
  (define (foldl-iter list ans)
    (cond ((null? list) ans)
          (#t (foldl-iter (cdr list) (proc ans (car list))))))
  (foldl-iter list elem))

(define (foldr proc elem list)
  (define (foldr-rec list)
    (cond ((null? list) elem)
          (#t (proc (car list) (foldr-rec (cdr list))))))
  (foldr-rec list))

> (foldl / 2.0 '(1 2 4 8))
0.03125
> (foldr / 2.0 '(1 2 4 8))
0.5

> (foldl / 3.0 '(1 3 5 7 2 1 ))
0.014285714285714287
> (foldr / 3.0 '(1 3 5 7 2 1 ))
1.4285714285714284

いい感じに頭がこんがらがってきました。

次は Pythonで。

def foldl(proc, elem, lis):
    lis.insert(0, elem)
    return reduce(proc, lis)

def foldr(proc, elem, lis):
    lis.append(elem)
    lis.reverse()
    return reduce(lambda x, y : apply(proc, [y, x]), lis)

fl = foldl(lambda x, y : x / y, 2.0, [1.0, 2.0, 4.0, 8.0])
fr = foldr(lambda x, y : x / y, 2.0, [1.0, 2.0, 4.0, 8.0])

>>> fl
0.03125
>>> fr
0.5
>>> print foldl(lambda x, y : x / y, 3.0, [1.0, 3.0, 5.0, 7.0, 2.0, 1.0])
0.0142857142857
>>> print foldr(lambda x, y : x / y, 3.0, [1.0, 3.0, 5.0, 7.0, 2.0, 1.0])
1.42857142857

Pythonて絶対こんな書き方をする言語ではないと思った。