• 日時　：2006/5/28 (Mon)
  • 場所　：名大 理学部1号館(多元数理科学研究科) 307室
  • 時刻　：18:00〜19:30
  • 参加者：10名
  • 話題　：
    • 積分のやつは長方形より台形のほうが精度が高い
    • 高階関数マンセー カリー化最高! → タプル(a,b)は何に使うの？ → 多値関数とかベクトルとか
    • 関数のアンカリー化(uncurrying)は結構使うかも？
    • アリティを返す関数って作れるの？→Haskellでやってみた．下記参照
    • camlでad-hoc polymorphismができるG'Camlってのがあります。
    • Printfの型はどうなってるんだ?
    • repeatとfold(reduce)は似てる
    • unlambda と brainfuck
    • let多相と値多相は結構重要
  • 4章に出てくるが今回話題にしなかった事：
    • パラメトリック多相，アドホック多相と部分型多相
    • η-展開(小笠原さんがちょっと言及)
  • 昨日は皆様お疲れさまでした〜 -- 今井け? 2006-05-30 (火) 19:09:46
  • 今回は難しかったデスネー。いっぺんには理解できないところもあったかと思いますが、気長にやりませう :) -- 小笠原? 2006-05-31 (水) 12:45:03

4章 Exercise †

↑

Exercise 1 (吉岡) †

∫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 (小笠原) †

# カリー化を利用した 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 (吉岡) †

#カリー化関数を受け取り、２つの組を受け取る関数に変換する関数。
let uncurry f (x,y) = f x y;;
↑

Exercise 5 (飯田) †

let fib n = 
  let (fibn, _) = repeat (fun (x,y) -> (y, x+y)) n (0,1) 
  in fibn;;
↑

Exercise 6 (みずの) †

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 (今井け) &dagger;

  • 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

↑

Exercize 8(よしひろ) &dagger;

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で関数のアリティを返す関数を作るには (今井け) &dagger;

  • アリティは静的に決まるので余り意味がないけれど一応.
  • Data.Typeableを使ってリフレクションで型を求める
  • Data.Typeableを使わなくても(型クラスを駆使して)できるかも
  • (->) が 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多相と値多相 (今井け) &dagger;

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

let多相と値多相の他の例：

# 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>

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2008-09-23 (火) 22:09:20 (5685d)