最近のキーワード

2006年06月21日

上限なしで素数生成(ML版)

さらに、ML(mosml)でやってみた。
問題:「キミならどう書く 2.0 - ROUND 1 -」
答え:
load "intmap";

fun prime(n,m,xs)
= let
    fun put m k v =
      if Intmap.peek(m,k) = NONE then
        Intmap.insert(m,k,v)
      else
        put m (k+v) v
  in
    if Intmap.peek(m,n) = NONE then
      (n, put m n n, n::xs)
    else
      let
        val v = Intmap.retrieve(m,n)
      in
        prime(n+1, put (#1(Intmap.remove(m,n))) (n+v) v, xs)
      end
  end

val empty : int Intmap.intmap = Intmap.empty()
val init = (2, empty, [])

fun primes 1 = prime
  | primes n = prime o primes(n-1)

(* 100までの素数を生成 その1 *)
val primes25 = (primes 25) init

(* 100までの素数を生成 その2 *)
val r = prime init
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
val r = prime r
(* これを続ければいくつまででも素数を作れる *)
結果:
samples$ /cygdrive/c/mosml/bin/mosml prime.sml
Moscow ML version 2.01 (January 2004)
Enter `quit();' to quit.
[opening file "prime.sml"]
> val it = () : unit
> val it = () : unit
> val prime = fn : int * int intmap * int list -> int * int intmap * int list
  val empty =  : int intmap
  val 'a init = (2, , []) : int * int intmap * 'a list
  val primes = fn :
  int -> int * int intmap * int list -> int * int intmap * int list
  val primes25 =
    (97, ,
     [97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19,
      17, 13, 11, 7, 5, 3, 2]) : int * int intmap * int list
  val r =
    (97, ,
     [97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19,
      17, 13, 11, 7, 5, 3, 2]) : int * int intmap * int list
[closing file "prime.sml"]
もちろん、コンパイルしてもOK。
posted by ttate at 05:32| 🌁| Comment(0) | TrackBack(0) | プログラム言語 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。