haskell-jp / questions #97 at 2021-06-13 00:48:03 +0900

IntSet みたいな~trie木~Patricia木を車輪の再開発しなければならなくなったのですが、型の御加護を受けつつ余計なreference indirectionを避けるために

data Patricia (inhabited :: Bool) :: Type where
  Branch :: {-# UNPACK #-} !Word -> !(Patricia True) -> !(Patricia True) -> Patricia True
  Tip :: {-# UNPACK #-} !Word -> Patricia True
  Nil :: Patricia False

newtype Patricia' = forall b. Patricia' (Patricia b)

みたいなことを考えたのですが、existential type って newtypeでは使えないようで、効率が悪そうというよりはただただ気持ち悪いです。empty と non-emptyを型で分離した上で、それらを統合するwrapperがheap中にもう一個できるのを回避するのは不可能でしょうか…。

何しろ、 これができないのなら

data InhabitedPatricia = Branch { label :: {-# UNPACK #-} !Word,
                                  leftChild :: !InhabitedPatricia,
                                  rightChild :: !InhabitedPatricia }
                       | Tip { key :: {-# UNPACK #-} !Word }

data Patricia = Inhabited !InhabitedPatricia | Empty

でも構わないことになる（ほんとか…？）ので。

今思いついたのが、

data Patricia (nullable :: Bool) :: Type where
  Branch :: forall nullable. {-# UNPACK #-} !Word -> !(Patricia False) -> !(Patricia False) -> Patricia nullable
  Tip :: forall nullable. {-# UNPACK #-} !Word -> Patricia nullable
  Nil :: Patricia True

newtype InhabitedPatricia = IPatricia (forall nullable. Patricia nullable)

newtype PatriciaTree = PatriciaTree (Patricia True)

っていう。