foldによるリストの長さを求めるためのメモ

fold_length.hs

foldr (+) 4 [1, 2, 3] -- 1 + (2 + (3 + 4)) == 10
foldl (+) 1 [2, 3, 4] -- ((1 + 2) + 3) + 4 == 10

1 + (2 + (3 + 4))
  (+) 1 (2 + (3 + 4))
    (+) 1 ((+) 2 ((+) 3 4))

((1 + 2) + 3) + 4
    (+) ((1 + 2) + 3) 4
    (+) ((+) ((+) 1 2) 3) 4

    
foldl (const   (+1)) 0 [1,2,3] -- 4 ?
foldr (const   (+1)) 0 [1,2,3] -- 3
foldl (const . (+1)) 0 [1,2,3] -- 3
foldr (const . (+1)) 0 [1,2,3] -- 2 ?

f1 = (const   (+1))
f2 = (const   (+1))
f3 = (const . (+1))
f4 = (const . (+1))

foldl f1 0 [1,2,3] -- 4
foldr f2 0 [1,2,3] -- 3
foldl f3 0 [1,2,3] -- 3
foldr f4 0 [1,2,3] -- 2

foldl f1 0 [1,2,3] -- 4
    (f1 (f1 (f1 0 1) 2) 3)
    (const (+1) (const (+1)  (const (+1) 0 1) 2) 3)
    (const (+1) (const (+1)  ((+1) 1) 2) 3)
    (const (+1) (const (+1)  2 2) 3)
    (const (+1) ((+1)  2) 3)
    (const (+1) 3 3)
    ((+1) 3)
    4

foldr f2 0 [1,2,3] -- 3
    (f2 1 (f2 2 (f2 3 0)))
    (const (+1) 1 (const (+1) 2 (const (+1) 3 0)))
    (const (+1) 1 (const (+1) 2 ((+1) 0)))
    (const (+1) 1 (const (+1) 2 1))
    (const (+1) 1 ((+1) 1))
    (const (+1) 1 2)
    ((+1) 2)
    3

foldl f3 0 [1,2,3] -- 3
    (f3 (f3 (f3 0 1) 2) 3)
    ((const . (+1)) ((const . (+1)) ((const . (+1)) 0 1) 2) 3)
    ((const . (+1)) ((const . (+1)) (const 1 1) 2) 3)
    ((const . (+1)) ((const . (+1)) 1 2) 3)
    ((const . (+1)) (const 2 2) 3)
    ((const . (+1)) 2 3)
    (const  3 3)
    3

foldr f4 0 [1,2,3] -- 2
    (f4 1 (f4 2 (f4 3 0)))
    ((f4) 1 ((f4) 2 ((f4) 3 0)))
    ((const . (+1)) 1 ((const . (+1)) 2 ((const . (+1)) 3 0)))
    ((const . (+1)) 1 ((const . (+1)) 2 (const 4 0)))
    ((const . (+1)) 1 ((const . (+1)) 2 4))
    ((const . (+1)) 1 ((const 3 4)))
    ((const . (+1)) 1 3)
    (const 2 3)
    2

:t const . (+1) 
    const . (+1) :: Num b => b -> b1 -> b

:t const . (+1) 1
    const . (+1) 1 :: Num (a -> b) => a -> b1 -> b

:t const . ((+1) 1)
    const . ((+1) 1) :: Num (a -> b) => a -> b1 -> b

:t (const . (+1)) 1
    (const . (+1)) 1 :: Num b => b1 -> b