Subscribed unsubscribe Subscribe Subscribe

代数的データ型を使わないリスト

Haskell

Haskellでは代数的データ型がよく使われています。取り扱いも簡単だしパターンマッチも便利。たとえばリストは次のように定義できます。

data List a = Nil | Cons a (List a)

でも、実は代数的データ型を使わずにリストを表現することもできます。え?さっぱり浮かばない?ではこんな型を考えてみましょう。

{-# LANGUAGE Rank2Types #-}
type List a = forall r. r -> (a -> r -> r) -> r

nil :: List a
nil x _ = x

cons :: a -> List a -> List a
cons x xs = \nil' cons' -> cons' x (xs nil' cons')

はて、これはいったい…本当にこれはリストなのでしょうか?帰納的なデータ構造のお友達foldrを定義してみます。

foldr :: (a -> b -> b) -> b -> List a -> b
foldr f z xs = xs z f

するとあら不思議、リストの総和を簡単に求められるようになりました。

sum :: List a -> Int
sum = foldr (+) 0

ほら、ちゃんと動いているでしょ。

Prelude> sum (cons 1 (cons 2 (cons 3 nil)))
6