Purely Functional Data Structures 写経 2.1 Lists

Purely Functional Data Structures

関数型言語ならではのデータ構造を身に付けるために Purely Functional Data Structures を購入しました。

中のサンプルコードが Standard ML で書かれているんですね。そのままでも意味は読み取れるんですが、より理解を深める為に Haskell で書き直してみることにしました。

ってよくよく見たら巻末に Haskell でのコードが載ってる＼(＾o＾)／　でも Queue からなのでそこまでやってみようと思いますorz

まずは P7〜P11 までの 2.1 List って章です。
基本的な Cons Cell についての章ですね。

Standard ML では signature と structure でインターフェイスと実装が分けられるみたいですね。Java の interface と class みたいなものでしょうか？ Haskell の class と instance とはちょっとニュアンスが違う気もするんですが、とりあえずいける所まで class と instance でやってみましょう。

class Stack s where
  empty :: s a
  isEmpty :: s a -> Bool
  cons :: a -> s a -> s a
  head' :: s a -> a
  tail' :: s a -> s a

まずはインターフェイスの定義。Listの章なのに Stack って名前が謎ですし、FILOとか気にしてなさそうですが、まぁ置いておきましょう。

本では普通に head と tail でしたが、既存の関数名とぶつかってめんどくさいので ' をつけました。今後もその辺の細かいところは勝手に変えちゃいます。

instance Stack [] where
  empty = []
  isEmpty = null
  cons x xs = x : xs
  head' = head
  tail' = tail

組み込みのリストを使っての実装。
ま、こんなとこでしょう。

data CustomStack a = Nil | Cons a (CustomStack a) deriving (Show)

instance Stack CustomStack where
  empty = Nil

  isEmpty Nil = True
  isEmpty (Cons _ _) = False

  cons = Cons

  head' Nil = error "Empty"
  head' (Cons a _) = a

  tail' Nil = error "Empty"
  tail' (Cons _ s) = s

自前実装の例。これも普通に。

(+++) :: Stack s => s a -> s a -> s a
(+++) xs ys = if isEmpty xs then ys else cons (head' xs) $ (tail' xs) +++ ys

append の実装。
ちょっとてこずりました。型宣言時に型classを使いたい場合は => で宣言しないとダメなんですね。

(+++) :: Stack a -> Stack a -> Stack a -- これは NG
(+++) :: CustomStack a -> CustomStack a -> CustomStack a -- これは OK
(+++) :: Stack s => s a -> s a -> s a -- これは OK

普通の data だと大丈夫。これは何が理由なんでしょうか？

それから当たり前ですが CustomStack と List の連結は型エラーになりました。統一的に扱えるようにするべきでしょうか。この辺は Java の interface を触ってると違和感がありますね。

気を取り直して次。

update :: Stack s => s a -> Int -> a -> s a
update stack index value
  | isEmpty stack = error "Empty"
  | index == 0    = cons value $ tail' stack
  | otherwise     = cons (head' stack) $ update (tail' stack) (index-1) value

指定index の要素を更新する update の実装。
本では何故か組み込み List での実装だったので Stack での実装に変えてみました。
otherwise はもうちょっと綺麗に書けそうな気もしますが。うーん……。

まぁこんなとこですかね。
List だと連結や更新に O(n) かかっちゃうよって話ですね。