トップ
新規
単語検索
ヘルプ
活動記録/第3回
をテンプレートにして作成
開始行:
- 日時 :2006/5/28 (Mon)
- 場所 :名大 理学部1号館(多元数理科学研究科) 307室
- 時刻 :18:00〜19:30
- 参加者:10名
- 話題 :
-- 積分のやつは長方形より台形のほうが精度が高い
-- 高階関数マンセー カリー化最高! → タプル(a,b)は何に使う...
-- 関数のアンカリー化(uncurrying)は結構使うかも?
-- アリティを返す関数って作れるの?→Haskellでやってみた....
-- camlでad-hoc polymorphismができる[[G'Caml:http://web.y...
-- Printfの型はどうなってるんだ?
-- repeatとfold(reduce)は似てる
-- [[unlambda:http://www.madore.org/~david/programs/unlam...
-- [[let多相と値多相:http://www.sato.kuis.kyoto-u.ac.jp/~...
-4章に出てくるが今回話題にしなかった事:
--パラメトリック多相,アドホック多相と部分型多相
--η-展開(小笠原さんがちょっと言及)
- 昨日は皆様お疲れさまでした〜 -- [[今井け]] &new{2006-05...
- 今回は難しかったデスネー。いっぺんには理解できないとこ...
----
#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]
#カリー化関数を受け取り、2つの組を受け取る関数に変換す...
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''は''$''を使って、関数を合成することによ...
つまり、例えば'''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 :...
==> c1 c2 (* 同様に c2 : b' -> int *)
==> 1
s k k のそれぞれの部分式の型は?
仮に s1 k1 k2 とすると
s1 : ('a1 -> ('b2 -> 'a1) -> 'a1) -> ('a1 -> 'b2 -> '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...
** 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で関数のアリティを返す関数を作るには (今井け) [#...
- アリティは静的に決まるので余り意味がないけれど一応.
- [[Data.Typeable:http://www.haskell.org/ghc/docs/latest/...
- [[Data.Typeable:http://www.haskell.org/ghc/docs/latest/...
- (->) が 2引数の型構築子であることを利用。
- splitTyConApp :: TyRep -> (TyCon, [TyRep]) は型を構成し...
- 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 <inter...
`Num a' arising from use of `+' at <interactive>:1...
Probable fix: add a type signature that fixes these ...
*Main> arity ((+)::Int->Int->Int)
2
*Main> arity True
0
* let多相と値多相 (今井け) [#a17e6643]
- ちょっと解説(小笠原)
-- let多相とは、let宣言/式の型に型変数を残して、後で型変...
-- あまりに当たり前なので、これが let宣言/式でしかできな...
-- 任意の式で多相にしようとすると(first-class polymorphis...
-- しかも OCaml には参照があるため、let多相に「多相にでき...
-- ちなみに、MLに first-class polymorphism(の部分)を[[導...
[[let多相と値多相:http://www.sato.kuis.kyoto-u.ac.jp/~iga...
# 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...
参考
# (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...
こうすれば fourtimes は値なので多相にできる
# let fourtimes f x = double double f x;;
val fourtimes : ('a -> 'a) -> 'a -> 'a = <fun>
終了行:
- 日時 :2006/5/28 (Mon)
- 場所 :名大 理学部1号館(多元数理科学研究科) 307室
- 時刻 :18:00〜19:30
- 参加者:10名
- 話題 :
-- 積分のやつは長方形より台形のほうが精度が高い
-- 高階関数マンセー カリー化最高! → タプル(a,b)は何に使う...
-- 関数のアンカリー化(uncurrying)は結構使うかも?
-- アリティを返す関数って作れるの?→Haskellでやってみた....
-- camlでad-hoc polymorphismができる[[G'Caml:http://web.y...
-- Printfの型はどうなってるんだ?
-- repeatとfold(reduce)は似てる
-- [[unlambda:http://www.madore.org/~david/programs/unlam...
-- [[let多相と値多相:http://www.sato.kuis.kyoto-u.ac.jp/~...
-4章に出てくるが今回話題にしなかった事:
--パラメトリック多相,アドホック多相と部分型多相
--η-展開(小笠原さんがちょっと言及)
- 昨日は皆様お疲れさまでした〜 -- [[今井け]] &new{2006-05...
- 今回は難しかったデスネー。いっぺんには理解できないとこ...
----
#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]
#カリー化関数を受け取り、2つの組を受け取る関数に変換す...
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''は''$''を使って、関数を合成することによ...
つまり、例えば'''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 :...
==> c1 c2 (* 同様に c2 : b' -> int *)
==> 1
s k k のそれぞれの部分式の型は?
仮に s1 k1 k2 とすると
s1 : ('a1 -> ('b2 -> 'a1) -> 'a1) -> ('a1 -> 'b2 -> '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...
** 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で関数のアリティを返す関数を作るには (今井け) [#...
- アリティは静的に決まるので余り意味がないけれど一応.
- [[Data.Typeable:http://www.haskell.org/ghc/docs/latest/...
- [[Data.Typeable:http://www.haskell.org/ghc/docs/latest/...
- (->) が 2引数の型構築子であることを利用。
- splitTyConApp :: TyRep -> (TyCon, [TyRep]) は型を構成し...
- 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 <inter...
`Num a' arising from use of `+' at <interactive>:1...
Probable fix: add a type signature that fixes these ...
*Main> arity ((+)::Int->Int->Int)
2
*Main> arity True
0
* let多相と値多相 (今井け) [#a17e6643]
- ちょっと解説(小笠原)
-- let多相とは、let宣言/式の型に型変数を残して、後で型変...
-- あまりに当たり前なので、これが let宣言/式でしかできな...
-- 任意の式で多相にしようとすると(first-class polymorphis...
-- しかも OCaml には参照があるため、let多相に「多相にでき...
-- ちなみに、MLに first-class polymorphism(の部分)を[[導...
[[let多相と値多相:http://www.sato.kuis.kyoto-u.ac.jp/~iga...
# 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...
参考
# (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...
こうすれば fourtimes は値なので多相にできる
# let fourtimes f x = double double f x;;
val fourtimes : ('a -> 'a) -> 'a -> 'a = <fun>
ページ名: