活動記録/第3回 のバックアップ(No.3)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• 活動記録/第3回 へ行く。
  • 1 (2006-05-30 (火) 18:00:14)
  • 2 (2006-05-30 (火) 20:42:17)
  • 3 (2006-05-30 (火) 23:24:38)
  • 4 (2006-05-31 (水) 12:45:03)
  • 5 (2006-05-31 (水) 18:43:56)
  • 6 (2006-06-03 (土) 07:34:25)
  • 7 (2006-06-03 (土) 10:39:41)
  • 8 (2007-11-27 (火) 14:40:24)

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

• 昨日は皆様お疲れさまでした〜 -- 今井け? 2006-05-30 (火) 19:09:46

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 4 (吉岡) †

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

Exercise 7 (今井け) †

• 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(よしひろ) †

double = 入f.入x.f (f x) とする。

Haskellで関数のアリティを返す関数を作るには (今井け) †

• アリティは静的に決まるので余り意味がないけれど一応.
• 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多相と値多相 (今井け) †

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