falsandtru https://blog.hatena.ne.jp/falsandtru/ falsandtruのメモ帳 https://falsandtru.hatenablog.com/ Haskell Haskellの差分リストは一般に([1,2,3] ++) . ([4,5,6] ++)のようにセクションで示される。しかしこれは連結の際に左側のリストの要素をたどって末尾を見るので計算量がリストの長さに比例して増加しO(n)となる。一方CTMCP(コンピュータプログラミングの概念・技法・モデル)では要素をたどらず直接末尾を見るので計算量がリストの長さに比例して増加せずO(1)となる実装がOzにより示され、そしてこの効率性が差分リストの特徴とされている。Haskellも遅延評価の場合は連結コストが使用時のコストに同化されO(1)となるかもしれないが正格評価の場合は連結時に直ちにO(n)のコスト… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ffalsandtru.hatenablog.com%2Fentry%2Fdifference-list-in-haskell" title="Haskellの差分リストはなんちゃって差分リストではないか？ - falsandtruのメモ帳" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-12-29 00:00:00 rich https://falsandtru.hatenablog.com/entry/difference-list-in-haskell 1.0 100%