宿題

Exercise 6   次の関数 funny がどのような働きをするか説明せよ．

# let rec funny f n = 
#   if n = 0 then id
#   else if n mod 2 = 0 then funny (f $ f) (n / 2)
#   else funny (f $ f) (n / 2) $ f;;
val funny : ('a -> 'a) -> int -> 'a -> 'a = <fun>

fをn回適用した関数を返す高階関数。repeatと同じ働きをする。

次のようにすると、どのような働きをするかがわかりやすい。

# let add1 x = x + 1;;
val add1 : int -> int = <fun>
# let add3 = funny add1 3;;
val add3 : int -> int = <fun>
# add3 5;;
- : int = 8
# add3 1;;
- : int = 4
#
# let add5 = funny add1 5;;
val add5 : int -> int = <fun>
# add5 5;;
- : int = 10
# add5 15;;
- : int = 20

let add5 = funny add1 5
         = funny (add1 $ add1) (5 / 2) $ add1 
         = funny (add1 $ add1) 2 $ add1
         = funny ( (add1 $ add1) $ (add1 $ add1)) (2 / 2) $ add1
         = funny (add1 $ add1 $ add1 $ add1) 1 $ add1
         = funny ( (add1 $ add1 $ add1 $ add1) $ (add1 $ add1 $ add1 $ add1)) (1/2) 
           $ (add1 $ add1 $ add1 $ add1) $ add1
         = funny ( (add1 $ add1 $ add1 $ add1) $ (add1 $ add1 $ add1 $ add1)) 0 
           $ (add1 $ add1 $ add1 $ add1) $ add1
         = id $ (add1 $ add1 $ add1 $ add1) $ add1
         = add1 $ add1 $ add1 $ add1 $ add1