/mrsekut-p/Associated Type Synonyms

generated at 2/18/2025, 12:34:16 PM
Associated Type Synonyms

著者
Manuel Chakravarty
Gabriele Keller
Simon Peyton Jones
2005/1

大まかな流れ
Abstract
1 Introduction
2 Applications of Associated Type Synonyms
3 The Programmer's-eye view
4 The Type System
5 Type Inference
6 Functional Dependencies
7 Other related work
8 Conclusions and further work
References





>読みメモ

https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/at-syns.pdf
fun depsとassocieated type synonymの関連、みたいなやつか
コレ読みたいやつだ
fun depsとの差異を知りたいだけなので全部を読む気はない

ムズイ。理解できない


これ前提として、
hsにfun depsが実装済み、で、type familyがまだない？もしくはtype familyはあるがAssociated typesがまだない？状況で書かれたものっぽい
GHC 年表見たがこの辺の時系列よくわからなかった

Abstract
multi paramな型クラスを使用する場合にFunctionalDependenciesがよく使われるが、プログラマの意図が伝わりにくい
そこで、型クラス内にType Familyを定義するAssociated Type Familyを提案する
これは、fun depsに比べて明示的であり、fun depsの代替手段になる

1 Introduction
fun deps周りの議論をするときに Collects 型クラスを扱うのってあるあるなのか？
ということは、Type Classes with Functional Dependenciesを読んでるのとかは割とアタリマエという感じなんかな
hsclass Collects e where
  type Elem e
  empty  :: e				
  insert :: Elem e -> e -> e
  toList :: e -> [Elem e]
ちなみにType Classes with Functional Dependenciesに載ってたやつ
元のmulti paramのやつ.hsclass Collects e ce where
  empty  :: ce					-- 空のcollectionを作成
  insert :: e -> ce -> ce		-- 追加
  member :: e -> ce -> Bool		-- 存在確認
fun depsで書き換えたやつ.hs class Collects e c | c -> e where
   empty  :: c
   insert :: e -> c -> c
   member :: e -> c -> Bool
membership testってなに #??
 Elem とは何か？
 Elem c は、collection type  c の要素となる型
 Elem は、collection typeをelement typeに変える型レベル関数とみなせる
 Elem はnon-parametoricである
> However, just as  insert  is non-parametric (its implementation varies depending on  c ), so is  Elem .
>>  For example, Elem [e]  is  e , but  Elem BitSet  is  Char .
 c はassociated type  Elem c を持つ
具体定期にどういう型なのかはclass宣言時には指定しない
isntance宣言時に与えられる
hsinstance Eq e => Collects [e] where
	type Elem [e] = e
	..
	
instance Collects BitSet where
	type Elem BitSet = Char
	..
	
instance (Collects c, Hasable (Elem c)) => Collects (Array Int c) where
	type Elem (Array Int c) = Elem c
	..
fun depsと比較してどちらが良いのかを言いたいわけではない
our goal here is only to describe and characterise a new pointin the design space of type classes.


2 Applications of Associated Type Synonyms
Associated Type Familyの有用性とsemanticsの調査
hs{-# LANGUAGE TypeFamilies      #-}
{-# LANGUAGE FlexibleInstances #-}


data I f = I f
data C f = C f
data S f = S String f

formatSpec :: S (I (S (C String)))
formatSpec = S "Int: " $ I $ S ", Char: " $ C $ "."


class Format fmt where
  type Sprintf fmt
  sprintf' :: String -> fmt -> Sprintf fmt

instance Format String where
  type Sprintf String = String
  sprintf' prefix str = prefix ++ str

instance Format a => Format (I a) where
  type Sprintf (I a) = Int -> Sprintf a
  sprintf' prefix (I a) = \i -> sprintf' (prefix ++ show i) a


instance Format a => Format (C a) where
  type Sprintf (C a) = Char -> Sprintf a
  sprintf' prefix (C a) = \c -> sprintf' (prefix ++ [c]) a

-- errorになる
instance Format a => Sprintf (S a) where
  type Sprintf (S a) = Sprintf a
  sprintf' prefix (S str a) = sprintf' (prefix ++ str) a

sprintf :: Format fmt => fmt -> Sprintf  fmt
sprintf = sprintf' ""











3 The Programmer's-eye view
Associated Type Familyが決定可能である場合に型推論を維持するために必要な構文上の制約について説明
4 The Type System
Associated Type Familyをサポートする型システムの提供
System F styleで記述したものを載せる
5 Type Inference
Associated Type Familyから生じるnon-syntactic equalitiesを処理できる型推論アルゴリズムの提示
これはA theory of qualified typesのqualified typeの拡張である


6 Functional Dependencies
fun depsとの比較
fun depsには3つのvariantが存在するので比較は複雑になる
1 Type Classes with Functional Dependenciesで記述されたもの
決定可能である
2 GHCで実装されているもの
決定可能でない
3 A theory of overloadingで形式化されたもの
Peter J. Stuckey
Martin Sulzmann
よくわからんが、一部を妥協することで1,2より一般的になっている
決定可能である
Associated Type Familyも決定可能である



7 Other related work
Hindley-Milner, ML moduleについての関連
8 Conclusions and further work
References