2010-02-05
Haskell でエラトステネスの篩
以下の方法が定番の方法である。
sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x /= 0] primes = sieve [2..]
しかしこれはとても遅いらしい。
という事でなんか良い方法無いのかなぁと考えた結果、現時点での素数の積を持っておいて、最大公約数を取ってどうにかすると良いのかなぁという感じになった。
sieve n (x:xs) = case gcd n x of 1 -> x:sieve (n*x) xs _ -> sieve n xs primes = sieve 1 [2..]
いやーでも対象となる数が大きければ大きい程遅くなるのは変わらんし、なんか大した事無いなぁ。ちょっとした改善にしかならなかった。
2010-02-04
2010-02-02
タプルと uncurry について考える
Haskell のタプルには色々な不満がある。2つ組のタプルに関しては uncurry,fst,snd などの便利な関数がいくつか定義されている。しかし、それ以外だとそうなっていない。
現在タプルで表現している物を全てペアに置き換える事で 標準で提供される関数をより広範囲に適用できるのではないか、と考えている。
以下が uncurry を利用した uncurry3,uncurry4,uncurry5 の定義である。
import Data.Graph.Inductive.Query.Monad uncurrySucc u = ((.).(.)) (uncurry u) mapFst uncurry3 :: (a -> b -> c -> d) -> (a,(b,c)) -> d uncurry3 = uncurrySucc uncurry uncurry4 :: (a -> b -> c -> d -> e) -> (a,(b,(c,d))) -> e uncurry4 = uncurrySucc uncurry3 uncurry5 :: (a -> b -> c -> d -> e -> f) -> (a,(b,(c,(d,e)))) -> f uncurry5 = uncurrySucc uncurry4
まあそんなに綺麗でもないのですが、どうでしょうか。
2010-01-27
最近購入した書籍
Amazon.com で購入。送料が約$9でしたが、Amazon.co.jp よりは安い。
2010-01-24
Haskell 的なパターンマッチについて考えてみる
Haskell はパターンマッチによる分岐が出来てとても便利というのは言うまでもない事なんだけど、これには少し不満がある。
因みにこの記事は俺言語メモ的な物ですから、Haskell にこういうのがあったら嬉しいというのとはちょっと違うかもしれません。
同じ値をどう表現するか
例えば、2つの同じ型の値を受け取って、もしそれらが同じであれば、その値に対して Just を適用した物を返し、そうでなければ Nothing を返すような関数を書くとする。
Haskell では以下のように書ける。
(\a b -> if a == b then Just a else Nothing)
自分としては、以下のように書けると嬉しい。
(\a a -> Just a | _ _ -> Nothing)
これは Wikipedia - Prolog # ユニフィケーションとバックトラックから得たアイディアである。
リテラルしか同値性テストができないのはおかしい
要するに、外側のスコープの変数とか普通の式をパターンマッチ式内に書きたいという話。
しかし実はそのまま外側のスコープの変数を参照させるのは表記上の問題で難しい。なぜなら、Haskell の代入の左辺は必ずパターンマッチ式で成り立っているため、それを許してしまうと外側のスコープで使われている名前を使う事ができなくなってしまうのである。
なので、パターンマッチ式内に普通の式を書きたい場合、それを明示的に区別する必要がある。具体的には以下のような感じに。
(\#(n*2) -> a | _ -> b)
まあ正直こっちは本当にいるのかなぁという感じがする。あまり煩雑になっても使いにくいので...。
