These are chat archives for scalajp/functional

28th
May 2015
Kota Mizushima
@kmizu
May 28 2015 15:54
何か「データ構造」という用法に違和感があるのは自分が長く大学に居たからなのかどうなのか
自分にとってはデータ構造(!=抽象データ型)というのは、スキップリストや赤黒木、AVL木、B木みたいに具体的なメモリ上のレイアウトがある程度決まってるような構造をさす気がしていて
↑の方でよしださんとかがくぞさんが言っているデータ構造というのは抽象データ型をさしている気がする
たとえば、Stackは抽象データ型で、ListStackはデータ構造だ、みたいな使い分けをします
Manabu Nakamura
@gakuzzzz
May 28 2015 15:58
なるほど
Kota Mizushima
@kmizu
May 28 2015 15:58
ArrayStackとかももちろんあるわけですが、これもデータ構造。抽象データ型は操作集合と操作の前後での抽象データの変化のみから構成されているもの、というのが割と厳密な定義。
kenji yoshida
@xuwei-k
May 28 2015 16:34
上記の文脈だと、ほぼ Haskell の予約語の dataclass のどちらになるか?という意味でデータ(構造) って言ってましたね
eugene yokota
@eed3si9n
May 28 2015 17:27
それを明確にするために具象コレクションなどのことを「データ構造 (data structure)」の代わりに「データ型 (datatype)」と最近書くようにしてます、僕は
eugene yokota
@eed3si9n
May 28 2015 17:35
@kmizu 具体的なメモリ上のレイアウトという用法は C言語とかで data structure and algorithm みたいな言い方をするときの用法なので、どっちかと言うと伝統的(命令型より)な使い方になる?

因みに Okasaki さんを読むと、

Any discussion of data structure is fraught with the potential for confusion, because the term data structure has at least four distrinct, but related, meanings.

と書いてあって

  • An abstract data type.
  • A concrete realization of an abstract data type.
  • An instance of a data type.
  • A unique identity that is invariant under updates.
の4つの意味があるらしいです。
Kota Mizushima
@kmizu
May 28 2015 22:41
自分は2番目の意味でdata structureと呼んで居ましたね。データ構造とアルゴリズムの本(抽象データ型と具象データ型の区別を重視するもの)だと、だいたいこの二つは重視されてることが多い気が…
特に区別したい場合は、abstract data type(抽象データ型) / concrete data structure(具象データ構造)という使い分けをします
abstract data structure(抽象データ構造)という用語も聞くことがあります
eugene yokota
@eed3si9n
May 28 2015 22:45
「データ構造とアルゴリズム」から僕が連想するのは、C とか pascal の peudo code で書かれた実装ベタベタのやつですね。変数名とか全部一文字みたいな。今の関数型って、データ型と関数分けようって言っててそっちに先祖返りしてる。
Okasaki さんの本は purely functional data structure
Kota Mizushima
@kmizu
May 28 2015 22:46
ふーむ。自分は
de
で初めて抽象データ構造と具象データ構造の区別を意識したのですが、そこでは口を酸っぱくして両者の違いを説明していましたね。抽象データ構造をJavaのinterfaceで、具象データ構造をそのinterfaceをimplementsしたclassで実装することで両者の違いを意識させてた
eugene yokota
@eed3si9n
May 28 2015 22:49
interface だと型クラスとかになって、それは果たして構造なのか? みたいな話になりそう
逆に実装はどうでもいいけど、O(1) で伸びていくような linked list とかの抽象的な話は「構造」という言葉がよく当てはまる気もします。
Kota Mizushima
@kmizu
May 28 2015 22:50
その本では、抽象データ構造=各操作(集合)の事前条件、事後条件と不変条件で構成される、という感じですね。で、それはinterface + 契約で書ける
そこでは計算量自体はいったん捨象されます。具象データ構造で初めて計算量の話に。
自分的には、linked listは具体的な話(実装)のように思ったのですが…
headとtailへのポインタ(参照)があって、それから構成されている、みたいな。imperativeな話だと、データの末尾もポインタで持つことが多いですが。余談。
eugene yokota
@eed3si9n
May 28 2015 22:53
構造化プログラミングから Java/C++ の OO でモジュラーなのを「抽象データ型」とか言ってたのが構造になって、型クラスがある言語だと構造はあくまでメモリ上の話みたいな感じでしょうか。
Kota Mizushima
@kmizu
May 28 2015 22:54
そうですね。自分的な用法では。
eugene yokota
@eed3si9n
May 28 2015 22:54
interface + 契約って、そのままモナド則とかにつながりそうだし
Kota Mizushima
@kmizu
May 28 2015 22:55
それは結構鋭い指摘な気がします
実際、Scalaでは型クラスをtrait(≒interface)で、型クラスのインスタンスを実装クラスで実現してるわけですよね…
eugene yokota
@eed3si9n
May 28 2015 22:56
用語とかごった煮にした C++ が悪いですね。Scala も似た役割を担ってる。
Kota Mizushima
@kmizu
May 28 2015 22:57
C++が悪いのかはちょっと判断つかないですw
ちなみに、抽象データ型はLiskovの60年代~70年代の研究で提示された概念なのでかなり古い歴史があります
OO以前からある概念
自分がその辺区別したがるのはLiskovの影響が大きいかも…
eugene yokota
@eed3si9n
May 28 2015 23:00
そのまま抽象化を続けていけば、結局圏論とかに行き着くのではないでしょうか。
あと、「抽象」とは? という話になる。Liskov とかモジュール化プログラミングだと置換性とか重視してそうだけど、実際に CanBuildFrom とかって言って置換して大丈夫なのかっていう話もある。
eugene yokota
@eed3si9n
May 28 2015 23:06
A behavioral notion of subtyping って 1994年とかでは?
Kota Mizushima
@kmizu
May 28 2015 23:07
あ、それは比較的新しい方ですね。
は70年代に出てます
A behavioral notion of subtypingはその名前の通り、派生型が基底型に対して満たすべき条件について形式化して詳しく述べたので
特にOOの分析にとっては重要な概念ですね。実際、これが元になってLiskov substitution principleが出てきている。
eugene yokota
@eed3si9n
May 28 2015 23:11
この辺りと関数型でいう natural transformation とかどういう影響があったのか気になる
Kota Mizushima
@kmizu
May 28 2015 23:11
どうなんでしょうね。関数型方面のデータ構造との関連はあまり追ったことがなかったです
少なくとも研究上はつながりありそうですが

ちなみにLiskovの70年代のpaperは詳しくは読んでませんが、A behavioral notion of subtypingは穴が空くほど詳しく読んでます

あ、何故か強調表示にw
あ、そうか。#はmarkdownで見出しだからか。
eugene yokota
@eed3si9n
May 28 2015 23:16
Scala の implicit はどういう扱いなんだろうか
subtyping と型クラスが同じ次元で使われてるし
List から method を全部抜いた (パターンマッチ用の unapply を除く) ものだけ欲しいとか思うときがあって、それはやっぱり「構造」と言うしか無い
eugene yokota
@eed3si9n
May 28 2015 23:52