他人のHaskell日記

■ transposeは非汚染

transposeは縦横共に無限リストが扱える

*Main > take 5 $ map (take 5) $ transpose [[1..],[100..]]
[[1,100],[2,101],[3,102],[4,103],[5,104]]

やるなλ星人っ

■ IOモナドもprimitive

http://www.sampou.org/haskell/report-revised-j/standard-prelude.html

うーん、自分が知りたいところが分からなくて歯がゆい

■ seqの定義はprimitive

http://www.sampou.org/haskell/report-revised-j/standard-prelude.html

seq :: a -> b -> b
seq = ...       -- Primitive

これはつまり、逐次的な評価は、

他の関数の組み合わせだけでは表現が出来ないという事だろうか。

■ 関数も型定義できる?

Haskell ReportのPreludeより

 type  ReadS a  = String -> [(a,String)]

別名だからデータコンストラクタは宣言できない(ってデータじゃなくて関数だから当たり前か）

・・なのにどうやって使うんだろ

strHead ::(Read a) => ReadS a
strHead (x:xs) = [(read [x],xs)]
  where types =(x::Char,xs::String)

うーん・・確かに関数の型宣言に使える。

「ReadS a」における型変数aの存在理由が分からなかったので

その型変数を使うような関数を作ってみる

strHeadAs :: (Read a,Num a) => a -> ReadS a
strHeadAs n (x:xs) = [(read [x] `asTypeOf` n,xs)]
  where types =(x::Char,xs::String)

実行結果

*Main> strHeadAs (0::Int) "1abc"
[(1,"abc")]
*Main> :t it
it :: [(Int, String)]
*Main> strHeadAs (0::Integer) "1abc"
[(1,"abc")]
*Main> :t it
it :: [(Integer, String)]

確かに多相的になっている。

なんだか使いこなすのは大変そうだ

あっ・・部分適用して「関数を返す」ようにすれば便利なのでは

strHeadAsInt     = strHeadAs (0::Int)
strHeadAsInteger = strHeadAs (0::Integer)

実行結果

*Main> strHeadAsInt "1abc"
[(1,"abc")]
*Main> :t it
it :: [(Int, String)]
*Main> strHeadAsInteger "1abc"
[(1,"abc")]
*Main> :t it
it :: [(Integer, String)]

うん、動く。

あああ、つまりつまり、もしかして

*Main> (strHead::ReadS Int) "1abc"
[(1,"abc")]
*Main> :t it
it :: [(Int, String)]
*Main> (strHead::ReadS Integer) "1abc"
[(1,"abc")]
*Main> :t it
it :: [(Integer, String)]

なるほど、strHeadAsなんていらない！

型変数恐ろしい子っ

■ クラスメソッドがわからない

クラスメソッドの中では引数を二つとるタイプの関数が定義されているけど

その引数がともに多相型で、しかも別の種類だった場合、

そのクラスメソッドはどちらの多相型のクラスに書くべきなの？（というか書けるの？）

■ 素数列をつくろう

http://ll.jus.or.jp/2006/blog/doukaku1

面白そうなのでミラーテストバージョンを書いてみました

http://www.faireal.net/articles/7/03/#d30129

このサイトを参考にしました。

import List

main =  putStrLn $unwords $ map show $ primes 100
primes n = 2:filter (check.map head.group.modList)[3..n] where
  check (1:[]) =  True
  check (1:(-1):_) = True
  check _ = False
  modList n = map (g.(`mod` n).(2^)) (f (n-1)) where
    f x | even x = x:f (x`div`2)
        | otherwise = x:[]
    g s | s > 1 = s - n 
        | otherwise = s

実行結果

*Main> main
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

■ 擬素数狩り

素数のフリしてお高くとまっている偽素数どもを発見し晒し上げる

正しい素数列としてid:nobsunのエラトステネスのふるいを

(http://haskell.g.hatena.ne.jp/nobsun/20060617)

フェルマーテストとしてd:id:nurseの書いたものをhaskellに書き換えたものを使います。

(http://d.hatena.ne.jp/nurse/20060616)

import List

--エラトステネスのふるい(id:nobsun)
sieve (p:ps) = p : sieve [q | q <- ps, q `mod` p /= 0]
primes = sieve [2..]

--フェルマーテスト(id:nurse)のHaskell版
primes' = 2:filter(\x -> ((2^(x-1)) `mod` x) == 1)[3..]

--ミラーテスト(id:taninsw)
primes'' = 2:filter millerTest [3..] 
millerTest = check.map head.group.modList where
  check (1:[]) =  True
  check (1:(-1):_) = True
  check _ = False
  modList n = map (g.(`mod` n).(2^)) (f (n-1)) where
    f x | even x = x:f (x`div`2)
        | otherwise = x:[]
    g s | s > 1 = s - n 
        | otherwise = s

--テスト用コード

--それぞれの素数列のn番目の要素を抜き出す
(!!!) n =  map ($ n)  [(primes !!),(primes' !!),(primes'' !!)]

--「正しい素数列」と「擬素数を含む素数列」から「（素数の振りをした）擬素数の配列」を作る
unmatch x@(xh:xt) y@(yh:yt) 
  | xh >  yh = yh:unmatch x yt  
  | xh <  yh = xh:unmatch xt y  
  | xh == yh = unmatch xt yt

実行結果

*Main> take 10 $ unmatch primes primes'                       --擬素数(最初の10個)
[341,561,645,1105,1387,1729,1905,2047,2465,2701]
*Main> take 10 $ unmatch primes primes''                      --強擬素数(最初の10個)
[2047,3277,4033,4681,8321,15841,29341,42799,49141,52633]

*Main> takeWhile (<10000) $ unmatch primes primes'            --擬素数(10000以下)
Loading package haskell98-1.0 ... linking ... done.
[341,561,645,1105,1387,1729,1905,2047,2465,2701,2821,3277,4033,4369,4371,4681,5461,6601,7957,8321,8481,8911]
*Main> takeWhile (<10000) $ unmatch primes primes''           --強擬素数(10000以下)
[2047,3277,4033,4681,8321]

ミラーテストで現れる擬素数は、フェルマーテストでも擬素数になっています。

逆にいえば、フェルマーテストを通過できなかったものは、ミラーテストも通過できない、ということです。

ちなみに、フェルマーテストもミラーテストも中身はまったく理解していません。

■ コードの短さ

print "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97";

より

main=print$takeWhile(<101)$s[2..]where s(n:p)=n:s[q|q<-p,q`mod`n/=0]

の方が短い。

フェルマーテストならもっと短い。

main=print$2:filter(\x->2^(x-1)`mod`x==1)[3..100]

■ どうして誰もベーシックを使わないんだー素数計算BASIC版

（Haskell日記じゃない・・。）

N88-Basic フェルマーテストバージョン

10 CLS
20 PRINT 2;
30 FOR I = 3 TO 100
40   IF (2^(I-1)) MOD I = 1 THEN PRIN I
50 NEXT I

う・・オーバーフローした・・。

とにかく自分より小さい数で割っちまえばいいんだ！

100 CLS
110 DIM I,J
120 PRINT 2;
130 FOR I = 3 TO 100
140 FOR J = 2  TO SQR(I)
150 IF I MOD J = 0 THEN GOTO 180
160 NEXT J
170 PRINT I;
180 NEXT I

昔はQuickBasicとVisualBasicの人間だった。

■ NScripter版素数計算

（もはやLLでは無い・・・。）

使ったことがないのでリファレンスを読みながら作成。

最初はfor文があることに気付かなかった。

雰囲気はなんとなくアセンブラっぽいですね。

*define
game
*start
caption "100までの素数列を作ろう。"
“２” /
for %0=3 to 100
   mov %4,0
   mov %5,%0
   dec %5
   for %1=2 to %5
     mov %2,%0
     mod %2,%1
     if %2=0 mov %4,1
   next
   if %4=1 jumpf
　 “ /
   %0 /
   ” /
   ~
next
click
end 

■ Excelで素数計算。

（・・・すでに言語ですらない。）

VBSは禁じ手にしてセルを利用して求める方針。

Excelも使ったことがないので四苦八苦。(Lotus 1-2-3なら弄ったことある)

アドイン入れないと最大公倍数関数GCDが使えないし

ヘルプみようとしてもイルカが邪魔するしで大変。

セルの相対指定絶対指定に戸惑ったもののなんとか出来た。

	2	3		5		7				11
		13				17		19		
		23						29		
31						37				
41		43				47						53						59		61		
				67				71		
73						79				
83						89				
				97			

縦

R1 C1～R100 C1 は順番に１～100

横

R1 C1～R1 C100 は順番に１～100

R2 C2～R2 C100 は「OR(GCD(RC1,R1C)=1,GCD(RC1,R1C)=R1C)」

　つまり2との最大公約数が1かまたはその値になるときTrue

全体

R3 C2～R100 C100 は「AND(OR(OR(GCD(RC1,R1C)=1),RC1>=R1C),R[-1]C)」

　つまり「一つ上のセルがTrue」かつ、一番左のセルの値と一番上のセルの値の公倍数が、

　一番上のセルの値あるいは１になるときTrue

結果表示部

R101 C1～R101は「IF(R[-1]C,R1C,"")」

　つまり「一つ上のセルがTrue」ならば値を表示し、そうでなければ表示しない

極めてシンプル。

■ 素数を求めるプログラムBATファイル版

・・を作ろうと弄ってたら朝になってしまった・・。

for /L %%I in (2,1,100) do echo "ttt" > %%1.prime

ファイルを作って削除していくことでフルいにかけようと思って

ファイル生成してからDIRしたらどうしても順番が変わってしまう。

ファイル名で並び替えてもダメ、日時で並び替えてもダメ

うーん・・・巨大なファイルでも生成させるべきかな・・・

・・寝よう

■ 独り言

brainfuckやwhitespaceで作る人が出てこないかな.

正規表現で出来るみたい(http://blog.livedoor.jp/dankogai/archives/50534089.html)

だからオートマトンやパーサーでも出来そうだ。

専用のLL言語作って1バイトで出来るとか言ったらやっぱ怒られるんだろうな。