3 Some Familiar Data Structures in a Functional Setting ぱらぱらめくる『Purely Functional Data Structures』

• Leftist heaps、Binomial queues、red-black trees
• 手続き型言語が持つデータ構造は、関数型言語に移しやすいものとそうでないものがある
• 移しやすい例
  • leftist heaps : 手続き・関数のどちらでも実装しやすい
  • binomial queues: 関数型でやりやすい
  • red-black trees: 関数型でやりやすい
    • RB-tree with Haskell (0)日本語
    • RB-tree with Haskell(1)
    • RB-tree with Haskell(2)
• ヒープ探索

module Heap (Heap(..))

where

class Heap h where

empty :: Ord a => h a
empty = undefined

isEmpty :: Ord a => h a -> Bool
isEmpty = undefined

insert :: Ord a => a -> h a -> h a
insert = undefined

merge :: Ord a => h a -> h a -> h a
merge = undefined

findMin :: Ord a => h a -> a
findMin = undefined

deleteMin :: Ord a => h a -> h a
deleteMin = undefined