![[PukiWiki]](image/caml3.jpg "[PukiWiki]")
OCamlテクニック/再帰型(Equi-recursive) のバックアップ(No.1)
- バックアップ一覧
- 差分 を表示
- 現在との差分 を表示
- ソース を表示
- OCamlテクニック/再帰型(Equi-recursive) へ行く。
- 1 (2007-06-08 (金) 09:24:45)
- 2 (2007-06-08 (金) 09:35:51)
- 3 (2007-06-08 (金) 12:52:20)
- 4 (2007-11-27 (火) 14:39:30)
- 5 (2007-12-23 (日) 18:43:52)
equi-recursive type in ocaml †
参考： Developing Applications With Objective Caml より、
たとえば、タプル型でリストを作ったりできる。以下の例では、-rectypesを使って、1の無限リストを直積型で実現する。 Haskellではこれはできない。Nominalな型システムだから？(耳学問、ソース求む)
$ ocaml
Objective Caml version 3.09.3
# let rec ones = (1, ones);;
This expression has type int * (int * 'a) but is here used with type int * 'a
# ^D
$ ocaml -rectypes
Objective Caml version 3.09.3
# let rec ones = (1,ones);;
val ones : int * 'a as 'a =
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(1,
(...)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
#
val x : int * 'a as 'a という型表現に注目して頂きたい。不動点演算子μで書くとμ'a.int*'a という感じ。
Haskellでムリヤリ同じことをやる †
Haskellでムリヤリ実現するには。
data Rec t = R (t (Rec t))
という「型レベルの不動点演算子」みたいなものを作る。Haskellでは、不動点演算子Yは y = f (y f)となるのを思い出してほしい。
ones = R (1, ones)
などとして使う。このonesの型は
*Main> :t ones ones :: Rec ((,) Integer)
データ構築子Rを介して再帰を展開する必要がある：
printRec (R (a,r)) = "(" ++ show a ++ "," ++ printRec r
*Main> printRec ones (1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,....
(けいご)
