2

T次の型は、Haskell または別の関数型言語で正式に定義できますか?

Typeには、 からのオブジェクトのコレクション(つまり、セット) を指定すると、そのコレクション内の各オブジェクトに番号を割り当てるT関数が含まれます。X

たとえば、tからの関数があるとしTます。その引数は、文字列のリスト ['abc', 'def', 'xyz'] など、argからのオブジェクトのコレクション (セット) でなければなりません。その戻り値は、 、またはの3 つの引数のみを取りX、数値を返す関数でなければなりません。この場合、特に引数として任意の文字列を受け入れたくありません。r'abc''def''xyz'r

例としては、オブジェクトのコレクションが与えられると、何らかの形でそれぞれにランクを割り当てる「ランク関数」があります。数値のコレクションだけを返すわけではありません。むしろ、元のコレクションのメンバーのいずれかを取得し、そのメンバーのランクを返す関数を返します。

もちろん、要件を少し変更すると、物事は非常に単純になります。t関数が単にオブジェクトのコレクションを取り、数値のコレクションを返すように頼むこともできます。これはほとんど同じですが、まったく同じではありません。このような定義には、追加の作業が必要になります。入力コレクションのオブジェクトと出力コレクションのオブジェクトを一致させる必要があります。また、それほど正確ではありません。返される数値のコレクションが入力オブジェクトと一致しない可能性があります (たとえば、1 つの数値が多すぎる可能性があります)。

私が説明している制約が型制約として表現できず、別の方法で強制する必要があるとしても驚かないでしょう。

EDIT:私はもともとU、関数を数値に取り、Xtype の関数を返す関数を含む型を定義することも求めていましたT。しかし、私はこれをうまく説明していませんでした.それは私の質問に混乱を加えるだけです. したがって、私の質問のこの部分は無視することをお勧めします。

4

3 に答える 3

1

T - タグ付け

分かりやすくするために、タイプの名前を変更したいと思います。T値に数値を割り当てます。コンテナーの構造が不明なため (そして柔軟性を維持したいので)、値と数値をペアでポップします(x,n)。そのタグ付けを reaname と呼びましょう。あなたのコレクションタイプがs のコレクションであるT Taggerことがわかっていると仮定すると、 typeが必要になるので、必要になりますCollXColl X

type CollTaggerXInt = Coll X -> Coll (X,Int)

これにより、必要な関数の型シノニムが作成されます。

しかし、が小さすぎてやその他の数値型Intを使用したい場合はどうでしょうか。IntegerDouble

data Num n => CollTaggerX n = CollTaggerX (Coll X -> Coll (X,n))

Xこれは、任意の固定タイプの数値データで値にタグを付けることができることを意味します。(Num n =>は、n が数値型でなければならないことを表明するデータ型制約です。) 右側の CollTaggerX は、タグ付け関数を軽量コンストラクターでラップすることにより、型の安全性を保証します。でパラメータ化したので、data代わりにを使用する必要があります。typen

コードの再利用を改善するために、固定型Xとコレクション型を型パラメーター (Java などの一部の言語のジェネリックなど)に置き換える傾向があります。Coll

data (Functor coll,Num n) => Tagger coll x n = Tgr (coll x -> coll (x,n))

collそのため、 ection タイプは Functor であると主張したので、fmap関数をポイントごとにコレクションに適用するために使用できます (あなたのケースでは重要であり、どのコレクション タイプも Functor のインスタンスになります)。

私はTaggerfor yourのその定義に最も満足していますが、 , andの可能性が 1 つしかない場合にT使用できます。CollTaggerXIntcollxn

U - タガーの作成

あなたのUタイプは、要素ごとのタガーをコレクションのタガーに変えるためのものです。Liftではなく、ingと呼んでいるような気がしUます。を使用している場合はCollTaggerXInt、型シノニムを再度使用できます。

type LiftXIntToTagger = (X -> Int) -> Coll X -> Coll (X,Int)

または、より柔軟なTagger定義を使用している場合は、次のように書くことができます

data (Functor coll,Num n) => Lifter coll x n = Lifter ((x -> n) -> coll x -> coll (x,n))

しかし、これはすべて、これの型を作成するのは気が狂っているように感じます。なぜなら、ポイントごとの関数がある場合は、とにかく型fmapで機能する which を使用して、すでにそれを持ち上げることができるからです。coll

