![[PukiWiki]](image/caml3.jpg "[PukiWiki]")
トップページ
OCaml Tips
- モジュールシステム紹介
- let多相紹介
- ヘテロなリスト
- 幽霊型
- OCamlでモナド
- 再帰型(Equi-recursive)
- サンタクロース問題
- デーモンの例
- Expression Problem
- ivarの必要性
- OSC2008In名古屋
ネタ記録庫
関数型言語によるWeb開発
ScalaByExample(訳)
限定継続
お勉強リンク
発表資料
活動記録
最新の20件
2016-02-23
2015-05-06
2015-05-04
2014-03-12
2012-05-22
2012-03-16
2012-03-03
2012-02-27
2012-02-03
2011-12-28
2011-12-10
2011-10-10
2011-09-29
2011-09-28
Thanks
OCamlテクニック/再帰型(Equi-recursive)
equi-recursive type in ocaml †
参考： Developing Applications With Objective Caml より、
たとえば、タプル型でリストを作ったりできる。以下の例では、OCamlのequi-recursive typeのサポート(オプション-rectypes)を使って、1の無限リストを直積型で実現する。
Haskellではequi-recursive typeのサポートがないのでこれはできない。
$ 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でムリヤリ実現するには。
newtype Rec t = R (t (Rec t))
という「型レベルの不動点コンビネータ」みたいなものを作る (FIXME:出典求む)。Haskellでは、不動点コンビネータYは y f = f (y f)と書けるのを思い出してほしい。
この型構築子は、
ones = R (1, ones)
などとして使う。このonesの型は
*Main> :t ones ones :: Rec ((,) Integer)
である。 (型(a,b)は (,) a b と表記されることに注意。(,)は2引数の型構築子で、 (,) 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,....
(けいご)
