let t = 関数型プログラミング言語ML 2

>>934
OCamlだったらMLDonkey、Unison？

leditって日本語使えないの?

使える/使えないの基準がわからないが、とりあえず入力されたモノはとりあ
えず通るみたい。
ただ、入力された日本語がちゃんと表示されないから(print_string などの結
果は問題ない)、そういう意味では使いづらい。

たしかに print_stringの結果は大丈夫ですね。
入力が化けてるから駄目なのかと思いました。

GODI 便利だーーーーーーーーーーーーー
と、当たり前のことであげてみるテスト

にはは、観鈴ちん強い子

Lispで書ける Memorize関数(同じ引数で同じ関数を呼ばないように配列に結果を記憶しておくやつ)
を OCamlで書くことはできますか？
let rec fib = mem (fun n -> match n with 0 -> 0 | 1 -> 1 | _ -> (fib (n - 1)) + (fib (n - 2)));;
みたいな再帰定義ができないので無理なんでしょうか。
関数に外からアクセスされないstaticな配列を持たせられればいいんですけど。

ごめんなさい。まさにそのことが書いてあるページを発見してしまいました。
上のは無視してください。

度々申しわけないですが
http://www.h2.dion.ne.jp/~pana/memoize.html
の
fun n -> memoize cache fib n
の行を
memoize cache fib
にしたら駄目な理由ってなんなんでしょうか？

>>942
やってみましょう。以下のようなエラーになります。

This kind of expression is not allowed as right-hand side of `let rec'

>>942
その理由が分かんないんです。
明示的に関数だって教えてあげないと再帰定義できないんでしょうか。

えーと、スタックオーバフローするけど、次は定義できる。
# let rec f x = g x + g x
and g x = f x;;
そして、g x = f x は、g = fun x -> f x の糖衣構文であることに注意する。
すると、f, g は共にラムダ抽象なので、評価が進まないことがわかる。

ところで、
# let rec f x = g x + g x
and g = f;;
は、g はこの時点ではラムダ抽象では*ない*(変数だと思え！)ので、この時点で
評価を進ませることが出来て、一歩進むと、
let rec f x = f x + f x
のようになり、あきらかに定義できない。(let rec x = 1 + x が定義できないように。)
このように、明らかに定義できない部分は蹴っている。

型ぐらいみろ、と思うかもしれないが、
f : 'a -> 'a は、f 1 とすると値だけど、f (fun x -> x) とすると、
ラムダ抽象。要するに、どっちも来うるので、安全側に倒しているのだろう。

私も良く分かっていませんが。

ようするに、あれだ。
値になってない部分は先をとりあえず見ているわけだ。
ラムダ計算的には、ラムダ抽象は「値」だから、ラムダの中身はみていない。

>>945
>型ぐらいみろ、と思うかもしれないが、
>f : 'a -> 'a は、f 1 とすると値だけど、f (fun x -> x) とすると、
>ラムダ抽象。要するに、どっちも来うるので、安全側に倒しているのだろう。

というのはどういう意味ですか？
単純に引数が足りないからラムダ抽象、というわけにはいかないんでしょうか？

>>940 がエラーになる理由はなんとなく分かったんですけど、
(ラムダ抽象だってことは分かっても再帰がからんでややこしい)
>>945 のが良く分かりません。 f = fun x -> f x が常に成り立つなら
片方が通って片方が駄目なのはおかしいような。

let rec x = 1 + x が定義できないのは xがラムダ抽象じゃないからではないですか？
let rec f x = f x + f x は定義できますよ。

> というのはどういう意味ですか？
> 単純に引数が足りないからラムダ抽象、というわけにはいかないんでしょうか？

実際に値を入れてみるまで分からない、という意味です。
定義時点の型と syntax では判断できない。
上のが定義できたとしたら、定義できた後では、
f 1 も f (fun x -> x) も通らないといけないのです。
上のはたまたま関数が来ることが分かっていたからいいけど、
そうでない場合があるかもしれなくて、それが
let rec x = 1 + x みたいな感じになることがあるので、だめ。

あー、ちゃんと説明できてない。

> let rec f x = f x + f x は定義できますよ。
let rec f x = f x + f x が定義できないというのは、
OCaml の関数として定義できないのではなくて、値が定まらないという
意味です。言葉足らず。

っていうか、例として不適切ですねえ。すまん。

だめぽ。

> 単純に引数が足りないからラムダ抽象、というわけにはいかないんでしょうか？
これは絶対無理。 -rectypes でよろ。
let rec eater x = eater
eater 1 2 3 4 5 6 7 ....

自分でもわけわかんなくなってきたけど、
let rec x = y + 1 and y = x + 1;;
これを禁止したかったから、ラムダの中にいれずに値としてつかっちゃだめよ、
ということかな？

エロい人補足よろ。

> 単純に引数が足りないからラムダ抽象、というわけにはいかないんでしょうか？
そういえばη展開とかいうキーワードもありますな。
Haskell とは違うのだよ。

Haskellでは問題ないね。

> memoize cache fib
は多相だからだめなんでないか？
> この制限を値多相(value polymorphism)と呼ぶ．値多相に制限しなければならない理由は副作用(7章参照)をもつ言語機構と深く関係があるのだが，ここでは説明しない．
...
> このように，関数を計算する式(ここでの double double)に fun x -> ... x をつけて値とするような(プログラムの)変換を η-展開(η-expansion)という．
http://www.sato.kuis.kyoto-u.ac.jp/~igarashi/class/isle4/mltext/ocaml005.html

>>953
そうなんですか？ fibまで貰った時点で多相じゃないような。

let rec は関数宣言にしか使えないので、
let rec f n = ... もしくは let rec f = fun n -> ... みたいな
形でしか宣言できないという説はどうでしょうか？

# let rec fib = (fun n -> match n with 0 -> 0 | 1 -> 1 | _ -> (fib (n - 1)) + (fib (n - 2)));;
当然OK

# let rec fib = (fun x -> x) (fun n -> match n with 0 -> 0 | 1 -> 1 | _ -> (fib (n - 1)) + (fib (n - 2)));;
右辺の第一項は 'a -> 'a 第二項は int -> int なので右辺は int -> int になりますが明示的でないのでNG

あのエラーメッセージはどうかと思いますが。

>>954
let rec x = 1 :: x;;
は通るよ。

> あのエラーメッセージはどうかと思いますが。
同感。何がだめなのかわからないよね。

>>955
>let rec x = 1 :: x;;
>は通るよ。

ほんとですね。>>953のとこに recが「有効なのは関数宣言のみである」って書いてあったので。
let rec x = 1;;
はダメだし
let f = (fun x -> x) (fun x -> x);;
はOKだけど
let rec f = (fun x -> x) (fun x -> x);;
はダメだから、このパターンなんじゃないですかね。

compilerのソースを読み解く勇者がいれば…
MLで書かれているから読みやすいはず（関数型言語の宣伝文句によれば）

>>957
べつにコンパイラ全部読むわけじゃないから、そんなに物凄く大変てこともないだろう。
で、見てみたが、件のエラーは translcore.ml で吐かれてて、しかもそれが
実際に起きるのは check_recursive_lambda が呼ばれてる個所のみ。
ここで右辺の値を調べてチェックしてるみたい。

なので後は自分で調べてほしいんだけど、自分でちょっと見てみたので、激し
く既出の内容だが、書いてみる。

簡単に言うと、単なる値と関数値はチェック時には区別がされている。
たとえば、
fun n -> memoize cache fib n
は明確に関数だということがわかるが、
memoize cache fib
を関数値として見ているわけじゃない(型チェックなどの労は惜しんでいる)。

で、自分の値を計算するのに自分の値が必要となるような状況は避けているか
らエラーになるわけだ。
let rec f x = g x
and g x = f x
だと、g の右辺値は(内部的には g = fun x -> f x なので)関数値とみなされエラーにならないが、
let rec f x = g x
and g = f
だと右辺値は単なる値なのでエラーになる。これと同じじゃないかな。

自分で言いだしといてなんだけど、
let rec x = 1 :: x;;
の場合、右辺値はコンストラクタなので他と扱いが違うんだろう。
let rec x = `x x;;
とかもできるのと同じだろうね。

