いろいろな操作を型クラスで統合して、さまざまなコンテナを同じ操作で扱えるようにしてみたら、いままで単純に扱えていた操作が型コンテキストを必要とするようになって、逆に面倒になってしまったという罠。 もっとも、リスト操作でもっとも重要な length,…

次のような指定はダメ。"multiply defined"といって怒られる。 class A q where a :: q -> {#Char} instance A {#a} where a _ = "Array" instance A {#Char} where a _ = "String" 次のような指定はOK。 class B q a where b :: (q a) -> {#Char} instance …

http://www.radiumsoftware.com/0605.html#060525 一定程度の誤りを許容することで高速化を図ったヒープのアルゴリズム

[id:lethevert:20070819:p1]であげた配列操作の中で、文字列のみと書いているのは、文字列のみ標準関数が提供されているのであるが、この実装はABCマシンで文字列専用のプリミティブが用意されていて、特別に効率よく操作できるようになっている。 で、これ…

++と+++の違いは、++は第２引数の評価がlazyなのに対して、+++はeagerなところです。 って、そんなことでいいのかなぁ

cons 連結 n番目の要素 最初の要素 残りのリスト n番目の要素の更新 スライス Clean list ［a:aa］ aa ++ bb aa !! n hd aa tl aa updateAt n elm aa aa % (i,j) Clean array - aa +++ bb (文字列のみ） aa.[n] aa.[0] - aa := (n,elm)（文字列のみ） aa % (…

[id:lethevert:20070815:p4] 修正版がリリースされたようです。 ftp://ftp.cs.ru.nl/pub/Clean/Clean22/linux/

http://ja.doukaku.org/45/ via [id:Gemma:20070818] なんですかこのErlangで書けといわんばかりのお題は？ それはともかく、こういうときはWSHという選択肢もあります。 http://msdn.microsoft.com/library/ja/default.asp?url=/library/ja/script56/html/w…

remove the minimumとfind the minumumが定数オーダーで、decrease keyが対数オーダーのPriority Queueのアルゴリズムについて考えている。 HeapもBinomial queueもFibonacci heapもremove the minimumが対数オーダーなんだよね。 リンクリストを使えば、rem…

[id:lethevert:20070815:p3] コンパイルしてみたら、gmp.cのコンパイルで警告が。 #include が不足しているみたいだ。 - ということで、小町算をリベンジしてみた。 [id:lethevert:20070718:p2]のプログラムとほとんど変わらない。Main.iclxが整数演算版で、…

プログラミング言語の機能で、例外ほど邪悪な機能はない。gotoなんて可愛いものである。 例外の悪い所は、いつどこで発生するか分からず、ひとたび発生すると、有無を言わせず残りの処理をスキップしてしまう。それに比べると、gotoはどこで発生するかが一目…

http://vag.wiki-site.com/index.php/UniqComb Cleanの一意型をうまく扱うためにさまざまなコンビネータを作ってみた人の記録。

遅レスながら。 [id:sshi:20070724:p1]とかhttp://alohakun.blog7.fc2.com/blog-entry-812.htmlとかのコメント欄で語られていることがいまいち理解できない。 eagerに評価してやると末尾再帰最適化がかかってループになる というのは何の話なのか？ 末尾再帰…

Haskellはデフォルトで遅延評価ですから、実装に関することは全部後で書くことになっているのですよ。 - 普通（って何が普通か知りませんが、私が普通だと思っている普通）は、末尾再帰の最適化というのは、次のような疑似アセンブリが FUNC_A: いろいろ処理…

[id:lethevert:20070813:p3] スタックオーバーフローだったようだ。しかし、gccがアレなせいで検知できなくて無限ループしてしまっていたらしい。

ftp://ftp.cs.ru.nl/pub/Clean/Clean22/linux/ こんなところにパッケージが。表のサイトからはリンクされてないよ？

いろいろ試しているわけですが、いまのところ、次のセッティングが一番効率がよくなるようで。 :: String2 :== String2Cons Char :: String2Cons a = ST !{#Char} | FT !(FingerTree Int String2Elem) BLOCKSIZE :== 512 :: String2Elem = {cArr :: !{#Char}…

文字列の連結に特化してテストプログラムを書いてみた 番号 内容 N=10000 N=50000 #0 文字配列 0.14 3.24 #1 文字配列 ブロック毎 0.02 0.32 #2 リスト 1.41 - #3 リスト reverse 0.00 0.01 #4 リスト ブロック毎 0.11 2.26 #5 String2 0.00 0.04 #6 String2…

簡単な速度調査とかやってみて分かったのは、文字列としての文字配列の性能というのはバカにならないくらいよいということだ。それは、Cleanのような非破壊的な文字配列であってもそうなのだ。 これは、まあ、結果を見てみればそうだろうと思ったのだけれど…

その上で、さらに少し書き換えてみて気づいたこと。 String2ではFinger treeの要素として、 :: String2Elem = {cArr :: !{#Char} ,sInd :: !Int ,eInd :: !Int } というレコードを生成している。で、どうもこのレコードの生成・アクセスコストがかなり影響し…

http://citeseer.ist.psu.edu/nocker91concurrent.html

http://d.hatena.ne.jp/NyaRuRu/20070813/p1 やっぱりデフォルト virtual はやめた方がいいんじゃね？ (C#) そうなのかー！

65536個を越える要素を追加すると、measure関数が返ってこなくなる。 - Cleanのバグ臭い。 module Test5 import StdBase, Test5Add Start = foldl add 0 (take 65536 (repeat 1)) implementation module Test5Add import StdInt add :: Int Int -> Int add a…

テストプログラムを書いてベンチマークを取ってみているのだけれど、組み込みの方が速い。それどころか、String2の方には見えてはいけない文字列が表示されているような気が・・・組み込みの方が速いのは、メモリの再利用をしやすいプログラムになっているか…

とりあえず、 -ci -lsetの２つは、常に付けておくとよいと思う。

適当なテストプログラムを書いて、速度調査してみた。 結果は次の通り。 組み込み文字列 $ ./bench_string 10000 "tabcdeabcdeqwertabcdeabcdertabcdeabcdeqwertabcdeabcdedeqwertabcdeabcdeqwertabcdeabcdeqwertabcdeabcdetabcdeabcdeqwertabcdeabcdertabcd…

最近、こればっか。 リストを与えられて、そこからFinger treeを作るという関数 listToTree を作るとして、どうやって作るか。 単純には、pushLを連続的に適用して、 listToTree ls = foldr pushL Empty lsとやって、pushLがO(1)なのでこれでもよいのだ（し…

右からリストで与えられた要素を追加するというもの。 FingerTreeというのは、左の方はリストと同順で並んでいるけれど、右の方はリストと逆順で並んでいるので、右から追加するという操作はちょっと複雑な動きになる。その辺を効率よく操作したいと思って、…

Finger treeの定義は、次のようにしていたのだけれど、 :: Tree v a = Empty | Single !a | Deep v !(Digit a) (Tree v (Node v a)) !(Digit a) :: Digit a :== [a]Digitの所が遅延リストだったので、不必要な非正格性が残ってしまっていた。そこで、正格リ…

http://cappuccino.jp/keisuken/logbook/20070812.html#p04 3D CMSの主要部分をScalaにする(暴走気味． すばらしい。