##すご >Typefxxk。 ところで基本的な質問ですが、型レベルでチューリング完全な言語が実装できてしまうということは、型つけが停止しないという可能性があるってことでしょうか。
#えーっと、いちおう Haskell98 では止まるように何らかの制限がかかってたと思います
#でも、 GHC の拡張を使えばそういう型つけをコンパイラに許すことができます
#-XUndecidableInstances でそれを許しています
#なるほど。なんとなく型システムは必ず停止するように作られてるような印象を持っていました。
#-XTypeFamilies -XUndecidableInstances なので、外している制限はこれですね。http://bit.ly/2R7KSd #基本的には（-XUndecidableInstances なしなら）型付けは必ず停止するように作られています。ただ、必ず停止するように作ると制限が厳しくなりすぎて、ユーザーは停止することが分かっているけれどコンパイラに弾かれるプログラムが出てきます
#そこで、より豊かな表現力を提供するために、GHC では型付けが停止できないような可能性のあるプログラムも許可する -XUndecidableInstances を提供しています。
#ただもちろん、無制限で型付けが停止しないプログラムを許可してしまうとコンパイラが停止しなくなってしまうので、GHC では展開するスタックの深さを制限するようになっています。http://bit.ly/2BfWeq #あっ、リンクする URL を間違えました。正しくはこちらです。http://bit.ly/Q60jT #ものまね鳥を許容するオプションはありませんか？
#m x = x x
##ググるとさかいさんの昔の記事が出てきました。 http://bit.ly/1T3QYe これは -XRank2Types というオプションでできます。型宣言は必須です。おもしろいですね #やはり酒井さんのページから http://bit.ly/1LQO7I GHC では inliner の都合で使えませんが……。 #YHC ではいけるのかな？ YHC でいけるなら、YHC -> GHC Core -> GHC で GHC Core をコンパイルという手段が使えそうな気も。
##スライドを見直したら、 Haskell -> YHC Core -> Haskell で、最終的に生成されたコードを GHC でコンパイルでした。
#ああっ、私の紹介したページは、回答すべきだったものとはちょっとずれていますね。
#お詫び代わりに、ググって発見したページを紹介しておきます。Combinators in Haskell [http://bit.ly/218t8W]、Combinatory Birds as Types [http://bit.ly/2HvMhW] ##型がなければうまくいくけど、Haskellではまともなものができそうにない気がする。型がなければこんな感じ
#pfc> (define (m x) (x x))
m
pfc> (define (c f x y) (f y x))
c
pfc> (define (b f g x) (f (g x)))
b
pfc> (define (s f g x) (f x (g x)))
s
pfc> (define l (c b m))
l
pfc> (define y (s l l))
y
pfc> (define fib (y (lambda (f n) (if (< n 2) n (+ (f (- n 1)) (f (- n 2)))))))
fib
pfc> (fib 10)
55
#さっき紹介したページのコメント欄より。
#> :m Control.Applicative Unsafe.Coerce
> let m = id <*> (unsafeCoerce id)
> :t m
m :: (a -> b) -> b
> let y f = m (f . m)
> let fact = y (\f x y -> if y == 0 then x else f (x*y) (y-1)) 1
> fact 5
120
> let fib = y (\f n -> if n < 2 then n else (f (n-1)) + (f (n-2)) )
> fib 10
55
#なら、m コンビネータを使って y コンビネータを定義できますね。
#unsafeCoerce を使って型検査を外しているのが酷いと思うかもしれませんが……。
#unsafeCoerce があったか。
#うげーですねぇ :)
#Haskellナイト出演者に質問がある人は に質問を投げてくださいませ。当日とりあげます。
#Haskellナイト出演者に質問がある人は @chaton_haskell に質問を投げてくださいませ。当日とりあげます。
#あなたにとってモナドとは何ですか? #haskell
#11/19-20 のFranzセミナーで、Haskellナイトの当日券が2000円になるチラシを限定100枚配布します。 #haskell
#@chaton_clj RT @eyasuyuki: 11/19-20 のFranzセミナーで、Haskellナイトの当日券が2000円になるチラシを限定100枚配布します。 #haskell
haskell-ja > Archives > 2009/11/17