活動記録/第3回 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• 活動記録/第3回 へ行く。
• 活動記録/第3回 の差分を削除

- 日時　：2006/5/28 (Mon)
- 場所　：名大 理学部1号館(多元数理科学研究科) 307室
- 時刻　：18:00〜19:30
- 参加者：10名
- 話題　：
-- 積分のやつは長方形より台形のほうが精度が高い
-- 高階関数マンセー カリー化最高! → タプル(a,b)は何に使うの？ → 多値関数とかベクトルとか
-- 関数のアンカリー化(uncurrying)は結構使うかも？
-- アリティを返す関数って作れるの？→Haskellでやってみた．下記参照
-- camlでad-hoc polymorphismができる[[G'Caml:http://web.yl.is.s.u-tokyo.ac.jp/~furuse/gcaml/]]ってのがあります。
-- Printfの型はどうなってるんだ?
-- repeatとfold(reduce)は似てる
-- [[unlambda:http://www.madore.org/~david/programs/unlambda/]] と [[brainfuck:http://www.muppetlabs.com/~breadbox/bf/]]
-- [[let多相と値多相:http://www.sato.kuis.kyoto-u.ac.jp/~igarashi/class/isle4/mltext/ocaml.html#htoc48]]は結構重要
-4章に出てくるが今回話題にしなかった事：
--パラメトリック多相，アドホック多相と部分型多相
--η-展開(小笠原さんがちょっと言及)

- 昨日は皆様お疲れさまでした〜 -- [[今井け]] &new{2006-05-30 (火) 19:09:46};
- 今回は難しかったデスネー。いっぺんには理解できないところもあったかと思いますが、気長にやりませう :) -- [[小笠原]] &new{2006-05-31 (水) 12:45:03};
- GHnthWvxrdXJJaSKBK -- [[cfbxlugcn]] &new{2008-09-23 (火) 10:36:12};

#comment

----
#contents

* 4章 Exercise [#d8cb57c7]

**Exercise 1 (吉岡) [#l5a82fd5]
∫f(x)dxを計算する関数integral f a bを定義する。
 #台形近似を使ってない方
 let integral f a b=
  let c =(b -. a)/.10000.0
  in let rec high f d = if d>=b then f d
  else f d +. (high f (d +. c))
  in c*.(high f a);;
  
 integral (fun x->sin x) 0.0 3.1415;;
 : float = 1.9999999242302231

**Exercise 2 (小笠原) [#v2ebf73d]
 # カリー化を利用した pow 関数
 let rec pow n x = 
  if n = 0 then 1.0
  else x *. pow (n - 1) x

 let cube = pow 3

 let rec pow' x n =
  if n = 0 then 1.0
  else x *. pow (n - 1) x
 
 let cube' x = pow' x 3

**Exercise 4 (吉岡) [#hf9ba65e]
 #カリー化関数を受け取り、２つの組を受け取る関数に変換する関数。
 let uncurry f (x,y) = f x y;;

**Exercise 5 (飯田) [#q7b11761]
 let fib n = 
   let (fibn, _) = repeat (fun (x,y) -> (y, x+y)) n (0,1) 
   in fibn;;

**Exercise 6 (みずの)[#oab2f3d6]
''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

まず、''funny''で使われている''id''と''$''の定義は次のようになっている。

 let id x = x;;
 let ($) f g x = f ( g x);;

そして、''funny''は''$''を使って、関数を合成することにより、''repeat''と同じ機能を実現している。
つまり、例えば'''add3''は、''add1''を3回、''id''を好きな数だけ合成することで得られる。

 let add3 = id $ add1 $ add 1 $ add1;;

そして、''funny''の動作を具体的にみると、

 funny f 0 = id
 funny f 1 = funny (f $ f) (1/2) $ f = id $ f
 funny f 2 = funny (f $ f) (2/2) = id $ f $ f
 funny f 3 = .........

のようになっている。(証明は勘弁してください)

名前は''reduce''や''fold''あたりがいいらしい。

**Exercise 7 (今井け) [#oa9ab931]
- k (s k k) = λab.bはわりと自明(--;

 Chap.4 Exercise 7 (今井け)
 
 まずはkとsの定義
 
 # let k x y = x;;
 val k : 'a -> 'b -> 'a = <fun>
 # let s x y z = x z (y z);;
 val s : ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c = <fun>
 
 問1. (s k k) == id の確認
 
 s k k 1
 ==> k 1 (k 1)  (* sの定義より *)
 ==> c1 (k 1)   (* ただし c1 は 必ず1を返す定数関数, c1 : 'b -> int *)
 ==> c1 c2      (* 同様に c2 : b' -> int *)
 ==> 1
 
 s k k のそれぞれの部分式の型は？
 
 仮に s1 k1 k2 とすると
 s1 : ('a1 -> ('b2 -> 'a1) -> 'a1) -> ('a1 -> 'b2 -> 'a1) -> ('a1 -> 'a1)
 k1 : 'a1 -> ('b2 -> 'a1) -> 'a1
 k2 : 'a1 -> 'b2 -> 'a1
 よって s1 k1 : ('a1 -> 'b2 -> 'a1) -> ('a1 -> 'a1)，
 s1 k1 k2 : ('a1 -> 'a1)．
 
 
 問2. 'a -> 'b -> 'b なる関数をskのみで構成
 
 答え．k (s k k)
 
 # k (s k k) 1 2;;
 - : int = 2
 
 - それぞれの部分式の型は？
 s k k : 'a1 -> 'a1 (恒等関数)．
 
 k : 'a -> 'b -> 'a だが，この 'a が s k k の 'a1 -> 'a1 と単一化され
 k : ('a1 -> 'a1) -> 'b -> ('a1 -> 'a1)
 という型が付く．
 よって k (s k k) : 'b -> 'a1 -> 'a1
 
参考：[[Combinator Birds:http://www.angelfire.com/tx4/cus/combinator/birds.html]]

** Exercize 8(よしひろ) [#sfedf9eb]
double = 入f.入x.f (f x) とする。
 double double f x = (double double f) x
 =  ((入f.入x.f (f x)) double f) x
 -> (double (double f)) x
 =  (double ((入f.入x.f (f x)) f) x
 -> (double (入x.f (f x))) x
 =  (入f.入x.f (f x)) (入x.f (f x)) x
 -> (入x.f (f x)) ((入x.f (f x)) x)
 -> (入x.f (f x)) (f (f x))
 -> f (f (f (f x)))

* Haskellで関数のアリティを返す関数を作るには (今井け) [#n364653e]
- アリティは静的に決まるので余り意味がないけれど一応.
- [[Data.Typeable:http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Typeable.html]]を使ってリフレクションで型を求める
- [[Data.Typeable:http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Typeable.html]]を使わなくても(型クラスを駆使して)できるかも
- (->) が 2引数の型構築子であることを利用。
- splitTyConApp :: TyRep -> (TyCon, [TyRep]) は型を構成している型構築子と型引数に分ける関数。 Int->Stringは (->, [Int, String]) になる。 
- tyArr :: TyCon は (->)

ソース arity.hs 
 import Data.Typeable
 
 tyArr = fst $ splitTyConApp $ typeOf (?x->not x)
  
 arity :: (Typeable a) => a -> Int
 arity f = countArr (typeOf f)
   where 
     countArr ty = 
       case splitTyConApp ty of 
         (tyCon, [_, tyRes]) -> 
           if tyCon == tyArr then 1 + countArr tyRes else 0
         _ -> 0

例
 *Main> arity (&&)
 2
 *Main> arity (||)
 2

(+) :: (Num a) => a -> a -> a だが，Num aから Typeable aは導出できない為，こっちで型を指定する必要がある
 *Main> arity (+)
 
 <interactive>:1:0:
     Ambiguous type variable `a' in the constraints:
       `Typeable a' arising from use of `arity' at <interactive>:1:0-4
       `Num a' arising from use of `+' at <interactive>:1:6-8
     Probable fix: add a type signature that fixes these type variable(s)
 *Main> arity ((+)::Int->Int->Int)
 2
 *Main> arity True
 0

* let多相と値多相 (今井け) [#a17e6643]

- ちょっと解説(小笠原)
-- let多相とは、let宣言/式の型に型変数を残して、後で型変数に任意の型を代入できるようにしてやる仕組みのこと。
-- あまりに当たり前なので、これが let宣言/式でしかできない事に気づかない。
-- 任意の式で多相にしようとすると(first-class polymorphism)、それは SystemF。表現力強すぎて、型付けできない。(この辺あやしい ToT)
-- しかも OCaml には参照があるため、let多相に「多相にできるのは値だけ(関数適用はだめ)」という制約がつく。これが値多相。
-- ちなみに、MLに first-class polymorphism(の部分)を[[導入できるという話:http://www.cs.nott.ac.uk/~gmh/appsem-papers/lebotlan.pdf]]もあるらしい。

[[let多相と値多相:http://www.sato.kuis.kyoto-u.ac.jp/~igarashi/class/isle4/mltext/ocaml.html#htoc48]]の他の例：
 # let double f x = f (f x);;
 val double : ('a -> 'a) -> 'a -> 'a = <fun>
 # let f1 x = x +1;;
 val f1 : int -> int = <fun>
 # let x1 = 0;;
 val x1 : int = 0
 
 こっちはOKのだけど
 # double double f1 x1;;
 - : int = 4
 
 こっちは型付けできない．
 #  (fun d -> d d f1 x1) double;;
 This expression (2つめのd) has type 'a -> 'b -> 'c -> 'd but is here used with type 'a
 参考
 # (fun d -> double d f1 x1) double;;
 - : int = 4
 # (fun d -> d double f1 x1) double;;
 - : int = 4

 多相にできるのは値のみ.
 # let fourtimes = double double;;
 val fourtimes : ('_a -> '_a) -> '_a -> '_a = <fun>
 # fourtimes((+) 1);;
 - : int -> int = <fun>
 # fourtimes((+.) 1.0);;
 This expression has type float -> float but is here used with type int -> int 
 こうすれば fourtimes は値なので多相にできる
 # let fourtimes f x = double double f x;;
 val fourtimes : ('a -> 'a) -> 'a -> 'a = <fun>