Scalaz勉強会 データ構造ひと巡り

gistfile1.rst

Scalazのデータ構造ひと巡り

発表場所:	Scalaz勉強会
資料のライセンス:	CC-BY-SA 4.0

自己紹介

• なかやん・ゆーき / ぺんぎん / もみあげ
• @pocketberserker / id:pocketberserker
• 通りすがりの社会人2年目
• Microsoft MVP for F# (2013/04 ～ 2015/03)
• たぶん Scala ビギナー
• 日課: Scalaz , GHC 周辺ライブラリの F# への移植実験

中盤なので

ゆるくデータ構造を見ていきましょう

データ構造 (data structures)

• 計算機科学でデータの集まりを効率よく扱うためのもの
• immutableなものもあるよ

Scalazのデータ構造っぽいもの

7.1.0 RC1 時点で deprecated でないもの(見落としあるかも)

• Cord
• DList (Difference lists)
• Diev (Discrete Interval Encoding Tree)
• FingerTree (2-3 finger tree)
• Heap
• ImmutableArray
• ==>> (HaskellのData.Mapのことらしい)
• NonEmptyList
• Tree (Rose Tree)
• Zipper

Cord

• https://github.com/scalaz/scalaz/blob/3bc05e3cef48abd6aec5f886e871260056684be4/core/src/main/scala/scalaz/Cord.scala
• String (紐) の強化版
• 文字列同士の結合やコピー、substring が高速
• 似たデータ構造として Rope があるが、Scalaz では 7.1.0 で deprecated
• 実装に FingerTree を利用
• Show に利用されている

DList

• https://github.com/scalaz/scalaz/blob/3bc05e3cef48abd6aec5f886e871260056684be4/core/src/main/scala/scalaz/DList.scala
• リストの append 操作が O(1)
• 実装に Trampoline を利用

Diev

昨日存在を知ったので飛ばします

• https://github.com/scalaz/scalaz/blob/3bc05e3cef48abd6aec5f886e871260056684be4/core/src/main/scala/scalaz/Diev.scala

FingerTree

• https://github.com/scalaz/scalaz/blob/3bc05e3cef48abd6aec5f886e871260056684be4/core/src/main/scala/scalaz/FingerTree.scala
• sequence の一種
• 連結や分割がならし計算量で O(log N)
• なぜか wikipedia の解説が充実している
• 論文公開が2006年なのでわりと新しめ
• 1000行以上ある

Heap

• https://github.com/scalaz/scalaz/blob/3bc05e3cef48abd6aec5f886e871260056684be4/core/src/main/scala/scalaz/FingerTree.scala
• bootstrapped skew binomial heaps をベースにしている
• https://github.com/ekmett/heaps/ の移植らしい

==>>

• https://github.com/scalaz/scalaz/blob/3bc05e3cef48abd6aec5f886e871260056684be4/core/src/main/scala/scalaz/Map.scala
• HaskellのData.Map
• 平衡二分木ベース
• Order に依存
• コードが長い

NonEmptyList

• https://github.com/scalaz/scalaz/blob/3bc05e3cef48abd6aec5f886e871260056684be4/core/src/main/scala/scalaz/NonEmptyList.scala
• 空でないことが保障されているリスト的なもの

Tree

• https://github.com/scalaz/scalaz/blob/3bc05e3cef48abd6aec5f886e871260056684be4/core/src/main/scala/scalaz/Tree.scala
• 多分木
• 関数プログラミング入門 Haskellで学ぶ原理と技法 に解説がある

Zipper

• https://github.com/scalaz/scalaz/blob/3bc05e3cef48abd6aec5f886e871260056684be4/core/src/main/scala/scalaz/Zipper.scala

‐ 要素の更新を簡単に - データ構造をたどる操作を効率的に - すごいHaskell楽しく学ぼう にちょっとした説明があったような

データ構造でよく現れる型クラス

• Foldable
• Semigroup
• Monoid
• Reducer

懸念

• 性能評価されていないらしい?

参考文献

• Purely Functional Data Structures(Chris Okasaki - 1998)
• 関数プログラミング入門 Haskellで学ぶ原理と技法(オーム社)
• すごいHaskell楽しく学ぼう(オーム社)

‐ 一部データ構造のコメントに記載されている論文

以下、時間が余った時用

私と Scalaz

• Iteratee を調べていたら見つけた
• Scala 基礎勉強会でさらに興味を持った

Scalaz の学び方?

ひたすら移植(写経)してみる