![Haskell 標準の配列を使う
配列を作るには？
→?array 関数を使う（或いは listArray ）
array?(0,?3)?[(0,?1),?(1,?2),?(2,?4),?(3,?9)]
array?((1,?1),?(2,?2))?[((1,1),?'a'),?((1,2),?'a'),?((2,1),?'z'),?
((2,2),?'d')]
listArray?(1,?100)?[0,?0?..]
インデックスには、 Int,?Char 及びそのタプルなどが
使える。
厳密には Ix 型クラスのインスタンスがすべて使える。
ここでは説明は省略。
? ?](https://image.slidesharecdn.com/00array-121002102559-phpapp02/85/-8-320.jpg)
![Haskell 標準の配列を使う
配列 ary の要素にアクセスしたい → (!) 演算子
例） let?x?=?ary!2?in?…
???????let?x?=?ary!(0,?3)?in?…
配列 ary の要素を更新したい → (//) 演算子
例） let?ary'?=?ary//[(1,?2),?(3,?0)]
???ary[1] を 2 に、 ary[3] を 0 に更新
ただし、これには後に述べるように罠が隠れている。
? ?](https://image.slidesharecdn.com/00array-121002102559-phpapp02/85/-10-320.jpg)
![なんでそんなことになってんの？
…… ではさすがにあんまりなので。
Array が正格評価する仕様だと、例えば変数 x,?y,?
z を用いて
ary?=?array?(1,?3)?[(1,?x),?(2,?y),?(3,?z)]
のようにに配列を作ると、 x,?y,?z は配列作成時に
全て評価されなければならない。（評価しないと
格納する値がわからない）
? ?](https://image.slidesharecdn.com/00array-121002102559-phpapp02/85/-15-320.jpg)
![「 Array と参照透明性」
に関する孔明の罠
つまり？
ary?=?array?(1,?2)?[(1,?1),?(2,?2)]
として、
ary!1
let?ary'?=?ary//[(1,?2)]?in
ary!1
は同じ値であってほしいなければならない。
? ?](https://image.slidesharecdn.com/00array-121002102559-phpapp02/85/-21-320.jpg)
![より進んだ話題
Haskell には並列処理用行列
repa （ [hackage]http://hackage.haskell.org/packa
ge/repa ）という、データ並列プログラミングをサ
ポートする特殊なライブラリもある。
→ 配列というよりは「行列」
→ ついこの間（ 2012/9/24 ） GHC?7.6 にも対応
DiffArray なんてのもある（ Immutable かつ更新も
それなりに速い）
[hackage]http://hackage.haskell.org/package/diffa
rray
? ?](https://image.slidesharecdn.com/00array-121002102559-phpapp02/85/-49-320.jpg)
More Related Content
What's hot (20)
Viewers also liked (20)
Similar to すごい配列楽しく学ぼう (12)
すごい配列楽しく学ぼう
- 1. すごい配列楽しく学ぼう ~ Haskell の配列事情 ~ @xenophobia__ ? ?
- 2. テーマについて 勉強会をやるらしい → 各 λ 人の好きな題材でいいらしい。 → じゃあ Haskell で何か話そう。 → でもすごい H 本出たし基本的なことはもう話題と して出尽してるよな…… → あれ？この本配列について書いてなくね？ →?λ ＜ Haskell の配列も楽しく学ぼう！ ? ?
- 3. Haskell とは！ なんてことを話している時間はない。 とりあえず今後の話に関わることとしてこれぐらい。 型に厳しい（強い静的型付けである） キャストとかゆとりな事はしない 型が合ってないと絶対許してくれない 参照透明性が（基本的には）成り立つ IO ?破壊的変更の扱いがめんどい特殊 unsafe ほげほげの話はしない 「型クラス」がある 「型クラス」は共通の性質を持った型の集まり ある型クラスに関して polymorphic な関数とか書ける ? ?
- 4. Haskell の配列について Haskell では、コレクションは普通リスト型で扱う。 配列はあんまり話題にならない気がする（すごい H 本にも記述は多分ない？ RHW にはあった） 調べるといろいろ (Array,?UArray,?IArray,?MArray,? IOArray,?...) でてきてよくわからない。 でも…… プロコンとかだと使いたい。 できるだけ速いほうがいい。 ? ?
- 5. Agenda とりあえず普通の配列（ Array,?UArray ） O(1) で変更できなきゃ配列じゃない！ (IOArray,? IOUArray) 型クラスの話をしよう (IArray,?MArray) ? ?
- 6. Agenda とりあえず普通の配列（ Array,?UArray ） O(1) で変更できなきゃ配列じゃない！ (IOArray,? IOUArray) 型クラスの話をしよう (IArray,?MArray) ? ?
- 7. Haskell 標準の配列を使う Array,?UArray （違いはあとで。） Array は Data.Array( または Data.Array.IArray) に ある。 UArray は Data.Array.Unboxed にある。 ? ?
- 8. Haskell 標準の配列を使う 配列を作るには？ →?array 関数を使う（或いは listArray ） array?(0,?3)?[(0,?1),?(1,?2),?(2,?4),?(3,?9)] array?((1,?1),?(2,?2))?[((1,1),?'a'),?((1,2),?'a'),?((2,1),?'z'),? ((2,2),?'d')] listArray?(1,?100)?[0,?0?..] インデックスには、 Int,?Char 及びそのタプルなどが 使える。 厳密には Ix 型クラスのインスタンスがすべて使える。 ここでは説明は省略。 ? ?
- 9. Haskell 標準の配列を使う 型は？ C などと違い、インデックスもいろいろ使える。 → インデックスも型パラメタとして与える。 インデックスが Int で要素が String の Array なら、 Array?Int?String? となる。 インデックスが (Char,?Char) で要素が Int の UArray なら、 UArray?(Char,?Char)?Int となる。 ? ?
- 10. Haskell 標準の配列を使う 配列 ary の要素にアクセスしたい → (!) 演算子 例） let?x?=?ary!2?in?… ???????let?x?=?ary!(0,?3)?in?… 配列 ary の要素を更新したい → (//) 演算子 例） let?ary'?=?ary//[(1,?2),?(3,?0)] ???ary[1] を 2 に、 ary[3] を 0 に更新 ただし、これには後に述べるように罠が隠れている。 ? ?
- 11. Array/UArray の違いって？ Array 型と UArray 型は、使い方はほぼ同じ。 じゃあ違いは？ Array は Box 化されている Uarray は Box 化されていない (? ? _ ? `) ？ ＜ おまえは なにを いってるんだ ? ?
- 12. Array/UArray の違いって？ つまり Array は、オブジェクトへのポインタを持った配列 UArray は、値そのものを入れる配列 もっと言うと Array は Lazy な配列 UArray は Strict な配列 ? ?
- 13. Array/UArray の違いって？ Array の要素を参照するときの動作 ポインタが示す先に行き、オブジェクトを返す そのオブジェクトの値が必要になったら評価する。 もちろん、オブジェクトが評価済みならその値自体を 返す。 0 1 未評価 評価済み Eval 2 10 ＊ 10 100 3 ? ?
- 14. なんでそんなことになってんの？ 知らん。 ? ?
- 15. なんでそんなことになってんの？ …… ではさすがにあんまりなので。 Array が正格評価する仕様だと、例えば変数 x,?y,? z を用いて ary?=?array?(1,?3)?[(1,?x),?(2,?y),?(3,?z)] のようにに配列を作ると、 x,?y,?z は配列作成時に 全て評価されなければならない。（評価しないと 格納する値がわからない） ? ?
- 16. なんでそんなことになってんの？ 「 x を配列に入れる」というロジックに「 x を評価す る」ことは必要か？ たとえば ary のうち一つの要素にしかアクセスしな いかもしれない。 → 「アクセスしない＝使わない」ってことじゃない の？ ? ?
- 17. なんでそんなことになってんの？ λ ＜使わないのに評価されるのは遅延評価とし ておかしい！（ Haskell は call?by?need の遅延評 価！） 要素が何であるかの評価は、実際にその要素の値 が必要になるまで遅延するのがよい！ てな感じなんじゃないですかね。知らんけど…… ? ?
- 18. UArray(Unboxed?Array) Q. じゃあ UArray って何？ A.?Array 遅い！って人のために。 UArray はポインタを介さない分 Array よりアクセ スが速い＆場所とらない。 速さとヒープ領域を気にするならこっち使いましょ う。 ? ?
- 19. Agenda とりあえず普通の配列（ Array,?UArray ） O(1) で変更できなきゃ配列じゃない！ (IOArray,? IOUArray) 型クラスの話をしよう (IArray,?MArray) ? ?
- 20. 「 Array と参照透明性」 に関する孔明の罠 さっき (//) という「更新」演算子がでてきた。 でも、 Haskell の関数は（基本的には）参照透明性 が成り立ってなければならない。 参照透明性 ： 関数と引数の組によって、返り値が 一意に決まる。 ? ?
- 21. 「 Array と参照透明性」 に関する孔明の罠 つまり？ ary?=?array?(1,?2)?[(1,?1),?(2,?2)] として、 ary!1 let?ary'?=?ary//[(1,?2)]?in ary!1 は同じ値であってほしいなければならない。 ? ?
- 22. 「 Array と参照透明性」 に関する孔明の罠 しかし、 ary を破壊的に更新してしまった場合、 ary!1 が元の値を返すかどうかはわからない。 ary!1 が更新前に評価されれば 1 が返り、 ary!1 が更新後に評価されれば 2 が返る。 → 参照透明性に反する！ ary!1 はいつ評価しても同じ値を返さなければなら ない。 ? ?
- 23. 「 Array と参照透明性」 に関する孔明の罠 じゃあどういう実装になってんの？ → 単純に、 ary には変更を加えず ary' 用の配列を新しく作る。 → これでどこをいつ参照しても矛盾は起きない。 やったね（？） ? ?
- 24. 「 Array と参照透明性」 に関する孔明の罠 …… なにもうまくいってません。 問題 1 ：そもそも「更新」じゃなくて「新規作成」演算 子になってる 問題 2 ：計算量 O(sizeof(ary)) →? プロコンでうっかり使ったりすると死ぬ 結論： (//) は更新する演算子ではなく、更新され た配列を新規作成する演算子 ? ?
- 25. 補足 注 1 ）ドキュメントにも Incremental?array?updates と書いてあってまぎらわしい。 注 2 ） Data.Array.IArray には、「殆どの IArray の インスタンスにおいて更新には O(N) かかる」と 書いてある。 注 3 ） Data.Array.IArray の (//) 関数の仕様自体が O(N) の計算量に本質的に関わっているわけで はない。（実際、もっと速い更新を実現する DiffArray などの IArray インスタンスもある） ? ?
- 26. うまい解決法はないか 破壊的更新ができれば文句ない。 Haskell で破壊的操作をうまく扱う方法として IO モナドがある。 IO モナドの文脈中ならうまいこと破壊的操作を扱 える。 →?IO モナドの中でしか使えない配列を作れば万 事解決！ ? ?
- 27. IOArray/IOUArray Data.Array.IO にどっちも定義されている。 作成?参照?更新は全て IO アクション。 → アクションの実行順序は保証されるので、参 照と更新の順序が入れかわったりしない！ ? ?
- 28. IOArray/IOUArray 作成： newArray(newArray_,?newListArray) newArray?(lb,?ub)?x? で、インデックスが lb ? ub の x で初期化された配列を返すアクションを返す。 参照： readArray readArray?ary?i で、 ary の i 番地の値を返すアクショ ンを返す。 更新： writeArray writeArray?ary?i?x で、 ary の i 番地の値を x に変更 するアクションを返す。 ? ?
- 29. IOArray/IOUArray 使い方 IO モナドの中で使う。 do?ary?←?newArray?(1,?10)?0 ??x?←?readArray?ary?1 ??writeArray?ary?1?3 ??y?←?readArray?ary?1 ??... x,?y? には 0,?3 がそれぞれ束縛される。 ? ?
- 30. 参照透明性は？ さっきのプログラムの 2 つの readArray?ary?1 って 別々の値を返してね？ → readArray?ary?1 はあくまで両方「 ary からイン デックス i の値を取り出す操作」を表すアクション なのであって、 x,?y を返す関数ではありません。 ? ?
- 31. Pros?&?Cons 正真正銘の O(1) 更新が可能！ ただ、 IO に汚染される上、インタフェースが多少め んどい。 ? ?
- 32. 備考 IOArray 以外にも、 STArray など破壊的代入がで きる配列はある。 IO モナドと違い ST モナドは外に脱出できるの で、 IO 操作を他に使わないならこっちのほうが いいかも。 IOArray と使い勝手は一緒 ? ?
- 33. 補足（ 1 ） thaw/freeze 関数を用いて普通の配列と可変配列 との相互変換もできる。 thaw （解凍）が Immutable?→?Mutable の変換 freeze （凍結）が Mutable?→?Immutable の変換 ? ?
- 34. 補足（ 2 ） もちろん thaw も freeze も O(N) 。 ドキュメントにもちゃんと” by?taking?a?complete?copy? of?it.” とある。 こういうときこそ STArray 使うといいかもしれない。 手前味噌ですが STUArray を用いたエラトステネス の篩実装例 http://d.hatena.ne.jp/g940425/20110827/1314442246 後半で unsafe な関数使ってるけど……こういう使い かたなら問題ないはず。 ? ?
- 35. Agenda とりあえず普通の配列（ Array,?UArray ） O(1) で変更できなきゃ配列じゃない！ (IOArray,? IOUArray) 型クラスの話をしよう (IArray,?MArray) ? ?
- 36. 抽象化したい！ Uarray と Array 、 IOUArray と IOArray は Box 化 / 非 Box 化の違いでしかない。 → これらの違いを無視した一般的なインタ フェースの関数を書きたい。 ? ?
- 37. 例えば…… sumA ： Int 要素を持つ Array の全要素の和 ? ?
- 38. 例えば…… sumA をそのまま UArray に使おうとすると、当然の ように型エラーで怒られる。 ? ?
- 39. 例えば…… 型ごとに関数を用意すればお k ！ ? ?
- 40. いやいや ＜「お k ！」じゃねえ！ 関数本体全く同じじゃねえか！ こういう、形がほとんど同じ関数を連ねるのを 「ボイラープレート（ boilerplate ）」という → Haskeller が最も嫌うもの 私も大嫌いです 形が同じなら、まとめてかけるはず ? ?
- 41. IArray/MArray 変更不可配列 (Immutable?Array) を抽象する型ク ラスが IArray 可変配列 (Mutable?Array) を抽象する型クラスが MArray 型クラス： Iarray/MArray はそれ自体「型」ではな い（ IArray? ? 型の値、は存在しない） ? ?
- 42. IArray/MArray IArray?a?e ： e 型の要素を持つ変更不可配列 a Marray?a?e?m ： m モナドのコンテクストで変更可能 な、 e 型の要素を持つ配列 a ? ?
- 43. 例ふたたび IArray を使って sumA を抽象化 GHC 拡張 FlexibleContexts が必要（理由は後述） ? ?
- 44. 例ふたたび sumA?::?IArray?a?Int?=>?… → 「 a が Int を要素に持つ変更不可配列」 という型制約をかけている sumA?::?…?=>?a?Int?Int?→?Int →?a?Int?Int?→?Int という型を持つので、 a として当てはまる（＝ IArray?a?Int というインス タンスが宣言されている）もの全てに適用可能 ? ?
- 45. 例ふたたび Data.Array.IArray にインスタンスとして IArray?Array?e IArray?UArray?Int が宣言されている。（ e は型変数で、なんでもよい） → a が Array でも UArray でも型が合う！ IArray?Array?Int?=>?Array?Int?Int?→?Int OK ！：インスタンス IArray Array e がある IArray?UArray?Int?=>?UArray?Int?Int?→?Int OK ！：インスタンス IArray UArray Int がある ? ?
- 46. 補足（ 3 ） Q. かける制約は IArray?a?e でよかったのでは？ A. 実は、 IArray?UArray?e という要素の型 e につい て一般化されたインスタンスはない。 (Data.Array.UArray のドキュメント参照） → なのでこの例では IArray?a?Int のインスタンス 宣言を使っており、そのため制約が IArray?a?Int となっている。 IArray?Array?e?=>?Array?Int?Int?→?Int OK ！：インスタンス IArray Array e がある IArray?UArray?e?=>?UArray?Int?Int?→?Int NG ！：インスタンス IArray UArray e はない ? ?
- 47. 補足（ 4 ） 本来、型制約に具体的な型を入れることはできな い。 → IArray?a?Int という制約はふつう許されない。 これを許可するのが FlexibleContexts 拡張 ? ?
- 48. 総括 Haskell でも普通に配列使える しかし、速いプログラムにするには工夫が要る →使えるところでは Unboxed な配列を使う、とか 抽象化もできる → ただ、なんでもかんでも抽象化すればいいと いうわけじゃない。 Lazy/Strict が本質的な場面 もあるだろうし、競技プログラミングでわざわざ 使いもしないのに抽象化した関数を書くのは得 策でない。 ? ?
- 49. より進んだ話題 Haskell には並列処理用行列 repa （ [hackage]http://hackage.haskell.org/packa ge/repa ）という、データ並列プログラミングをサ ポートする特殊なライブラリもある。 → 配列というよりは「行列」 → ついこの間（ 2012/9/24 ） GHC?7.6 にも対応 DiffArray なんてのもある（ Immutable かつ更新も それなりに速い） [hackage]http://hackage.haskell.org/package/diffa rray ? ?