昔は rec は関数定義しか通らなかったと聞いた。
いつから通るようになったんだろ。Changes とか見ればいいんでしょうが。

そろそろ次スレかな？

>>959
リリースアナウンスを訳した記憶があるから確か3.07からだったような。
と思ってアナウンスを調べたてみたら、MLにしか上がってないのな。
http://caml.inria.fr/archives/200309/msg00313.html
Both compilers:
- Compilation of "let rec" on non-functional values: tightened some checks,
relaxed some other checks.

>>958
>let rec x = `x x;;
ﾜﾗﾀ。その二個目のxはyでもXでもおんなじやん。
何となく「できるだけ分かりにくくしよう」という嫌がらせを感じなくもないｗ

新スレ立てました。

関数型言語ML(SML, OCaml, etc.), Part 3
http://pc5.2ch.net/test/read.cgi/tech/1103606223/

>>962
いやそんな意図を持って書いたわけじゃなかったんですが、たしかに見辛いですな。

ちなみにヘンな let rec といえばこんなのも。
# let rec x = lazy(Lazy.force x);;
val x : 'a lazy.t = <lazy>
# Lazy.force x;;
Exception: Lazy.Undefined.

OCamlで、相互に参照するクラス関係はどのように書けば良いのでしょうか？

GOFのObserver-patternを適用することで解決できましたが、もっと良い方法があれば教えていただきたく思います。

class A = object ... end
and B = object ... end;;

とかいうことではなくて？

>>967
相互依存関係のことなので、それだけではできませんでした。

exception Opnotsupported;;
class ['test2] test1 =
object (self)
val mutable test2_ = ([] : 'test2 list)
method add_test2 t =
if test2_ = [] then test2_ <- t::test2_
else raise Opnotsupported
method get = (List.hd test2_)#get
end;;

class test2 t1 =
object (self)
val str = "test2desu"
val test1_ = t1
initializer test1_#add_test2 self
method get () = str
method print () = print_string (test1_#get ())
end;;

let t1 = new test1 in let t2 = new test2 t1 in t2#print ();;

私は上記のようにしたのですが、test2のインスタンスは1つしか持たないのにリストとして保持しています。
あまり綺麗ではないので、もっと良い方法は無いものでしょうか。

>>969
問題点がどこにあるのかいまいち理解できないんだけど．
相互再帰うんぬんではなくて，単にこういうことではないの？

exception Opnotsupported;;
class ['test2] test1 =
object (self)
val mutable test2_ = (None: 'test2 option)
method add_test2 t =
match test2_ with
None -> test2_ <- Some t
| Some _ -> raise Opnotsupported
method get =
match test2_ with
None -> failwith "Wow!" (* ここは適当な処理に変えてね *)
| Some x -> x#get
end;;

class test2 t1 =
object (self)
val str = "test2desu"
val test1_ = t1
initializer test1_#add_test2 self
method get () = str
method print () = print_string (test1_#get ())
end;;

ブラザー、春だぜ。
今日OCaml初めて使いました。ところで、質問。

2重ループを書くとき、
let rec loop i j 結果 =
if i = 10 && j = 10 then 結果
else if j = 10 then loop 0 (j+1)
else loop (j+1) i 処理 in
loop 0 0;;
のように書くのか、for文をネストして書くのかどちらが一般的なのでしょうか？
for文は手続き処理部分を含むので関数的ではありませんよね？

for の方が最適化されやすくて高速になる。後は趣味による。
個人的には末尾再帰の方が好みだけど、処理にもよる。

>>972
なるほど。ありがとうございます。

OCamlでは、string型でfold_rightのような関数が定義されていないのはどうしてですか？

訊く場所が間違っている

stringがすっげー不便なんだけど、char listで扱った方がよくないっすか？
また、stringの代わりにchar listを使った場合にどんな問題が出る？

let recで名前付けないで再帰関数を作る方法はありますか？

>>974,976-977
まず、次スレがあるから、真面目な質問ならそっちで聞いてみた方が答える人
が微妙に多いんじゃないか。

string が char list ではなく別の型になっているのは高速化と最適化のため。
文字列とリストはメモリの割当て方がぜんぜん違う。配列とは近いから
char array でも大差ない気もするけど、そこのところはよくわからない。

fold 系とかがなんでないのかは知らん。 ExtLib http://ocaml-lib.sourceforge.net/
で追加されているからそっちを使ってみるのもよし。

無名再帰関数を作ることはできるが、ちょっとトリッキーな関数を定義してや
らないといけない。
http://www.kurims.kyoto-u.ac.jp/~hassei/selfref.pdf
の最後に、 SML でそういう関数を定義しているのが載っているから、これを
書き直せば使える。

>>978
Haskellじゃ[Char]になっているのはちょっと効率悪いって事か。
OCamlの方が高速少メモリなのかな

>>978 ども。OCamlはじめたばかりだったんであっちは別スレとおもてたよ

目的がよくわからんレポートだったけど、factorial定義でやろうとしてることは
なんとなくわかったつもり。こういうことかな

まず再帰関数の定義を、自分を渡すパラメータとして定義する
let defFact = fun fact n -> if n = 0 then 1 else n * fact (n - 1)

で、これを直接つかうとしたらこんな感じになるんで
defFact (defFact (defFact .. (defFact dummy))) 10

つまり.不動点てのは、その関数を無限（必要な限り）に適用した感じものか
ただfixpointでなにやってるかはわからんかったが

理解できました

type genDef = wrapGenDef -> (int -> int)
and wrapGenDef = Wrap of genDef

let unwrap = function Wrap(func) -> func

let fixpoint = fun funDef ->
let genFunc = fun wrapped -> funDef (fun n -> (unwrap wrapped) wrapped n) in
let wrapped = Wrap(genFunc) in
genFunc wrapped

let factorial = fixpoint (fun fact n -> if n = 0 then 1 else n * fact (n - 1))

open Printf;;
printf "%d\n" (factorial 5)

必要なときに取り出して使う感じに思った

ここまで来てなんだが、あんなにややこしいことをしなくても、
let rec fix f x = f (fix f) x
と明示的に関数として定義してやれば可能なのを思い出した。スマソ。


fix (fun f x -> if x <=0 then 1 else x * f (x - 1))
↑普通の階乗。

fix (fun f res n -> if n <= 0 then res else f (res * n) (n - 1)) 1
↑末尾再帰な階乗。

let rec つかってるじゃん