fmap :: Functor f => (a -> b) -> f a -> f b

したがって、これをcollas fxas a(x,n)as b で使用して、定義することができます

liftT :: (Functor coll,Num n) => (x -> n) -> coll x -> coll (x,n)
liftT f = fmap tag   where 
      tag x = (x,f x)

あなたのタイプを定義したいのなら、OKですが、あなたのタイプでliftT唯一の賢明な関数かもしれないと思いますU

ランク - U+コンテキスト

あなたのランクの例は役に立つと思うので、それを調べてみましょう。ランク関数はコレクションのすべての要素を調べる必要があるため、コレクション全体を最初のパラメーターとしてrankfunction :: coll x -> x -> n( context 内で(Functor coll,Num n)) 与えましょう。

liftInContext :: (Functor coll,Num n) => (coll x -> x -> n) -> coll x -> coll (x,n)
liftInContext rankfunction mycoll = liftT (rankfunction mycoll) mycoll

ここで関数(rankfunction mycoll)は、liftT を使用して各要素に適用する前に、rankfunction にその最初のパラメーター (コレクション全体) を渡します。これは部分評価と呼ばれ、このような場合に非常に便利です。

于 2012-09-18T11:55:01.047 に答える
1

編集:質問の更新に照らして、この回答を完全に書き直しました。

型の重要性を少し無視して実用的なアプローチを取り、Haskell でこの機能を構築してみましょう。まず、関数、オブジェクトのリスト、およびオブジェクトが与えられた場合、そのオブジェクトがリストにある場合にそのオブジェクトに関数を適用する関数を次に示します。

u f list x = assert (x `elem` list) $ f x

(アサート関数は from ですControl.Exception) これはガードでも実現できます。

u f list x | (x `elem` list) = f x --similar but gives a slightly different error msg

ghci でいくつかの例を実行すると、次の結果が得られます。

*Main> u (+1) [1,2,3] 1
2
*Main> u (+1) [1,2,3] 2
3
*Main> u (+1) [1,2,3] 3
4
*Main> u (+1) [1,2,3] 4
*** Exception: test.hs:3:14-19: Assertion failed

ただし、関数がこの方法で呼び出されてクラッシュが発生しないという静的な保証がないため、これはあまり安全なコードではありません。

別のアプローチは、Maybe型を使用することです。

u' f list x = if elem x list then Just (f x) else Nothing

次の動作があります。

*Main> u' (+1) [1,2,3] 2
Just 3
*Main> u' (+1) [1,2,3] 3
Just 4
*Main> u' (+1) [1,2,3] 4
Nothing

これは、関数が間違った方法で呼び出されないことを静的に保証するものではありませんが、戻り値に基づく結果が と の両方Just resultを処理する必要があることを静的に保証しNothingます。Maybeこれには、失敗する可能性のある計算と考えることができるモナドであるという利点もあります。したがって、このように簡単に呼び出しをチェーンできます

*Main> let func = u' (+1) [1,2,3]
*Main> func 1
Just 2
*Main> func 1 >>= func
Just 3
*Main> func 1 >>= func >>= func
Just 4
*Main> func 1 >>= func >>= func >>= func
Nothing

これは、Haskell でこのような問題を解決する最も実用的な方法のようです。しかし、質問は、このような機能を具体的にピン留めするタイプがあるかどうかを尋ねます。これらの関数の型を見てみましょう:

u  :: Eq x => (x -> a) -> [x] -> x -> a
u' :: Eq x => (x -> a) -> [x] -> x -> Maybe a

これらのタイプのどちらも、それらを機能させるかどうかはリストのメンバーであることを要求しません。これを型として機能させる唯一の方法は、コレクション自体を型と見なすことです。その type を呼び出すとcol、次のことができます

u :: (col -> x) -> col -> x

しかし、これは実用的な価値がほとんどないだけでなく、これらの機能を正確に特定することもできません。ペアに基づくアプローチも同様です。私の経験では、値のみを含む型のような非常に制限的な型を構築しようとすることは、['abc', 'def', 'xyz']あまり実用的ではありません。

于 2012-09-18T11:13:09.183 に答える
0

値を取り、型を返す関数が必要な場合 (特に)、依存型が必要になります。Haskell で依存型をシミュレートできますが、きれいではありません。

于 2012-09-18T19:31:00.513 に答える