##########################
Scalazのデータ構造ひと巡り
##########################
:発表場所: `Scalaz勉強会 `_
:資料のライセンス: `CC-BY-SA 4.0 `_
自己紹介
========
.. image:: https://dl.dropboxusercontent.com/u/57478758/pbsk.jpg
- なかやん・ゆーき / ぺんぎん / もみあげ
- @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 の学び方?
----------------
ひたすら移植(写経)してみる