ブログトップ 記事一覧 ログイン 無料ブログ開設

Hatena::Diary::pi8027

 

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-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-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)

まあ正直こっちは本当にいるのかなぁという感じがする。あまり煩雑になっても使いにくいので...。

最新コンパイラ構成技法の誤植

250ページの真ん中よりちょっと下あたり。

メモり
メモリ

他にも色々ありそうですがとりあえず。あと出版社には連絡しました。